Indexed by:Journal Papers

Date of Publication:2020-01-01

Journal:JOURNAL OF COMBINATORIAL OPTIMIZATION

Included Journals:EI、SCIE

Volume:39

Issue:1

Page Number:1-14

ISSN No.:1382-6905

Key Words:Flexible flow shop scheduling; Parallel machines; Approximation algorithm

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)-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.