Abstract
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 binary NP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.
| Original language | English |
|---|---|
| Journal | Journal of the Operational Research Society |
| DOIs | |
| Publication status | Accepted/In press - 2020 |
Keywords
- complexity
- dynamic programming
- fixed job sequence
- makespan
- Parallel machines
- single server
ASJC Scopus subject areas
- Management Information Systems
- Strategy and Management
- Management Science and Operations Research
- Marketing