# Scheduling for parallel dedicated machines with a single server

Glass, Celia A., Shafransky, Yakov M. and Strusevich, Vitaly A.
(2000)
*Scheduling for parallel dedicated machines with a single server.*
Naval Research Logistics, 47 (4).
pp. 304-328.
ISSN 0894-069X (Print), 1520-6750 (Online)
(doi:10.1002/(SICI)1520-6750(200006)47:4<304::AID-NAV3>3.0.CO;2-1)

## Abstract

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is NP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore-Gomory traveling salesman problem and solve it in polynomial time. (c) 2000 John Wiley & Sons, Inc.

Item Type: | Article |
---|---|

Additional Information: | [1] First published online: 6 April 2000. [2] Published in print: June 2000. |

Uncontrolled Keywords: | scheduling, parallel dedicated machines, single server, complexity, approximation |

Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software |

Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |

Related URLs: | |

Last Modified: | 14 Oct 2016 09:00 |

URI: | http://gala.gre.ac.uk/id/eprint/392 |

### Actions (login required)

View Item |