Research On Inverse Dynamic Driven Integrated Scheduling Algorithm

Integrated scheduling problem is the third kind of production scheduling problem after pipeline scheduling problem and shop scheduling problem.In this kind of production scheduling problem,the processing operation and the assembly operation are no longer distinguished,but the processing procedure and the assembly procedure are unified and dealt with together.The previous integrated scheduling solutions mostly adopt the idea of positive sequence scheduling,that is,the processing starts from the leaf node process preferentially,and the completion of root node processing indicates the completion of product processing.When it is used the idea of positive sequence scheduling to design the scheme,it is necessary to consider the constraints of the process,that is,it is necessary to consider the processing order and equipment arrangement of the process,in order to ensure the completion time of the process as short as possible.In this paper,the idea of reverse scheduling is adopted,that is,the root node process is scheduled first,and the processing of leaf node process is completed,indicating the completion of product processing.In this way,the constraints of multi-compact pre-operation can be converted into single compact pre-operation,which is convenient for the design of comprehensive scheduling algorithm.Therefore,aiming at general integrated scheduling problem,flexible integrated scheduling problem,general integrated scheduling problem considering migration time and equipment network integrated scheduling problem,this paper proposes solutions based on the reverse scheduling idea.The specific research content is divided into the following four parts:1.Aiming at the general integrated scheduling problem,a queue-driven integrated scheduling algorithm for complex products based on multi-subtree index is proposed to optimize the processing time cost of products and reduce the idle time of equipment.The algorithm mainly aims at the two states of the drive queue of the idle device resources,and adopts the queue long path priority strategy and the multisubtree index strategy to determine the scheduling order of the processes.The comparative simulation results show that the idle device resource looks for processes from its own drive queue,keeping the way of finding processes unchanged,and greatly reducing the idle waiting time on the device resource.2.In view of the problem that the previous flexible comprehensive scheduling algorithms all consider forward scheduling,so that it is necessary to consider the constraints of multiple tight preceding processes of the target process,which makes it difficult to reasonably arrange the relevant processes and thus affect the product completion time,a flexible comprehensive scheduling algorithm based on the priority of the reverse order layer is proposed.First of all,the priority strategy of the reverse order layer is proposed,and each operation is assigned to the set of operations to be scheduled in the reverse order layer;Secondly,a dynamic quasilength path strategy is proposed to determine the scheduling order of the centralized processes of the processes to be scheduled in each reverse order layer;Then,equipment selection strategy and equipment preemption strategy are proposed to determine the processing equipment and processing time of the target process;Finally,a scheduling scheme conversion strategy based on completion time reversal is proposed to convert the reverse scheduling scheme into the positive scheduling scheme.The example verification shows that compared with the existing mainstream algorithms,this algorithm can shorten the product completion time without increasing the complexity of the algorithm.3.According to the previous comprehensive scheduling algorithm for complex products,the migration time of processes between equipment is ignored or included in the processing time of its adjacent processes,resulting in inaccurate scheduling results and difficult to meet the actual production scheduling environment.Based on the framework of genetic algorithm,a complex product comprehensive scheduling algorithm based on dynamic subtree process set reverse coding is proposed.First,a reverse order coding method based on dynamic subtree operation set is proposed to enhance the quality of the initial population individuals on the basis of ensuring the legitimacy of the initial individuals.Secondly,based on the crossing vector,a single point crossing mode and a multi-point crossing mode are given respectively,both of which can ensure that the priority constraint relationship between the same equipment processes in the generated individuals is not damaged;Then,a mutation method based on mutation row vector and mutation column vector is given to ensure the feasibility and diversity of the offspring.Finally,a pre-decoding method based on device idle event-driven and a positive sequence scheme conversion strategy based on completion time reversal are given.Finally,the performance of the algorithm proposed in this paper is verified by a number of comparative experiments.4.Aiming at the problem that the idea of positive scheduling in flexible equipment network comprehensive scheduling leads to unsatisfactory scheduling results,a reverse order equipment network comprehensive scheduling algorithm based on dynamic root node operation set is proposed.In order to avoid the constraints of multiple tight preceding operations in positive sequence scheduling,the idea of reverse sequence scheduling is adopted.A coding method based on dynamic root node operation set is proposed to ensure the validity of inter-process constraints;The cross method based on the reorganization row vector and the subtree are proposed respectively to ensure the legitimacy of the individuals after the cross reorganization;The chaotic mutation method based on sibling process and the random mutation method based on mutation row vector are proposed respectively to ensure the diversity of the population.A local search strategy based on the key process equipment set is proposed to enhance the search ability of the algorithm for the optimal solution.A positive sequence scheduling scheme conversion strategy based on completion time reversal is presented,which is convenient to convert the optimal reverse sequence scheme into positive sequence scheduling scheme.The experimental results show that the proposed algorithm is feasible and effective.