A heuristic for the two-machine open-shop scheduling problem with transportation times

Authors
Strusevich, VA
Citation
Va. Strusevich, A heuristic for the two-machine open-shop scheduling problem with transportation times, DISCR APP M, 93(2-3), 1999, pp. 287-304
Citations number
15
Categorie Soggetti
Engineering Mathematics
Journal title
DISCRETE APPLIED MATHEMATICS → ACNP
Volume
93
Issue
2-3
Year of publication
1999
Pages
287 - 304
Database
ISI
SICI code
Abstract
The paper considers a problem of scheduling n jobs in a two-machine open sh op to minimize the makespan, provided that preemption is not allowed and th e interstage transportation times are involved. This problem is known to be unary NP-hard. We present an algorithm that requires O(nlogn) time and pro vides a worst-case performance ratio of 3/2. (C) 1999 Elsevier Science B.V. All rights reserved.