Parallel Batching And Setup Operation Scheduling Problem In Flexible Flow Shop

Production scheduling, which is both a decision-making process and combinational optimization problem, is an important part of corporation management. And the scheduling problems in flexible flow shop environment are the classic problems in the production scheduling area. The standard flexible flow shop(FFS) model contains at least two processing stages, each of which equipped with at least one identical machine and at least one stage owns at least two identical machines. In general practical environment, FFS usually has some additional elements such as parallel batching, sequence dependent setup time. Moreover, the optimization objectives such minimize the makespan, minimize the sum of the earliness-tardiness penalties need to be concerned when dealing with scheduling problem in FFS. Hence scheduling problem in flexible flow shop is quite intricate, and has been proved to be NP-hard. In the other hand, the production model has been increasingly popular in the application today for the reason that in flexible flow shop, the duplication of the number of machines in some stages can be introduced flexibility to increase the overall capacities, which can avoid bottlenecks if some operations are too long. Hence the research on the scheduling problems in FFS is tremendously significant in both academy and application.In this thesis, with the background of semiconductor assembling and testing industry, we first investigate the flexible flow shop scheduling problem, then we study the flexible flow shop scheduling problem with parallel batching scheduling problem and the flexible flow shop scheduling problem with sequence dependent setup time scheduling problem, and last, we focus on the flexible flow shop scheduling problem with parallel batching and sequence dependent setup time. In the solution aspect, we design three algorithm which are based on compact genetic algorithm and used as the global optimization purpose, additional, we explore the machine assignment scheme with multiple rules and game theory.The contributions of this work are listed as below:1. A mixed integer programming model is constructed for the flexible flow shop scheduling problem with minimizing the sum of the earliness-tardiness penalties(FFSP-ET) and a dynamic co-evolution compact genetic algorithm(DCCGA) is carried out for FFSP-ET. In DCCGA, a probabilistic model is design corresponding to FFSP-ET and two modification: the elite inheritance strategy and the co-evolution mechanism are embeded into the compact genetic algorithm to enlarge the solution searching scale and enhance the stability of the evolution process.2. A mixed integer programming model is constructed for the flexible flow shop scheduling problem with parallel batching(FFSP-PB), the process of batching of jobs and the distribution of jobs are analyzed, and then a self-adaptive co-evolution compact genetic algorithm(SCCGA) is proposed to settle FFSP-PB. In SCCGA, three things: hanming distance based individual selection mechanism, two-individual probabilistic model updating mechanism and self-adaptive elite inheritance strategy are incorporated based on the compact genetic algorithm.3. A mixed integer programming model is constructed for the flexible flow shop scheduling problem with sequence dependent setup time(FFSP-SDST). With the consideration of the two constraints come from sequence dependent setup time and machine idle time, we develop six rules for jobs' machine assignment. By combining with repeated cooperative game, an equilibrium machine assignment scheme(EMS) is derived to assign jobs to the machine at each stage. To optimize the sequence of jobs at each stage, the self-adaptive co-evolution compact genetic algorithm is used. So a self-adaptive co-evolution compact genetic algorithm with equilibrium machine assignment scheme(SCCGA-EMS) is used for solving FFSP-SDST. The results of the experiments show that, EMS could greatly reduce the sequence dependent setup time cost, and SCCGA-EMS could obtain the maximum of 80.24% ralative improvement comparing with genetic algorithm in solving FFSP-SDST.4. A mixed integer programming model is designed for the flexible flow shop scheduling problem with parallel batching, sequence dependent setup time and minimizing the sum of earliness-tardiness penalties(FFSPPS-ET). The effect of parallel batching machine maximum capacity and different jobs' processing requirements at each stage are analyzed. The equilibrium machine assignment scheme is used to assign jobs or batches to the machines at each stage, and an inflated compact genetic algorithm(ICGA) is designed for the global optimization purposed. In ICGA, a normal distribution based probabilistic model updating mechanism is introduced to improve the algorithm ability to escape from the local optimal, and enlarge the solution exploring scale; an entropy based adaptive evolution pace control mechanism is used to adjust the convergence speed adaptively. Finally, an inflated compact genetic algorithm with equilibrium machine assignment scheme(ICGA-EMS) is carried out for solving FFSPPS-ET. The results of the experiments show, ICGA-EMS could efficiently deal with FFSPPS-ET particularly the large scale ones which commonly exist in the practical environment. And the maximum relative improvement of ICGA-EMS reaches to 81.33% comparing with genetic algorithm.