Search

CN-122022265-A - Distributed flow shop scheduling method based on large model auxiliary multi-objective optimization algorithm

CN122022265ACN 122022265 ACN122022265 ACN 122022265ACN-122022265-A

Abstract

The invention discloses a distributed flow shop scheduling method based on a large-model-assisted multi-objective optimization algorithm, and particularly provides a non-dominant ordering genetic algorithm based on large language model assistance, aiming at the problems of insufficient sequence related setting time, insufficient non-waiting constraint processing and low multi-objective optimization efficiency in the existing distributed heterogeneous factory scheduling. The method comprises the steps of constructing a double-target optimization model, adopting a one-dimensional integer array coding solution structure, separating a factory operation sequence through '-1', selecting greedy initialization based on maximum finishing time or greedy initialization algorithm based on sequence dependent setting time to initialize a population by combining greedy algorithm ideas, designing a large model prompt word comprising problem definition, solution examples, evolution instructions and validity verification, executing father selection, intersection and mutation operation by a large language model, updating the population through non-dominant sorting, and finally outputting a pareto front solution.

Inventors

  • ZHAO HONG
  • QIU QI
  • LIU JING

Assignees

  • 西安电子科技大学广州研究院

Dates

Publication Date
20260512
Application Date
20251231

Claims (5)

  1. 1. A distributed flow shop scheduling method based on a large model auxiliary multi-objective optimization algorithm is characterized by comprising the following steps: S1, determining relevant parameters of a required solution, including a total job number n, a total factory number f, a machine number m in each factory, processing time pl, i, j of each job on each machine in different factories and required machine conversion time sdstl, i, j, v for processing the job, wherein the relevant parameters comprise a total job number n, a total factory number f, a total job number m, and a required machine conversion time sdstl, i, j, v for minimizing maximum finishing time (Cmax) and minimizing non-working time (Tlot) of the machine; s2, population initialization, namely setting the chromosome coding length according to the problem parameters, and randomly selecting a mode to perform greedy initialization, wherein the greedy initialization comprises greedy initialization based on Cmax and greedy initialization based on sdst. Initializing to generate Npop individuals; S3, population evolution, namely constructing prompt words by using a large language model to assist in executing selection, intersection and variation operations in the population evolution, wherein the prompt words mainly comprise four parts: a) A problem definition module for describing DHNPFSP-SDST parameters, a decoding format and Cmax and Ttot optimization targets; b) The solution example module is used for providing integer array codes of the current population solution, pareto levels of the solution, working time of each factory corresponding to the solution and total machine conversion time of each factory; c) The evolution instruction module is used for executing a parent selection strategy, a CrO1-CrO3 crossover operator and an M1-M3 mutation operator; d) The legality verification module is used for requiring generation of a solution without repeated operation and conforming to the coding format and the constraint condition; S4, evaluating the fitness, performing non-dominant ranking on the evolved population, namely performing fitness evaluation on the generated new individuals by an algorithm after finishing the operation of the step 3 each time, then directly competing the child individuals and the father individuals based on the non-dominant relationship and the crowding ranking, and selecting a better solution in the child individuals and the father individuals to enter the next generation; And S5, archiving the non-dominant solution, namely updating the external archive storing the non-dominant solution by the algorithm after each generation of evolution is completed, namely, after each operation of the step 3 is completed. The solutions which are subjected to the new solution in the archive are directly discarded, and the solutions which form the non-dominant relationship with the solutions in the archive are added to the archive; S6, judging whether the termination condition is met, if not, entering the step 3, continuing to execute the evolution operation on the current population, and if so, selecting a solution in the authority external archive, and outputting a corresponding scheduling scheme.
  2. 2. The distributed flow shop scheduling method based on the large model aided multi-objective optimization algorithm according to claim 1, wherein the scale and the optimization objective of the explicit problem in step S1 specifically follow the following steps: S1.1, defining problem parameters; Defining a total job number n, a total job set j= { J1, J2,., jn }, a total job number F, a total job set f= { F1, F2,., ff }, each of the factories comprising M machines having different processing capacities, the machine set being denoted m= { M1, M2, mm }, and the processing flow being fixed as M1 → M2 → Mm; a processing time matrix p l,i,j (representing the processing time of job i on machine J of factory l) and a sequence dependent setup time matrix sdst l,I,j,v (representing the transition time required to process job Jj machine Mi after processing job Jv on machine Mi of factory); S1.2, setting constraint conditions; The method comprises the steps of processing each job in a factory, wherein the processing of each job in the factory is continuous, the waiting time is not intermediate, and the initial setting time constraint is that the setting time of the first job in each factory on a first machine is zero; S1.3, constructing an optimization target; Maximum completion time cmax= maxC l end , where C l end is the completion time of the last job in the plant Fl. Total machine dead time ttot=Σ l=1 f Σ i=1 m T l.i idle , where T l.i idle is the idle time integration of machine Mi of factory Fl during all job processing, including setup time and wait time.
  3. 3. The distributed flow shop scheduling method based on the large model aided multi-objective optimization algorithm of claim 1, wherein in step S2, the population initialization specifically operates as follows: S2.1, the individual chromosome encoding using a one-dimensional array of integers x= [ X1, -1, X2, -1, xf ], where xl represents the job processing sequence of the factory Fl, each job Jj being represented by a unique integer identifier, "-1" being used separately only as an identifier; S2.2, generating a random number Prand between (0, 1), wherein if Prand is more than 0.5, the individual adopts greedy initialization based on Cmax, and if Prand is less than 0.5, the individual adopts greedy tooth initialization based on Ttot; S2.3, initializing a population by using a greedy strategy; a) Initializing each factory current finishing time C l current =0, finding a factory l meeting l * =arg min l C l current for each job Jj in Xshuffled, and inserting the job Jj into the job processing sequence of the factory l; b) Greedy initialization based on Ttot has the following operation forms of randomly shuffling and scrambling all job sequences to generate Xshuffled, finding the factory l with the minimum SDST time required for processing the job Jj for each job Jj in Xshuffled, and inserting the job Jj into the job processing sequence of the factory l.
  4. 4. The distributed flow shop scheduling method based on the large model assisted multi-objective optimization algorithm according to claim 1, wherein in step S3, cross and mutation operations are performed on population evolution, that is, population, mainly by means of large models through prompt words; Firstly, encoding information such as job distribution, job sequences, corresponding objective function values and the like of individual solutions in a population into a natural language format suitable for large language model processing; Then, a hint word is constructed that includes the following four parts: a) The problem definition and solution representation part is used for elaborating DHNPFSP-SDST problems, defining parameters such as the number of factories, the number of jobs and the like, defining the solution to adopt one-dimensional integer array coding, taking '1' as a factory operation sequence separator, and clearly defining optimization targets of minimizing maximum finishing time (Cmax) and minimizing machine non-working time (Ttot); b) The input solution example part selects a plurality of solutions from the current population, provides the integer array coding form of the solutions, and attribute values such as pareto level, finishing time of each factory, total machine conversion time of each factory and the like corresponding to each solution for the large model together as a context learning material to help the large model understand the relation between the solution structure and the optimization target; c) And the evolution operation instruction part gives an explicit instruction to the large model to guide the large model to execute parent selection, crossover and mutation operations. The method comprises the steps of selecting a large model from a current population, randomly selecting diversified parent solutions by the large model, optionally executing one of three cross operators CrO1, crO2 and CrO3 by a cross operation instruction, wherein CrO1 is a factory index which is obtained by acquiring a time list of each factory in the two parent solutions and corresponds to the maximum value, exchanging a work sequence of the factory in the two parent solutions, crO2 is a factory index which is obtained by acquiring a total SDST list of each factory in the two parent solutions and corresponds to the maximum value, exchanging a work sequence of the factory in the two parent solutions, and CrO3 is used for executing multi-point cross on codes of the two parent solutions, namely randomly selecting a plurality of cross points and exchanging code fragments between the cross points to generate new child codes. The mutation operation instruction requires that the large model is executed by selecting one of three mutation operators M1, M2 and M3, wherein M1 is used for randomly selecting two elements in the code and exchanging positions, M2 is used for selecting any interval in the code and reversing the sequence of the elements in the interval, and M3 is used for selecting the operation sequence of any two factories in the code and exchanging; d) And the output validity verification part is used for requiring the large model to verify the generated new solution, ensuring that the new solution accords with the designated coding format, no repeated operation exists, meeting all constraint conditions of DHNPFSP-SDST problems, and if the new solution which does not accord with the requirements exists, modifying the new solution until the requirements are met. Simultaneously, returning a preset number of effective solutions in an integer array format so as to be directly integrated into the next generation population of NSGAII algorithm; And finally, inputting the constructed prompt word into a large model, and executing crossing and mutation operations according to the prompt word requirement by the large model based on self pre-training knowledge and an inference algorithm to generate a new solution individual.
  5. 5. The method for large language model assisted multi-objective optimization for solving distributed heterogeneous flow shop scheduling problems taking sequence dependent setup time as claimed in claim 1, wherein in step S5, the archive of non-dominant solutions is updated, i.e. after each evolution is completed, it is checked one by one whether the newly generated solution updates the archive, and the following three criteria are satisfied: a) If the newly generated solution completely dominates a solution in the archive, deleting the dominated solution in the archive, and then adding the newly generated solution into the archive; b) If all solutions in the newly generated solution and the archive form a non-dominant relationship, adding the newly generated solution into the archive; c) If the newly generated solution is dominated by a solution in the archive, no update is made.

