Two-machine open shop scheduling with special transportation times

D Rebaine and V A Strusevich ()
Additional contact information
D Rebaine: University of Tizi-Ouzou
V A Strusevich: University of Greenwich

Journal of the Operational Research Society, 1999, vol. 50, issue 7, 756-764

Abstract: Abstract The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.

Keywords: open shop scheduling; transportation time; two machines (search for similar items in EconPapers)
Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2600769 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:50:y:1999:i:7:d:10.1057_palgrave.jors.2600769

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2600769

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().