標題: Server scheduling on parallel dedicated machines with fixed job sequences
作者: Cheng, T. C. E.
Kravchenko, Svetlana A.
Lin, Bertrand M. T.
資訊管理與財務金融系 註:原資管所+財金所
Department of Information Management and Finance
關鍵字: fixed job sequence;makespan;parallel dedicated machines;single server
公開日期: 1-Jun-2019
摘要: We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial-time algorithm to solve the two-machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP-hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.
URI: http://dx.doi.org/10.1002/nav.21846
http://hdl.handle.net/11536/151971
ISSN: 0894-069X
DOI: 10.1002/nav.21846
期刊: NAVAL RESEARCH LOGISTICS
Volume: 66
Issue: 4
起始頁: 321
結束頁: 332
Appears in Collections:Articles