Scheduling for parallel dedicated machines with a single server

Citation
Ca. Glass et al., Scheduling for parallel dedicated machines with a single server, NAV RES LOG, 47(4), 2000, pp. 304-328
Citations number
20
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Civil Engineering
Journal title
NAVAL RESEARCH LOGISTICS
ISSN journal
0894-069X → ACNP
Volume
47
Issue
4
Year of publication
2000
Pages
304 - 328
Database
ISI
SICI code
0894-069X(200006)47:4<304:SFPDMW>2.0.ZU;2-J
Abstract
This paper examines scheduling problems in which the setup phase of each op eration needs to be attended by a single server, common for ail jobs and di fferent from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two paralle l dedicated machines we Drove that the problem of finding an optimal schedu le is NP-hard in the strong sense even if all setup times are equal or if a ll processing times are equal. For the case of m parallel dedicated machine s, a simple greedy algorithm is shown to create a schedule with the makespa n that is at most twice the optimum value. For the two machine case, an imp roved heuristic guarantees a light worst-case ratio of 3/2. We also describ e several polynomially solvable cases of the later problem. The two-machine now 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 now sho p no-wait problem with a single server to the Gilmore-Gomory traveling sale sman problem and solve it in polynomial time. (C) 2000 John Wiley Be Sons, Inc.