Research For Flexible Flow-shop Scheduling Problem With Limited Waiting Time

Flexible flow shop scheduling problems with waiting time constraints are NP-hard combinatorial optimization problems, which widely exist in in the modem manufacturing environment. The research of the scheduling methods has vital effect on production management and control system. Considering the problems with waiting time constrains, this thesis explore the algorithms to solve the minimization of total weighted completion time or makespan.For the limited-wait flexible flow shop scheduling problem to minimize total weighted completion time, an integer programming model is formulated and an improved genetic algorithm is proposed based on penalty function method. By computing the times of violating constraints for each unit at iterative population, the intensity of each constraint is determined. Thus, it helps to search feasible solutions quickly in the former period and obtain satisfactory solutions in the later. Matlab is finally used to implement the above algorithm. The results of computational experiments show that the improved algorithm provides better global convergence and quicker searching speed.For the no-wait flexible flow shop scheduling problem to minimize makespan, a mixed integer programming model is built, and a new genetic algorithm is designed to construct the initial solution. The job-based encoding method of chromosome simplify the operators in GA. For the two-stage and multi-stage no-wait flexible flowshop scheduling problems, simulation results show the feasibility and the validity on genetic algorithm, especially for large-scale problem instances.