点击次数：

论文类型：期刊论文

发表时间：2020-01-01

发表刊物：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录刊物：EI、SCIE

卷号：39

期号：1

页面范围：1-14

ISSN号：1382-6905

关键字：Flexible flow shop scheduling; Parallel machines; Approximation algorithm

摘要：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.