Search

CN-121981506-A - Multi-mode multi-target reentrant mixed flow shop scheduling method

CN121981506ACN 121981506 ACN121981506 ACN 121981506ACN-121981506-A

Abstract

The invention relates to the technical field of workshop scheduling, in particular to a multi-mode multi-target reentrant mixed flow workshop scheduling method, which is based on a multi-mode multi-target model method driven by layered online learning and comprises the following steps of 1, establishing a problem model; the method comprises the steps of setting operation parameters of a method, generating a population by adopting an initialization strategy, judging whether a first-stage termination condition is met or not, if not, executing a first-stage evolution strategy and an environment selection strategy on the population, otherwise, executing step 5, constructing a multi-mode file, and judging whether a second-stage termination condition is met or not, wherein the method comprises the steps of judging whether the target space is converged, maintaining the diversity of a decision space, and effectively excavating a large number of multi-mode scheduling solutions with equivalent performances and different structures.

Inventors

  • HAN YUYAN
  • Li Chexiang
  • WANG YUTING
  • LI HUAN
  • MA MINGXIAO
  • WANG YUE
  • ZHAO JIAXIN

Assignees

  • 聊城大学

Dates

Publication Date
20260505
Application Date
20260409

Claims (10)

  1. 1. The multi-mode multi-target reentrant mixed flow shop scheduling method is based on a multi-mode multi-target model factor method driven by layered online learning and is characterized by comprising the following steps of: step 1, taking the minimum maximum finishing time and the minimum total energy consumption as optimization targets, and simultaneously maximizing the number of multi-mode solutions, and establishing a multi-mode multi-target reentrant mixed flow shop scheduling problem model; step 2, setting operation parameters of the scheduling problem model; Step 3, generating a population by adopting an initialization strategy based on the operation parameters, and setting the operation time of the method; step 4, judging whether the first stage termination condition is reached currently according to the running time of the method, if not, executing a first stage evolution strategy and a first stage environment selection strategy on the population, otherwise, executing step 5; Step 5, extracting multi-modal solutions from the population to construct a multi-modal file; And 6, judging whether the second-stage termination condition is reached currently according to the running time of the method, if not, executing a second-stage evolution strategy, environment selection, energy-saving strategy and genetic strategy on the population and the multi-mode file, and otherwise, outputting a pareto solution set and a pareto front.
  2. 2. The method according to claim 1, wherein the step 3 comprises: the first stage population is based on Encoding a workpiece sequence of each pass, wherein the workpiece sequence is Generating an initial scheduling scheme through a diversity heuristic method, and distributing workpieces to all machines; Wherein, the For a sequence of workpieces Is used for the indexing of (a), Is the first The number of workpieces to be processed is one, For the last machined workpiece; For the number of lanes.
  3. 3. The method according to claim 1, wherein the step 6 comprises: judging whether the second stage termination time is reached according to the running time ; If the energy-saving strategy is not achieved, a second-stage evolution strategy is executed on the population, the population and the multi-mode file are updated by adopting a second-stage environment selection strategy, and then the energy consumption is further reduced by adopting an energy-saving strategy on the population and the multi-mode file; Performing a second-stage genetic operation every five iterations, and updating the population and the multi-mode file by adopting a second-stage environment selection strategy, wherein the population and the multi-mode file in the second stage are jointly encoded by adopting a process sequence and a machine sequence, and the process sequence is that The machine sequence is ; Wherein, the Is a sequence of procedures Is used for the indexing of (a), For the last working procedure of the process, For machine sequences Is used for the indexing of (a), Machine assigned to last process, expiration time of second stage ; Wherein, the Is the number of the work pieces, Is the number of times, Is the number of stages.
  4. 4. The method according to claim 2, wherein the diversity heuristic method of step 3 is specifically as follows: The work piece firstly generates seed sequence according to the non-ascending arrangement of the total processing time ; Then, three workpiece insertion rules are adopted to generate a workpiece sequence The three workpiece insertion rules comprise an insertion rule aiming at minimizing the maximum finishing time, an insertion rule aiming at minimizing the total energy consumption, and an insertion rule for simultaneously optimizing the maximum finishing time and the total energy consumption; After the workpiece is inserted, five machine distribution modes are adopted, wherein the five machine distribution modes comprise: (1) Selecting a machine that is capable of earliest completing processing of the workpiece, when there are a plurality of machines that meet the condition, selecting a machine that has the lowest total energy consumption at the allocation; (2) Selecting a machine capable of enabling the workpiece to finish machining at earliest, and randomly selecting one machine when a plurality of machines meeting the conditions exist; (3) Selecting a machine capable of minimizing total energy consumption, and selecting a machine capable of finishing processing earliest when a plurality of machines with the same energy consumption exist; (4) Selecting a machine capable of minimizing total energy consumption, and randomly selecting one machine when a plurality of machines with the same energy consumption exist; (5) When a plurality of machines with the same energy consumption exist, randomly selecting one machine; through the combination of the three workpiece insertion rules and five machine distribution modes, 15 individuals can be generated, and the rest The individual randomly generates a workpiece sequence and is generated by matching with the five machine distribution modes, wherein, Representing population size.
  5. 5. The method according to claim 1, wherein the first stage environment selection strategy in step 4 is specifically: First, to the solution set The first stage adopts a first de-duplication method, and the second stage adopts a second de-duplication method; the method comprises the following steps: the first deduplication method is based on the objective function value, and eliminates individuals with the same objective function value; Then, carrying out minimum-maximum normalization processing on each individual in the de-duplicated solution set to obtain a normalized solution set ; Then, for the normalized solution set Performing non-dominant ranking and selecting individuals layer by layer according to dominant layer to join the population if the current dominant layer is joined Later on, the population size exceeds Executing a subarea screening strategy; The subarea screening strategy comprises the following steps: The first quadrant [0,90 ° ] of the target space is uniformly divided into Sub-region Wherein the number of subareas , The region of interest is indicated by the term, Represent the first Individual region, for the ith individual within the region , And Representing a first target value and a second target value of the ith individual, respectively, according to their polar angle in the target space Determining the sub-region to which the polar angle belongs, wherein the polar angle and the region division formula are as follows: ; for individuals in each sub-region Respectively calculate it to ideal point Is the Euclidean distance of (2) Optimal point to completion time Is the Euclidean distance of (2) To the best point of total energy consumption Euclidean distance of (2) The method comprises the following steps of: ; ; ; and taking the minimum value of the distances as an individual Is a comprehensive evaluation index of (2) The method comprises the following steps: ; Each subarea is based on the comprehensive evaluation index Is selected for representative individuals.
  6. 6. The method according to claim 2, wherein the second stage evolution strategy in step 6 comprises an adaptive local search strategy based on online learning, in particular: (1) Dividing and mapping a target space; firstly, dividing a first quadrant of a target space into three characteristic subareas by adopting a target space division mode which is the same as the first-stage environment selection, wherein the three characteristic subareas are respectively a low-total-energy area Equalization optimization region Low finishing time zone Introducing an external non-dominant solution archive A as a knowledge base for online learning, and providing real-time data support for subsequent regional potential evaluation and adaptive decision-making; (2) A region selection layer decision; the region selection layer guides the self-adaptive distribution of search resources to the subregions with higher potential by on-line evaluating the evolution value of each characteristic subregion and introduces a spatial distribution sparsity index And regional uncertainty measure The method is used for comprehensively measuring the evolution potential of the subregion, and comprises the following steps: ; Wherein, the The representation is located in a sub-region Non-dominant solution set in the interior, spatial distribution sparsity The larger the value of the distribution density used for representing the solution in the region is, the sparse the distribution of the solution in the region is indicated, so that the solution has higher supplementation potential; Indicating the number of global searches and, Representing sub-regions Selected times, regional uncertainty measure The full degree of exploration for describing the region is larger, which indicates that the lower the exploration degree of the region is, the higher the exploration value is; For exploring the weight coefficient, the method is used for adjusting the influence intensity of the uncertainty item in the area selection process; the region selection layer selects the target subregion with the current most evolutionary potential according to the following criteria: ; (3) Operator selection layer in determining target subarea Then, the operator selection layer searches the operator set from the multi-mode local part based on the history search feedback accumulated on line Selecting a local search operator that performs optimally within the target sub-region, wherein Representing an operator; the multi-mode local search operator set is designed based on the structural characteristics of a key process and a non-key process, wherein a key path is defined as a longest processing sequence from a start point to an end point of an operation, processes on the key path are defined as key processes, and other processes are defined as non-key processes, and the multi-mode local search operator specifically comprises: randomly selecting a non-critical process and comparing it with Exchanging the randomly selected non-key processes to generate candidate solutions, and retaining the solutions with optimal performance on the maximum finishing time, the dominant relationship and the total energy consumption index; randomly selecting Re-distributing the working procedures to other feasible processing machines, and after generating candidate solutions, reserving the solutions with optimal performance on the maximum finishing time, the dominant relationship and the total energy consumption index; Randomly selecting a procedure and combining it with Exchanging processing machines of the same processing stage, generating candidate solutions, and retaining the solutions with optimal performance on the maximum finishing time, the dominant relationship and the total energy consumption index; Randomly selecting a key procedure and attempting to insert the key procedure into the key procedure Randomly selecting candidate positions, generating candidate solutions, and retaining the solutions with optimal performance on the maximum finishing time, the dominance relation and the total energy consumption index; Randomly selecting a procedure and combining it with Exchanging the randomly selected procedure positions to generate a candidate solution, and then retaining the solution with the optimal performance on the maximum finishing time, the dominant relationship and the total energy consumption index; Wherein, the Representing the neighborhood size of the local search, The total number of the working procedures; For each set of region-operator pairs Maintaining region-operator prize values, respectively Number of operator calls And evaluating operators in the region on line Average efficacy in Uncertainty measure The following are provided: ; Wherein, the Representation operator In the area The number of calls in; the larger the operator is, the better the history optimization effect of the operator in the area is; The larger the operator is, the higher the exploratory value of the operator in the region is; exploring a weight coefficient for an operator, and adjusting the influence intensity of an uncertainty item in the operator selection process; the operator selection layer selects the target region according to the following criteria The following optimal local search operator: ; (4) Updating an online rewarding mechanism and parameters; Based on selected local search operators The generated candidate solution is compared with the original solution In combination with the optimized emphasis points of different target subregions, constructing an instant reward function: ; Wherein, the The method respectively represents an individual with optimal finishing time, an individual with optimal dominance and an individual with optimal total energy consumption; in order to achieve a maximum finishing time, Representing individuals Is used for the maximum finishing time of the (c), Representing individuals Maximum completion time of (2); as a result of the total energy consumption, Representing individuals Is used for the energy consumption of the (a), Representing individuals Energy consumption of (2); Representing a dominance relationship; Subsequently, the region-operator rewarding matrix is modified in an incremental updating mode: ; Wherein, the Representing a region Using operators Is a region-operator prize value; finally, synchronously updating the external files Statistical information of the region selection layer and the operator selection layer.
  7. 7. The method according to claim 2 or 6, wherein the second stage environment selection strategy in step 6 is specifically: First, from the solution set Extracting multi-modal solutions, and adding the multi-modal solutions into a multi-modal file; then, to the solution set Performing a first stage environment selection; Then, executing multi-mode environment selection on the multi-mode file; the multi-modal environment selection comprises the steps of: extracting non-dominant solution from multi-modal file to form candidate solution set, when the scale of the candidate solution set is smaller than the preset multi-modal file scale The candidate solution set is used as the updated multi-modal file when the scale of the candidate solution set is not smaller than the preset multi-modal file scale In the time-course of which the first and second contact surfaces, dividing the candidate solution set into Individual target clusters Traversing all non-empty target clusters in turn, selecting a representative multi-modal file after adding update from one target cluster in each round until reaching the preset multi-modal file scale Or all target clusters are empty.
  8. 8. The method according to claim 1, wherein the step 5 comprises: extracting multi-modal solutions from the population in the first stage to multi-modal files, wherein the multi-modal solutions refer to a plurality of scheduling schemes with significant differences in decision space structure under the condition that the target space performances are the same and non-dominant, and the multi-modal files are of the scale 。
  9. 9. The method according to claim 2, wherein the second stage genetic strategy in step 6 is specifically: firstly, merging a population and a multi-mode file; then, selecting half of parent individuals from the combined population by adopting binary tournament to execute a second-stage genetic strategy; The second stage genetic strategy comprises the following steps of Partial sequential crossover to OS and uniform crossover to MS to Performing reverse order variation on OS and random machine replacement variation on MS, otherwise outputting pareto solution set and pareto front, wherein the cross probability Probability of variation OS represents a process sequence, and MS represents a machine sequence.
  10. 10. The method according to any one of claims 1-6, wherein the energy saving strategy in step 6 is specifically: firstly, starting from the last working procedure of the last workpiece in a reverse traversing mode, sequentially right-shifting each working procedure from back to front, wherein the right-shifting comprises the following rules: The first rule is that when the process does not belong to the last pass, the right shift is not later than the starting time of the corresponding process of the next stage and the subsequent process of the same machine, and the minimum value of the two processes is taken; And when the procedure belongs to the last pass, the right shift meets the two constraints in the first rule, and the minimum value of the first procedure, the second procedure and the third procedure is not later than the starting time of the first procedure of the next pass.

