A 3/2 algorithm for two-machine open shop with route-dependent processing times

Authors
Strusevich, VA Van De Waart, AJA Dekker, R
Citation
Va. Strusevich et al., A 3/2 algorithm for two-machine open shop with route-dependent processing times, J HEURISTIC, 5(1), 1999, pp. 5-28
Citations number
12
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
JOURNAL OF HEURISTICS
ISSN journal
13811231 → ACNP
Volume
5
Issue
1
Year of publication
1999
Pages
5 - 28
Database
ISI
SICI code
1381-1231(199904)5:1<5:A3AFTO>2.0.ZU;2-7
Abstract
This paper considers the problem of minimizing the schedule length of a two -machine shop in which not only can a job be assigned any of the two possib le routes, but also the processing times depend on the chosen route. This p roblem is known to be NP-hard. We describe a simple approximation algorithm that guarantees a worst-case performance ratio of 2. We also present some modifications to this algorithm that improve its performance and guarantee a worst-case performance ratio of 3/2.