Research On Flow Shop Group Scheduling Problem With Special Constraints

The flowshop group scheduling problem widely exists in the process industry with batch or group processing characteristics.In a specific production environment,the flowshop group scheduling problem is often accompanied by special constraints derived from the production process,which requires more targeted solutions.Starting from the actual production management requirements of seamless steel tubes,the thesis extracts several flowshop group scheduling problems with special but key constraints such as job-related blocking,round-trip transportation time and sequence-dependent setup time.Basic properties,mathematical models and solving algorithms of those problems are systematically studied step by step with the objective of minimizing the makespan.The main research contents and innovations are as follows:(1)Based on the actual production of seamless steel tubes in the tube-processing workshop,a two-stage flowshop group scheduling problem with job-related blocking constraint is extracted.To solve this scheduling problem,a mixed integer linear programming model is presented as first,and then the NP-hard characteristics of the problem is proved by reduction of the 3-partition problem.A co-evolutionary estimation of distributed algorithm(CEDA)was proposed according to the problem characteristics,in which the group sequence and the job sequence within each group are encoded independently.A variety of scale experiments based on the actual production data are carried out,and the result shows that the proposed model and algorithm are effective.(2)Combined with the actual production of seamless tubes in the tube-processing workshop,transportation process between stages are further considered,and a two-stage flowshop group scheduling problem with round-trip transportation times and job-related blocking is studied.Aiming at this scheduling problem,a mixed integer linear programming model is established at first,and then a co-evolutionary genetic algorithm(CGA)is proposed based on the characteristics of the problem.In the proposed CGA,the two sub-problems,namely group scheduling and job scheduling within each group,are synergistically evolved via a co-evolution framework,and a block-mining-based artificial solution construction strategy is proposed to speed up the convergence process.Numerical experiments based on actual production data are carried out.The results indicate that the proposed CGA is effective for the considered problem.(3)The round-trip transportation time constraint that is widely existed in steel production process is extended to the classic flowshop group scheduling problem,and a multi-stage flowshop group scheduling problem with sequence-dependent setup and round-trip transportation times is studied.For solving this problem,a mixed integer linear programming model is established,and an improved iterative greedy algorithm is designed.Furthermore,two different lower bounds of the problem are developed based on mathematical analysis to evaluate the solution quality of the algorithm.Experiments with different scales and comparative analysis with comparison algorithms are carried out,and the results verify the effectiveness and robustness of the proposed algorithm.(4)The classic flowshop group scheduling problem is further extended to hybrid flowshop environment,and a hybrid flowshop group scheduling problem with sequence-dependent setup and unrelated parallel machines is studied.Aiming at this scheduling problem,a mathematical model is established,and an enhanced migrating birds optimization(EMBO)algorithm is proposed.In the EMBO algorithm,a new coding and decoding scheme is designed,where the three sub-problems,including the assignment of parallel machines for each group at each stage,the sequence of groups on each parallel machine,and the sequence of jobs within each group,are uniformly coded.Based on the coding strategy,a new neighborhood construction strategy and a reset mechanism are designed to balance the global and local search capabilities.Extensive numerical experiments are conducted and comparisons with other state-of-the-art algorithms verify the effectiveness of the proposed algorithm.