CN-121599415-B - Optimization method for flexible job shop scheduling for solving and adjusting resource constraint

CN121599415BCN 121599415 BCN121599415 BCN 121599415BCN-121599415-B

Abstract

The invention relates to the technical field of flexible job shop scheduling in intelligent manufacturing and production scheduling, in particular to an optimization method for flexible job shop scheduling for solving and adjusting resource constraint. The method comprises the steps of initializing parameters, randomly generating an initial population, sequentially using a crossover operator and a mutation operator to evolve the current population, executing a mixed decoding strategy on the current population, sequencing individuals in the current population from small to large according to the maximum finishing time to form an elite population, updating the elite population through problem-specific local search, judging whether the evolution condition is met, executing the mathematical evolution based on the CP if the evolution condition is met, and outputting a final solution when the running time reaches the running total time. The invention has the advantages of reducing the waiting time of resources, improving the utilization rate of machines and improving the utilization efficiency and scheduling performance of resources produced in the whole workshop.

Inventors

MENG LEILEI
ZHANG YUSHUAI
CHENG WEIYAO
ZHANG BIAO
WU YAJIE
LI PENG

Assignees

聊城大学

Dates

Publication Date: 20260508
Application Date: 20260127

Claims (8)

1. An optimization method for solving and adjusting flexible job shop scheduling of resource constraint is characterized by comprising the following steps, Step 1, initializing parameters, and setting an initial population scale N p , an elite population scale N e , a crossover probability P c , a variation probability P m and a total running time; Step 2, randomly generating an initial population with a scale of N p , circularly initializing individuals, wherein the initial population is iterated from 0 to N p through a circle, and each iteration creates an individual, each individual consists of three vectors, namely a process sequence vector, a machine selection vector and a resource selection vector, wherein the length of the process sequence vector is the total number of processes, the process sequence vector is initialized, each workpiece number is repeatedly added into the process sequence vector according to the number of processes of the workpiece, then the process sequence vector is randomly arranged, N is the total number of the workpieces, the number of times of each workpiece number appearing in the process sequence vector is consistent with the number of the processes contained in the workpiece, the length of the machine selection vector is the total number of the processes, one machine is randomly selected from a processable machine set of the processes according to the sequence, the machine number in the machine set is in the range of [0, M-1], the processable machine set is the total number of the total machine, the processable machine set is the initial set which can process the corresponding processes, N is the total number of the machines of the processes, the resource selection vector is adjusted to be in the range of 0, the resource selection vector is adjusted to be the total number of the individuals, and the number of the individuals is adjusted to be 0, and the number of the individuals is generated in the initial population is adjusted to be 0; Step 3, evolution is carried out on the current population by sequentially using a crossover operator and a mutation operator; Step 4, executing a mixed decoding strategy on the current population, dividing the current population into three sub-populations with equal scale, wherein each sub-population has the scale of N p /3, respectively applying basic decoding, mathematical heuristic decoding and simulated learning auxiliary decoding to the three sub-populations, The basic decoding operation process is that an individual process sequence vector, a machine selection vector and a resource selection vector are input, and the maximum finishing time is output; traversing the j-th process of the workpiece i in the process sequence vector, acquiring a machine k of the process O i,j from the machine selection vector, acquiring an adjustment resource w of the process O i,j from the resource selection vector, if the k is processed, and the workpiece i of the current process O i,j is different from the workpiece of the previous process completed on the machine k, checking whether the w is currently available, if the w is available, directly executing the adjustment task, then executing the processing operation on the k, if the w is unavailable, waiting for the w to be available, then executing the adjustment task, and executing the processing operation on the k, and if the k is not processed, or the workpiece i of the current process O i,j is the same as the workpiece of the previous process completed on the machine k, directly executing the processing operation on the k, and recording the starting time and the ending time of the process O i,j ; The operation process of mathematical heuristic decoding is that basic decoding is executed on an input individual to generate an initial scheduling scheme, the initial scheduling scheme comprises a procedure time vector and an adjustment time vector, the starting time of each procedure and the starting time of a corresponding adjustment task of the procedure are obtained, each procedure O i,j in a procedure ordering vector is traversed, the starting time of the procedure O i,j is recorded in the procedure time vector and the starting time of the adjustment task corresponding to the procedure O i,j is recorded in the adjustment time vector from the initial scheduling scheme; The operation process of the simulated learning auxiliary decoding is that an individual process sequence vector, a machine selection vector, a resource selection vector, a state vector and a simulated learning agent are input, the maximum finishing time is output, the state vector is used for recording a workpiece i to which a process O i,j belongs and a machine k of a process O i,j , the vector length of the state vector is 2N, N is the total number of processes, and the simulated learning agent can select an adjustment resource w for enabling the maximum finishing time of the individual to be minimum according to the input state vector; traversing each process O i,j in the process sequencing vector, acquiring a machine k of a process O i,j from the machine selection vector, recording a workpiece i belonging to a process O i,j and a machine k of a process O i,j into a state vector, simulating that a learning agent selects and adjusts a resource w according to the state vector, if k is processed, and the workpiece i belonging to a current process O i,j is different from the workpiece belonging to a previous process completed on the machine k, checking whether w can be used currently, directly executing an adjustment task if the w can be used, then performing a processing operation on k, if the w can not be used, waiting for w to be used, then executing the adjustment task, then performing the processing operation on k, if k is not processed, or the workpiece i belonging to the current process O i,j is the same as the workpiece belonging to the previous process completed on the machine k, directly performing the processing operation on k, recording the starting time and the ending time of the process O i,j , and selecting the maximum ending time as the maximum finishing time of an individual; Step 5, sequencing individuals in the current population from small to large according to the maximum finishing time to form an elite population with a scale of N e , and updating the elite population through problem specific local search; And 6, judging whether the evolution condition is met, if yes, constructing a CP model, taking the individuals in the updated elite population as initial solutions in the CP model, executing the mathematical evolution based on the CP by utilizing the global searching capability of the CP model, and taking the individuals with the smallest maximum finishing time in the evolved elite population as final solutions and outputting when the running time reaches the running total time, otherwise, returning to the step 3.
2. The method of claim 1, wherein in step 3, the process of evolution of the crossover operator is to generate a random value P 1 in the range of 0 to 1, randomly select two individuals from the current population if P 1 is less than crossover probability P c , and execute the crossover operator, wherein the crossover operator comprises a priority process crossover operator and a uniform crossover operator, the priority process crossover operator is applied to the process sequencing vector, the uniform crossover operator is applied to the machine selection vector and the resource selection vector, The operation process of the priority process crossing operator is that process sequencing vectors of an individual pop 1 and an individual pop 2 are obtained, wherein the process sequencing vectors are expressed as process sequences, a list C 1 and a list C 2 are initialized, a list C 1 is used for storing the process sequences of a crossed pop 1 , a list C 2 is used for storing the process sequences of a crossed pop 2 , all workpieces are randomly divided into two different sets and respectively marked as a workpiece set I 1 and a workpiece set I 2 , processes belonging to the workpiece set I 1 in the process sequencing vectors of the pop 1 are sequentially copied to corresponding positions in the list C 1 , processes belonging to the workpiece set I 2 in the process sequencing vectors of the pop 2 are sequentially copied to unoccupied positions in the list C 2 according to the sequence in the pop 2 , the processes belonging to the workpiece set I 2 in the process sequencing vectors are sequentially copied to corresponding positions in the list C 2 , the process sequences belonging to the workpiece set I 2 in the process sequencing vectors of the pop 2 are sequentially copied to the corresponding positions in the list C 2 , the process sequences belonging to the workpiece set I 2 in the sequence in the cross 2 are sequentially copied to the list C 2 , and the sequence is assigned to the unoccupied positions in the list C 2 ; The operation process of the uniform crossover operator is that machine selection vectors of an individual pop 1 and an individual pop 2 are obtained, wherein the machine selection vectors are expressed as machine sequences, a list C 1 and a list C 2 are initialized, a list C 1 is used for storing the machine sequences of the crossed pop 1 , a list C 2 is used for storing the machine sequences of the crossed pop 2 , a binary mask vector B with the same length as the machine sequences is randomly generated, for each bit in the mask vector B, if the value is 0, a machine at a corresponding position in the machine sequences of the pop 1 is copied to a corresponding position in the list C 1 , a machine at a corresponding position in the machine sequences of the pop 2 is copied to a corresponding position in the list C 2 , if the value is 1, a machine at a corresponding position in the machine sequences of the pop 2 is copied to a corresponding position in the list C 2 , a machine sequence obtained after the crossing in the list C 1 is given a corresponding position in the machine sequences of the pop 1 , and if the value is 1, a machine at a corresponding position in the machine sequences of the pop 2 is copied to a corresponding position in the list C 2 , and a value is given to a machine after the cross-over is given a value of the machine sequence obtained by giving a value to the machine in the list 2 .
3. The method of claim 2, wherein the evolution of the mutation operator is performed by generating a random value P 2 in a range of 0 to 1 after the evolution of the crossover operator, randomly selecting an individual from the current population if P 2 is less than mutation probability P m , and executing the mutation operator, wherein the mutation operator comprises a swap mutation operator and a reassignment mutation operator, the swap mutation operator is applied to the process ranking vector, the reassignment mutation operator is applied to the machine selection vector and the resource selection vector, The operation process of exchanging mutation operators is that two different positions rand 1 and rand 2 are randomly selected from individual process sequence vectors, and the processes on the selected positions rand 1 and rand 2 are exchanged; The operation procedure of reassigning the mutation operator is to randomly select a position from the individual machine selection vector, and to reselect a machine from the machinable machine set corresponding to the selected position to replace the current machine, wherein the machinable machine set represents the set of machines capable of machining the corresponding procedure.
4. A flexible job shop scheduling optimization method for solving and adjusting resource constraints according to claim 3, characterized in that in step 5, the implementation process of performing problem-specific local search on elite population is to construct a critical path based on extraction graph model for each individual in elite population and to perform local search on each individual in elite population by using four neighborhood structures, wherein the extraction graph model is constructed by constructing an extraction graph model g= (V, C "D), G represents the current extraction graph model, V represents the set of process task nodes and two virtual nodes, each process O i,j to be processed corresponds to one process task node, the two virtual nodes include one virtual start node and one virtual end node, the start node represents the start of the whole scheduling plan, and the end node represents the end of the whole scheduling plan; C represents a set of connecting arcs representing process constraints inside the workpiece, the next process O i,j+1 being started after the previous process O i,j has to be completed in the same workpiece, i.e. an arc pointing from the corresponding process task node of process O i,j to the corresponding process task node of process O i,j+1 , D represents a set of extracted arcs representing two process task nodes connected to the same machine for processing, representing the order of processing on the machine, if process O i,j and process O i',j' are processed on the same machine, and process O i,j is before process O i',j' , i.e. there is an arc pointing from the corresponding process task node of process O i,j to the corresponding process task node of process O i',j' , C ∈d representing the set of all connected arcs and extracted arcs in the extracted graph model.
5. The method of claim 4, wherein the critical path is constructed by creating an empty critical process file for storing all identified critical process task nodes based on the constructed extraction graph model, calculating the earliest start time and the latest end time of each process task node, and calculating the earliest start time of u for any process task node u in the model , , Indicating the precursor process task node of u on the belonging workpiece, i.e. the process task node that must be processed before u in the same workpiece, Representing the precursor process task node of u on the path of the machine, i.e. the process task node processed before u on the same machine, Node for representing process task Is used as a starting point for the initial end time of (c), Node for representing process task Is used as a starting point for the initial end time of (c), Representing the adjustment time of the sequence dependence, i.e. when u follows the process task node When processing on the same machine, the earliest starting time of u is limited by the end time of the precursor process task node on the belonging workpiece and the end time of the precursor process task node on the belonging machine path plus the required adjustment time, and the later is taken out, the latest end time of u is calculated , , Indicating the subsequent process task nodes of u on the belonging workpiece, i.e. the process task nodes in the same workpiece that have to be processed after u, Representing the subsequent process task nodes of u on the path of the machine, namely the process task nodes processed after u on the same machine, Node for representing process task Is set to be the latest starting time of the (c), Node for representing process task Is set to be the latest starting time of the (c), Representing the adjustment time of the sequence dependence, i.e. when u follows the process task node When processing on the same machine, u must be finished before the processing of the subsequent process task node of the belonging workpiece is started, and must be finished before the processing of the subsequent process task node of the belonging machine path, after the calculation of the earliest starting time and the latest finishing time of all process task nodes is finished, traversing each process task node, if the earliest starting time of u Latest end time equal to u I.e. And according to the connection relation of all process task nodes in the key process file and the process task nodes in the extraction graph, the key process task nodes are connected in sequence to form one or more continuous paths from the virtual starting node to the virtual ending node, and the continuous paths are defined as key paths.
6. The optimization method for flexible job shop scheduling according to claim 5, wherein the four neighborhood structures include a swap neighborhood, an insert neighborhood, an invert neighborhood, and a reassign neighborhood, wherein, The operation process of exchanging the neighborhood is that two key working procedures are randomly selected from the key path of the individual, and the processing sequence of the selected two key working procedures is exchanged; The operation process of inserting the neighborhood is to randomly select two key processes from the key paths of the individual, and insert the selected later key process into the previous process of the selected earlier key process; The operation process of reversing the neighborhood is to randomly select two key working procedures from the key path of an individual and reverse the processing sequence of all working procedures between the two selected key working procedures; The operation of reassigning the neighborhood is to randomly select one critical process from the critical path of the individual, and to reselect one machine from the set of machineable machines of the selected one critical process to replace the current machine, the set of machineable machines representing a set of machines capable of machining the corresponding process.
7. The optimization method for flexible job shop scheduling for solving and adjusting resource constraints according to claim 6, wherein the operation process of the local search is to traverse each individual of the elite population, randomly select one from four neighborhood structures and apply to the current individual, thereby generating an initial disturbance solution, the disturbance solution represents a temporary solution generated in the local search process, traverse all neighborhood structures, select an exchange neighborhood structure and apply to obtain a new solution, update the new solution to be the current latest disturbance solution if the maximum finishing time of the new solution is smaller than the maximum finishing time of the current disturbance solution, search again from the exchange neighborhood structure, select an insertion neighborhood structure and apply until all neighborhood structures are selected, add the final disturbance solution to the new elite population if the maximum finishing time of the final disturbance solution is smaller than the maximum finishing time of the current individual, and add the final disturbance solution to the new elite population instead of the current elite population if the maximum finishing time of the final disturbance solution is not smaller than the maximum finishing time of the current individual.
8. An optimization method for flexible job shop scheduling to solve and adjust resource constraints according to any of claims 1-7, wherein the CP model contains a set of constraints, (1) (2) (3) (4) (5) (6) (7) (8) (9) Wherein, I represents the index of the work piece; j represents the process index; a process set representing a workpiece i, K representing a machine index, K representing a set of all machines, N representing a total workpiece number, N representing a total process number; representing a sufficiently large positive number; representing the total number of adjustment resources; a set of machines capable of processing step O i,j ; A continuous decision variable that is the maximum completion time; is an interval variable of the process O i,j ; Indicating the procedure Interval variable of (2); adjusting task interval variables for process O i,j ; An optional process variable on machine k for process step O i,j ; Decision variables for machine sequences including assigned optional interval variables ; A null mark; The mark of the process O i,j ; Storing a sequence dependent adjustment time for a transfer matrix of machine k; The constraint set (1) represents the goal of minimizing the maximum finishing time Function of Return interval variable End time of (2); Constraint set (2) represents interval variable The length of (2) is greater than or equal to zero, ensuring that the duration of each adjustment task is non-negative, function Function return interval variable Is a length of (2); Constraint set (3) represents interval variable Length equal to the sequence dependent adjustment time, function Returning sequence decision variables Immediately following interval variable Identifier of next interval variable thereafter, if interval variable Is a sequence decision variable The last of (3), the function returns And (2) and If interval variable Out of sequence In (c), the function returns 0, and ; The constraint set (4) represents the interval variable A start time of equal to or greater than the interval variable I.e., after the completion of the processing in the process O i,j , the adjustment task of the next process is performed, Function return interval variable Is used for the start time of (1), Function return interval variable End time of (2); a constraint set (5) is expressed on the machine k, and the interval variable The end time of (a) must be equal to or less than the in-sequence decision variable Start time of next interval variable of the selectable interval variables, function Returning sequence decision variables Medium selectable interval variable When the next interval variable starts at the same time, the interval variable is selected Non-sequence decision variables The function returns a value of 0 when the alternate interval variable Is a sequence decision variable The last of (3), the function returns a value of , Function return interval variable End time of (2); The constraint set (6) represents the interval variable Variable only in interval The processing is started after the processing is finished, namely the processing process O i,j+1 can be performed after the processing process O i,j is finished, The function represents interval variable The start time of (a) is not earlier than the interval variable End time of (2); The constraint set (7) represents the values of the interval variables With only one selectable interval variable There is a single machine for each process O i,j , Representing the variable in each interval Can only select one optional interval variable ; The constraint set (8) represents an optional inter-zone variable that ensures machine k under consideration of adjusting resources Without overlapping, transfer matrix Constraint of minimum distance between two adjacent interval variables, the minimum distance being determined by adjustment time It is decided that the method comprises the steps of, The function indicates that two processes cannot be performed simultaneously on machine k, and that there must be sufficient adjustment time between adjacent processes; the constraint set (9) represents that the use quantity of the adjustment resources is less than or equal to the total number of the adjustment resources in any time period of scheduling , The function represents interval variable 1 Adjustment resource is occupied during the duration.

Description

Optimization method for flexible job shop scheduling for solving and adjusting resource constraint Technical Field The invention relates to the technical field of flexible job shop scheduling in intelligent manufacturing and production scheduling, in particular to an optimization method for flexible job shop scheduling for solving and adjusting resource constraint. Background The flexible job shop scheduling problem (Flexible Job Shop Scheduling Problem, FJSP) is a core scheduling problem in the intelligent manufacturing system, breaks through the fixed constraint of the traditional job shop scheduling problem (Job Shop Scheduling Problem, JSP) "one-process-one-machine", allows the process to be processed on a plurality of compatible machines, and remarkably improves the production flexibility and the equipment utilization rate. The flexible job shop scheduling problem (Flexible Job Shop Scheduling Problem with Sequence-DEPENDENT SETUP TIMES, FJSP-SDST) with sequence dependent adjustment time is widely applied in light industry such as printing, chemical industry and the like as an extension form of FJSP, and FJSP-SDST considers that a machine needs to perform adjustment tasks between working procedures for continuously processing different workpieces, wherein the adjustment tasks refer to equipment state adjustment operation performed by the machine to meet processing requirements when the machine continuously processes the working procedures of the different workpieces, the operation needs to occupy corresponding adjustment resources and consume a certain adjustment time, and the adjustment time is determined by both the current working procedure and the previous working procedure. Existing FJSP-SDST studies generally assume that the tuning tasks are autonomously managed by the machine, without considering coordination and constraints of external resources, which limits applicability in a practical production environment where resources are limited, and are now addressed by solving FJSP-SDST (RFJSP-SDST) that adjusts the resource constraints. RFJSP-SDST considers the tuning tasks performed by external resources, the RFJSP-SDST problem is the NP-hard problem, and the main solution methods include exact and approximate methods. The Mixed-integer linear Programming (MILP) model and the constraint Programming (Constraint Programming, CP) model both belong to accurate methods, and an optimal solution for small-scale examples can be obtained, whereas for large-scale examples, approximation methods, particularly meta-heuristic algorithms, are effective solution tools, and the solution space is effectively explored by using evolutionary operators and search mechanisms. Imitation learning (Imitation Learning, IL) is an important field in reinforcement research, and is a decision learning method based on expert demonstration data, and by learning action decisions adopted by experts in a specific scheduling state, the mapping relationship between the states and the action decisions can be constructed, so that the method can quickly converge to an effective strategy. The RFJSP-SDST problem involves four sub-problems, process sequencing, machine selection, tuning task allocation and resource allocation, which makes RFJSP-SDST difficult to solve effectively. Therefore, a hybrid optimization method that efficiently balances resource allocation, explores solution space, and optimizes scheduling performance is needed. Disclosure of Invention The invention aims to provide an optimization method for flexible job shop scheduling for solving and adjusting resource constraint, which solves the problems of unreasonable resource allocation, insufficient solution space exploration, low search efficiency, low machine utilization rate and the like in the existing scheduling method so as to achieve the purpose of realizing the scheduling target of minimizing the maximum finishing time. The invention provides an optimization method for solving and adjusting flexible job shop scheduling of resource constraint, which is characterized by comprising the following steps, Step 1, initializing parameters, and setting an initial population scale N p, an elite population scale N e, a crossover probability P c, a variation probability P m and a total running time; step 2, randomly generating an initial population with a scale of N p; Step 3, evolution is carried out on the current population by sequentially using a crossover operator and a mutation operator; Step 4, executing a mixed decoding strategy on the current population; Step 5, sequencing individuals in the current population from small to large according to the maximum finishing time to form an elite population with a scale of N e, and updating the elite population through problem specific local search; And 6, judging whether the evolution condition is met, if yes, constructing a CP model, taking the individuals in the updated elite population as initial solutions in the CP model, exe