Description

Multi-mode multi-target reentrant mixed flow shop scheduling method Technical Field The invention relates to the technical field of workshop scheduling, in particular to a multi-mode multi-target reentrant mixed flow workshop scheduling method. Background The re-entrant mixed flow shop scheduling problem is characterized in that products need to pass through a plurality of continuous processing stages in sequence, each stage comprises a plurality of parallel devices, and on the other hand, the working procedure needs to return to the preceding stage for re-processing, so that a re-entrant processing flow is formed. Due to the diversity of equipment configuration, process paths and reworking times, a plurality of scheduling schemes with different structures and equivalent performances always exist under the same optimization target, so that the problems naturally have multi-mode characteristics. Meanwhile, in actual production, a plurality of mutually conflicting scheduling targets are usually required to be optimized simultaneously, so that the problem presents the complex characteristics of multiple modes and multiple targets. Taking a semiconductor packaging and testing production line as an example, chip products need to undergo multiple processing stages such as die bonding, packaging, curing, testing, sorting and the like in sequence. Under the requirements of high reliability and high precision manufacture, in order to meet strict performance consistency and quality stability constraint, the chip needs to be subjected to multiple rounds of refinement processing and performance consolidation processing, so that a production path for reentrant for multiple times in the same processing stage is formed, and the typical reentrant characteristic is reflected. In the process, due to the differences of optional equipment combination, processing sequence arrangement and multi-round processing path configuration, under the condition that the maximum finishing time is the same as the objective function value such as total energy consumption, various process routes and scheduling sequences with obvious structural differences can still be corresponding, and obvious multi-mode solution structural characteristics can be displayed. The multi-mode scheduling scheme enables the system to be quickly switched to an alternative equivalent scheme on the premise of not sacrificing scheduling performance when the system faces abrupt change of customer demands (such as early delivery of individual workpieces) or production disturbance, so that response flexibility and operation robustness of the production system are improved. In such production systems, the scheduling objectives include not only minimizing the maximum finishing time, but also reducing the overall energy consumption during the production process. For example, packaging equipment, curing ovens, and test tools can consume significant energy during frequent start-up and shut-down, idle, and multiple rounds of processing. Different scheduling schemes may be similar in finishing time and energy consumption index, but have obvious differences in equipment load distribution, processing round configuration, process path selection and the like, so that different influences are generated on system operation stability, equipment service life and capability of coping with uncertain disturbance. Therefore, how to effectively mine and maintain various scheduling schemes with equivalent performances and obvious structural differences while ensuring the target space convergence is a key challenge with important engineering value and research significance in the multi-mode multi-target reentrant mixed flow shop scheduling problem. Disclosure of Invention Aiming at the characteristics of multi-time reentrant processing, parallel equipment selection, performance equivalent multi-mode solution coexistence and the like existing in the problem, the application provides a multi-mode multi-target reentrant mixed flow shop scheduling method driven by layered online learning. The method takes the structural characteristics of the problem as a starting point, fully considers the multi-mode distribution characteristics of the scheduling solution in the decision space, constructs a method framework of the collaborative evolution of the population and the multi-mode file, divides the method evolution process into two stages, improves the convergence of the target space and enhances the diversity of the decision space, thereby more fully mining and maintaining various scheduling schemes with equivalent performances and obvious structural differences. Compared with the traditional flow shop scheduling method, the method is designed for the actual scheduling requirement of the re-entrant mixed flow shop, has the advantages of simple implementation, easy parameter adjustment and the like, and is excellent in target space convergence, decision space diversity and multi-modal solution discovery