Title of article
A heuristic for the two-machine open-shop scheduling problem with transportation times Original Research Article
Author/Authors
V.A. Strusevich، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 1999
Pages
18
From page
287
To page
304
Abstract
The paper considers a problem of scheduling n jobs in a two-machine open shop to minimize the makespan, provided that preemption is not allowed and the interstage transportation times are involved. This problem is known to be unary NP-hard. We present an algorithm that requires O(n log n) time and provides a worst-case performance ratio of 32.
Keywords
Worst-case analysis , Open shop , approximation , Transportation time
Journal title
Discrete Applied Mathematics
Serial Year
1999
Journal title
Discrete Applied Mathematics
Record number
884914
Link To Document