The three-machine proportionate open shop and mixed shop minimum makespan problems

Christos Koulamas and George J. Kyparisis

European Journal of Operational Research, 2015, vol. 243, issue 1, 70-74

Abstract: We first consider the ordinary NP-hard three-machine proportionate open shop minimum makespan O3|prpt|Cmax problem and show that it is solvable in O(nlog n) time when certain conditions on the total machine load are met. When these conditions are not met, we derive an approximate solution by implementing the optimal solution for the O3|prpt|Cmax problem when the two longest jobs are of equal length. In that case, both absolute and ratio worst-case bounds are derived. We also consider the more general mixed shop problem M3|prpt|Cmax in which a given job subset must be processed as in a flow shop while the remaining jobs can be processed as in the O3|prpt|Cmax problem. We show that our open shop solution techniques can be implemented to derive exact and approximate solutions for the M3|prpt|Cmax problem. Finally, we discuss the applicability of our open shop results to the proportionate open shop problem with unequal machine speeds.

Keywords: Scheduling; Open shop; Mixed shop (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714009606
Full text for ScienceDirect subscribers only

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:eee:ejores:v:243:y:2015:i:1:p:70-74

DOI: 10.1016/j.ejor.2014.11.037

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().