Skip navigation

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

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

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: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 / Department / Research Group: Faculty of Architecture, Computing & Humanities
Related URLs:
Last Modified: 14 Oct 2016 08:59
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/176

Actions (login required)

View Item View Item