Strusevich, V.A., van de Waart, A.J.A. and Dekker, R. (1999) A 3/2 algorithm for two-machine open shop with route-dependent processing times. Journal of Heuristics, 5 (1). pp. 5-28. ISSN 1381-1231 (Print), 1572-9397 (Online) (doi:https://doi.org/10.1023/A:1009643112214)

Full text not available from this repository.

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 possible routes, but also the processing times depend on the chosen route. This problem 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.

Item Type:	Article
Uncontrolled Keywords:	approximation, open shop scheduling, heuristics, worst-case analysis
Subjects:	Q Science > QA Mathematics
Faculty / School / Research Centre / Research Group:	Faculty of Liberal Arts & Sciences
Related URLs:	Publisher
Last Modified:	14 Oct 2016 08:59
URI:	http://gala.gre.ac.uk/id/eprint/176

Actions (login required)

View Item