The two-stage no-wait/blocking proportionate super shop scheduling problem

Christos Koulamas and S.S. Panwalkar

International Journal of Production Research, 2019, vol. 57, issue 10, 2956-2965

Abstract: We analyze the ‘no-wait’ proportionate two-stage super shop scheduling problem with the objective of minimising the maximum job completion time (makespan). The existing simple sorting procedures for the open shop and the job shop do not work on the super shop. We show that the problem is still solvable in $ \hbox{O}({{n^3}} ) $ O(n3) time using a procedure based on dynamic programming (DP). A unique feature of this procedure is that the state variable is defined based on the number of jobs; thus, reducing the complexity to polynomial. The same procedure solves the super shop problem with the blocking constraint. We also consider the case of machine dominance and show that the problem can be solved in linear $ \hbox{O}(n ) $ O(n) time. Finally, we highlight the differences between the super shop with ‘no-wait’ and ‘synchronous’ processing modes via a numerical example.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2018.1518603 (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:taf:tprsxx:v:57:y:2019:i:10:p:2956-2965

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2018.1518603

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().