Approximation algorithms for two-stage flexible flow shop scheduling

Minghui Zhang (), Yan Lan () and Xin Han ()
Additional contact information
Minghui Zhang: Dalian Neusoft University of Information
Yan Lan: Dalian Neusoft University of Information
Xin Han: Dalian University of Technology

Journal of Combinatorial Optimization, 2020, vol. 39, issue 1, No 1, 14 pages

Abstract: Abstract This paper considers a two-stage flexible flow shop scheduling problem, where there are a single machine at the first stage and m parallel machines at the second stage. Each task can be processed by multiple parallel machines at the second stage. The objective is to minimize the makespan. Under some special conditions there is a 3-approximation algorithm for this problem. We propose a new ($$2+\epsilon $$2+ϵ)-approximation algorithm without any condition. For the case where all parallel machines assigned to a task at the second stage must have contiguous addresses, we propose two polynomial time approximation algorithms with approximate ratio less than or equal to 3 by using the existing parallel machine scheduling and strip packing results. Meanwhile two special cases are discussed when the machines number of the second stage is 2 and 3 respectively. Two approximation algorithms with approximation ratios of 2.5 and 2.67 under linear time complexity are proposed. Finally a new lower bound of the model is provided according to the classical Johnson algorithm which improves the previous result.

Keywords: Flexible flow shop scheduling; Parallel machines; 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/s10878-019-00449-3 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:jcomop:v:39:y:2020:i:1:d:10.1007_s10878-019-00449-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00449-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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