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

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

0.00 Avg rating—0 Votes
Article ID: iaor20001496
Country: Netherlands
Volume: 93
Issue: 2/3
Start Page Number: 287
End Page Number: 304
Publication Date: Jul 1999
Journal: Discrete Applied Mathematics
Authors:
Keywords: heuristics
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 3/2.

Reviews

Required fields are marked *. Your email address will not be published.