Description

Distributed flow shop scheduling method based on large model auxiliary multi-objective optimization algorithm Technical Field The invention relates to the technical field of optimization algorithms, in particular to a multi-objective evolutionary algorithm based on large language model assistance and an application method thereof in the scheduling problem of a distributed heterogeneous non-waiting flow shop considering sequence dependency setting time. Background With the global trend of digital transformation in manufacturing, the production model is transitioning from single plant production to distributed heterogeneous plant networks driven by the need for flexibility, and sustainability. In this mode, production tasks are allocated to factories with scattered geographical locations and different production capacities, which brings great complexity to production synchronization and resource optimization. The traditional factory scheduling model takes single-factory single-target optimization as a core, and mainly solves the production scheduling problem of a flow shop and a job shop through mathematical planning and heuristic algorithms. Since Johnson et al first proposed an optimal scheduling method for a two-stage flow shop, this field has developed a paradigm of research aimed at minimizing maximum finishing time. However, conventional FSP is limited to idealized scenarios that cannot address challenges in distributed heterogeneous environments that need to account for differences in different factory production levels and machine efficiencies. The traditional scheduling model has the following defects that firstly, although heterogeneous factory configuration and machine related processing parameters are commonly existing in industrial scenes, a plurality of existing models either assume that the machine capacity is homogeneous or the variability of the setting time among continuous operation sequences is not fully considered, SDST is integrated into an optimization framework to bring about calculation complexity and influence algorithm efficiency, secondly, no waiting constraint requires continuous processing among machines and no interruption, which is critical in industries such as steel casting, food processing and the like, but is less included in a multi-target distributed scheduling model, thirdly, most researches take the maximum finishing time as an optimization target, actual data show that machine idling in a distributed system can cause energy waste in a high-throughput manufacturing environment, only the maximum finishing time index is focused on key machines of a key factory to a certain extent, and the utilization rate of non-key factory machines is ignored, so that the resource saving is not facilitated. In recent years, the rapid development of large language models has revolutionized the influence of many research fields, and new possibilities are brought to solve the optimization problem. The large language model can be proficiently used for processing complex problem description and constraint by virtue of strong natural language understanding and generating capability, and has great potential in the field of optimization. The present invention has been made in view of this. Disclosure of Invention The invention aims to provide a multi-objective optimization method based on large model assistance in order to solve the scheduling problem of a distributed heterogeneous non-waiting replacement flow shop considering sequence dependence setting time. Compared with the existing multi-objective optimization algorithm, the multi-objective optimization method based on the large model assistance effectively solves the current multi-objective optimization problem by combining greedy initialization, large language model assistance evolution and external archiving storage non-dominant solution. In the population initialization link, different from the traditional random initialization mode, the invention specially designs two greedy initialization strategies aiming at two optimization targets of minimizing the maximum finishing time (Cmax) and minimizing the non-working time (Ttot) of the machine, and randomly selects and executes the greedy initialization strategies with the probability of 0.5. The initialization mode of the dual-strategy random selection enables individuals in the initial population to be closer to the optimization target, the quality of the initial population is obviously improved, and then the convergence efficiency of the algorithm is improved. In the population evolution process, the invention introduces a large language model auxiliary mechanism. The selection, crossing and mutation operations in population evolution are delegated to a large language model for execution by constructing a prompt word system comprising four parts of problem definition, solution examples, evolution instructions and validity verification. The large language model is based on strong natural