Research On Models And Evolutionary Algorithms Of Multi-objective Flexible Job Shop Scheduling

For discrete manufacturing enterprises with multi-type of production,small batches and flexible production mode,reasonable shop scheduling can improve production efficiency and save production costs.Meanwhile,the flexible job shop scheduling problem is a typical NP hard combinatorial optimization problem and thus,it has been a hot topic in both industry and academia.The difficulties of this problem lie in:(1)the optimization objectives may have conflict;(2)the important parameters such as processing time and delivery date may be uncertain;(3)there may be some dynamic disturbance factors,such as machine breakdown(repair),emergency insertion and so on.In addition,considering the computational complexity,we cannot mathematically solve this problem in polynomial time.In recent years,evolutionary algorithms(EAs)developed by mimicking the process of biological evolution have been widely studied by a large number of scholars,and have provided effective methods and means that are available to solve this problem.Lots of effects have been made on the multi-objective,uncertainty and dynamic flexible job shop scheduling,and researchers have obtained many significant achievements.However,most of the previous studies only focused on one of these characteristics rather than simultaneously considered them.The researches on multi-objective mainly concentrated on the low-dimensional scheduling problems by optimizing the common objectives of completion time and machine workload,whereas many-objective scheduling problems with more than three objectives are rarely studied.In addition,there are few researches on scheduling problems considering multiple dynamic events simultaneously.Since these problems have more constraints and is harder to get object values,higher requirements are put forward for the quality and efficiency of the optimization algorithm,greatly increasing the difficulty of research.To solve these more complex problems,several kinds of scheduling models and corresponding evolution optimization methods are investigated as follows.1.To address the problem of the deficiency of existing methods for solving low-dimensional static multi-objective flexible job shop scheduling problem,we propose a multiobjective memetic algorithm based on decomposition.A hybridization of different machine assignment and operation dispatching rules is designed to improve the qualities and diversifications of initial solutions.By using well-designed genetic operators,the multi-objective evolutionary algorithm based on decomposition(MOEA/D)is adapted for the global search.Besides,a local search based on moving critical operations is incorporated into MOEA/D to enhance the local exploitation.Experimental results show that the proposed algorithm can maintain the balance of convergence and diversity of Pareto front and has good computational efficiency.2.To solve the problem that processing time and due data cannot be expressed by exact values,we adopt the triangular and trapezoidal fuzzy numbers to respectively represent them,and propose memetic algorithm for solving multi-objective fuzzy flexible job shop scheduling problem.Since the aggregate function of MOEA/D is not suitable for the uncertain value,the NSGA-II is used for global search.The possibility degree of comparing two fuzzy numbers is defined,and then a Pareto dominance relation in the fuzzy sense is further proposed.A modified crowding operator based on decision space is put forward to maintain population diversity.Moreover,a variable neighborhood local search is designed to strengthen the local exploitation.Experimental results show that the proposed algorithm has better convergence.3.For the uncertain processing time,it is difficult to obtain the exact membership function.However,its inter range can be easily achieved.Based on this fact,we use the interval time to represent the processing time,and then formulate the multiobjective interval job shop scheduling problem.We propose a NSGA-II based multiobjective evolutionary optimization method to solve this scheduling problem.The NSGA-III algorithm combines machine assignment and operation dispatching rules with interval number operators to initialize population.A Pareto dominance relation ship based on inter possibility degree and a crowding measure hybridized with interval normalization are respectively proposed to improve the convergence and distribution of Pareto solutions.The experimental results show that,the algorithm can guarantee the computational efficiency and obtain the Pareto front with both good convergence and distribution.4.A model of many-objective flexible job shop scheduling is formulated,in which the completion time,machine workload,due date,cost,quality and energy consumption are simultaneously considered.Considering the environment selection mechanism based on crowding distance in NSGA-II is not suitable for many-objective optimization problems,we use the NSGA-III algorithm to solve the model.Since the machine has different processing speeds in this problem,a coding method including machine assignment,operation sequence and speed selection is firstly proposed.Then,the corresponding greedy insertion decoding method and effective genetic operators are also designed.In addition,an integrated multi-attribute decision making method is introduced to select one solution that fits into the decision maker's preference.Experimental results validate the effectiveness of NSGA-III in solving such problems.5.To address the unexpected events of urgent job arrivals,machine breakdowns and repairs in real situation,a NSGA-III based predictive-reactive method is proposed to solve the many-objective dynamic flexible job shop scheduling problem.A combination of periodic and event driven scheduling strategy is employed to divide the dynamic scheduling process into a series of static scheduling windows.In each static window,NSGA-III is applied to simultaneously optimize efficiency,workload,stability and energy consumption.Additionally,the algorithm adopts a hybrid strategy so as to generate an initialization population to preserve the original scheduling information and maintain system stability.The experimental results show the superiority of the proposed method over other rescheduling methods.6.Based on the real production conditions of mould workshop in plastic products plant,the above results have been applied into the practical shop production,and then the mould production multi-mode scheduling system is designed.The system architecture and function modules are described.Meanwhile,the actual implementation effect is also given.