摘要
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.
| 原文 | English |
|---|---|
| 頁（從 - 到） | 321-332 |
| 頁數 | 12 |
| 期刊 | Naval Research Logistics |
| 卷 | 66 |
| 發行號 | 4 |
| DOIs | |
| 出版狀態 | Published - 6月 2019 |