| A two-stage flexible flow shop scheduling is a manufacturing infrastructure designed to process a set of jobs,in which a single machine is available at the first stage and m parallel machines are available at the second stage.At the second stage,each task can be processed by multiple parallel machines.The objective is to minimize the maximum job completion time,i.e.,the makespan.This paper mainly studies the approximate algorithm design and the worst case analysis of the non-preemptively two-stage flow shop scheduling problem.The corresponding approximate algorithms are designed in multiple different machine environments and their worst cases are given.The full paper is divided into five chapters,the first chapter introduces the related concepts and preliminary knowledge of the scheduling problem,and summarizes the research results in this field in recent decades.The second chapter studies the non-preemptively two-stage flexible flow shop scheduling problem F2(1,P2)| linei | Cmax.we present an O(n log n)-time approximation algorithm with only two parallel machines on the second stage,and proved the worst case of the algorithm is 2.25.The third chapter studies the non-preemptively two-stage flexible flow shop scheduling problem F2(1,P3)| linei | Cmax.we present an O(nlogn)-time approximation algorithm with only three parallel machines on the second stage,and proved the worst case of the algorithm is 7/3,The fourth chapter studies the non-preemptively two-stage flexible flow shop scheduling problem F2(1,Pm)| linei | Cmax.we present an O(n)-time optimal algorithm under the assumption min1≤i≤n{pli}≥ max1≤i≤n {p2i} with m parallel machines on the second stage.The fifth chapter mainly introduces the conclusions and future prospects of this article. |
