|標題:||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|
|摘要:||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.|
|期刊:||JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY|
|Appears in Collections:||Articles|