標題: Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences
作者: Cheng, T. C. E.
Kravchenko, Svetlana A.
Lin, Bertrand M. T.
資訊管理與財務金融系 註:原資管所+財金所
Department of Information Management and Finance
關鍵字: Parallel machines;fixed job sequence;single server;makespan;complexity;dynamic programming
公開日期: 1-Jan-1970
摘要: We study server scheduling on parallel dedicated machines to minimize the makespan subject to given processing sequences. Before a job starts its processing on its designated machine, a loading operation must be performed, which is undertaken by a server shared by all the jobs. While the two-machine problem is polynomially solvable, we show that the problem becomes binaryNP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.
URI: http://dx.doi.org/10.1080/01605682.2020.1779625
http://hdl.handle.net/11536/155218
ISSN: 0160-5682
DOI: 10.1080/01605682.2020.1779625
期刊: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
起始頁: 0
結束頁: 0
Appears in Collections:Articles