Scheduling Methods For Multi-constraint Blocking Flow-shop

The complicated optimization problems are always a hot topic in academic and engineering fields.The production scheduling problems,as a kind of combinatorial optimization problems,usually have characteristics of complexity,multi-constraint and multi-objective.Meanwhile,most of them are NP(Non-deterministic Polynomial)hard problems,and how to design the effective scheduling optimization methods to help enterprises improve production efficiency and reduce production costs has become a key problem to be solved urgently for academia and manufacturing enterprises.The blocking flow-shop scheduling problem,as an extension of the traditional flow-shop scheduling problem,has widely existed in chemicals,pharmaceutical,iron and steel,plastic,electronic products and many other production processes.In comparison to the traditional one,it considers the flow-shop scheduling problem in the scenario without any buffers,which is closer to the actual production scenario,and has important value both on theory and practice.This dissertation combines several constraints in practical production to make a thorough study on the blocking flow-shop scheduling problem and its extensions.The main research work of this dissertation is shown as follows:(1)An estimation of distribution algorithm with path relinking is proposed for the general blocking flow-shop scheduling problem.In the proposed algorithm,a heuristic and the random method are combined to generate the initial population.The probabilistic model of the superior population is constructed by employing the job order and job blocks.To avoid the blindness of sampling,the path relinking is performed on the new individuals.An improved reference local search is introduced to further strengthen the local exploitation.Simulation experiments based on 120 benchmark instances reveal that the proposed algorithm is significantly better than 11 algorithms in the literature and achieves the new best solutions on 59 benchmark instances.(2)A heuristic with tie-breaking mechanism is firstly proposed for the blocking flow-shop scheduling problem with due date,which incorporates seven tie-breaking mechanisms to enhance the performance of the original heuristic.Afterwards,a self-adaptive discrete invasive weed optimization algorithm is also proposed.In the proposed algorithm,a self-adaptive insertion-based spatial dispersal is adopted to guide the algorithm to effectively search the solution space.A variable neighborhood search with speedup mechanism to further enhance the local exploitation.A distance-based competitive exclusion is employed to ensure the quality and diversity of the offspring population.Simulation experiments based on 480 benchmark instances indicate the performance of the original heuristic raises nearly 40% by incorporating the adopted tie-breacking mechinisms.Meanwhile,the proposed invasive weed optimization algorithm significantly outperforms 7 algorithms in the literature and obtains the new best solutions on 132 benchmark instances.(3)A multi-objective invasive weed optimization is proposed for the multi-objective blocking flowshop scheduling problem with due date.In the proposed algorithm,a decomposition-based method is developed to initialize the population.The reference line model is introduced into the reproduction phase,which balances the individuals in each searching direction.Meanwhile,the spatial dispersal and competitive exclusion phases are re-designed based on the Pareto concept.Additionally,a self-adaption phase is introduced to enhance the local exploitation ability.Simulation experiments based on 480 benchmark instances indicate the proposed multi-objective optimization algorithm can obtain the Pareto solution sets with better convergence and distribution comparing with 13 algorithms in the literature.(4)Two composite heuristics are firstly proposed for the blocking flow-shop scheduling problem with sequence-dependent setup times based on several existed heuristics.Afterwards,a discrete water wave optimization algorithm is proposed,which overrides three phases of the original water wave optimization algorithm.In the initial phase,the initial population is constructed by combining the proposed heuristic and a perturbation procedure.In the propagation phase,a two-stage propagation is employed to ensure the global exploration and local exploitation.In the refraction phase,the path relinking is adopted to avoid trapping into local optimum.In the breaking phase,a variable neighborhood search is embedded to enhance the local exploitation.Simulation experiments based on480 benchmark instances reveal that the quality of the scheduling solutions raises nearly 20% by using the proposed heuristics comparing with the original ones.Meanwhile,the proposed water wave optimization algorithm is significantly superior to 23 algorithms in the literature and achieves the best solutions on 296 benchmark instances.(5)A heuristic is firstly proposed for the distributed blocking flow-shop scheduling problem,which adopts an assignment strategy based on job load and an improved insertion mechanism.Afterwards,a discrete fruit fly optimization algorithm is proposed.In the proposed algorithm,the proposed heuristic is employed to initialize the central location of the fruit fly swarms.In the smell-based search stage,an insertion-based neighborhood operator is adopted to ensure the global exploration.In the vision-based search stage,an effective local search is embedded to enhance the local exploitation.Meanwhile,a simulated annealing-like acceptance criterion is employed to avoid trapping into local optimum.Simulation experiments based on 720 benchmark instances exhibit that the proposed heuristic enhances the quality of the scheduling solutions by 10% comparing with the original ones.Meanwhile,the proposed fruit fly optimization algorithm is significantly better than 10 algorithms in the literature and achieves the new best solutions on 353 bechmark instances.