Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments

Jianming Dong (), Joshua Chang (), Bing Su (), Jueliang Hu () and Guohui Lin ()
Additional contact information
Jianming Dong: Zhejiang Sci-Tech University
Joshua Chang: University of Alberta
Bing Su: Xi’an Technological University
Jueliang Hu: Zhejiang Sci-Tech University
Guohui Lin: University of Alberta

Journal of Scheduling, 2020, vol. 23, issue 5, No 5, 595-608

Abstract: Abstract We study a scheduling environment that finds many real-world manufacturing applications, in which there is a close connection between a hybrid multiprocessor open shop and multiple parallel identical flow shops. In this environment, there is an extended two-stage open shop, where in one stage we have a set of parallel identical machines, while in the other we have a two-machine flow shop. Our objective is to minimize the makespan, that is, the latest completion time of all jobs. We pursue approximation algorithms with provable performance, and we achieve a 2-approximation when the number of parallel identical machines is constant or is part of the input; we also design a 5/3-approximation for the special case where there is only one machine in the multiprocessor stage, which remains weakly NP-hard. Our empirical experiments show that both approximation algorithms perform much better in simulated instances; their average ratios over the proposed lower bound are around 1.5 and 1.2, respectively.

Keywords: Scheduling; Extended two-stage open shop; Two-machine flow shop; Multiprocessor; Approximation algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00633-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:23:y:2020:i:5:d:10.1007_s10951-019-00633-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-019-00633-7

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().