Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 321-332 |
| Number of pages | 12 |
| Journal | Naval Research Logistics |
| Volume | 66 |
| Issue number | 4 |
| DOIs | |
| State | Published - Jun 2019 |
Keywords
- fixed job sequence
- makespan
- parallel dedicated machines
- single server