CN117707083A - Scheduling method, terminal equipment and storage medium for distributed assembly line shop - Google Patents

Abstract

The invention discloses a scheduling method, terminal equipment and storage medium of a distributed assembly flow shop, and belongs to the technical field of scheduling problems of flexible distributed assembly flow workshops.

Description

Scheduling methods, terminal equipment and storage media for distributed assembly flow workshops

Technical field

The invention relates to the technical field of flexible distributed assembly flow shop scheduling issues, and in particular to a scheduling method, terminal equipment and storage medium for a distributed assembly flow shop.

Background technique

With the latest development of Industry 4.0, smart manufacturing is driving changes in manufacturing automation, making the production model more flexible, intelligent and highly integrated. As the core of intelligent manufacturing management decision-making, shop floor scheduling can integrate the physical and decision-making aspects of production planning and promote autonomous manufacturing in decentralized supply chain systems. However, with the deepening development of globalization, traditional single factory production can no longer meet the rapid changes in global market demand. In industries such as automobiles, steel, electric power, clothing, LCD, chemical processing, etc., multi-factory production or distributed production has become a popular production method. Therefore, in modern manufacturing environments, distributed workshop scheduling has attracted much attention. In addition, as energy issues become increasingly prominent, energy-saving dispatch has also received attention. In this context, studying the energy-saving distributed production scheduling problem considering energy efficiency has important practical significance and engineering application value.

Among the distributed scheduling problems that have attracted much attention at present, the Distributed Assembly Permutation Flow-Shop Scheduling Problem (DAPFSP) is a problem that widely exists in advanced manufacturing systems and modern supply chains. Many practical scheduling problems faced by manufacturing companies can be summarized as the DAPFSP model. For example, in large and medium-sized domestic companies that manufacture personal computers, all the components of each personal computer, such as CPU, battery, radiator, etc., will first be produced and processed in different factories or flow workshops. Will be delivered to the assembly factory to assemble into a personal computer.

However, DAPFSP assumes only one assembly machine during the assembly stage, which limits the flexibility of distributed production. If multiple assembly machines are used for assembly, productivity and assembly efficiency can be improved, thereby causing the distributed assembly flow shop scheduling problem to evolve into a more complex flexible distributed assembly flow shop scheduling problem (Distributed Flow-Shop WithFlexible Assembly Scheduling Problem, DFFASP) , and then it is necessary to propose a scheduling method that can solve the scheduling problem of flexible distributed assembly flow shop, thereby improving production efficiency and assembly efficiency.

The above content is only used to assist in understanding the technical solution of the present invention, and does not represent an admission that the above content is prior art.

Contents of the invention

Embodiments of the present invention achieve the purpose of solving the scheduling problem of flexible distributed assembly flow workshops by providing a scheduling method, terminal equipment and computer-readable storage medium for a distributed assembly flow workshop, thereby improving production efficiency and assembly efficiency.

To achieve the above objectives, embodiments of the present invention provide a scheduling method for a distributed assembly flow shop. The scheduling method for a distributed assembly flow shop includes the following:

According to the process parameters of the flexible distributed assembly flow shop, construct a mathematical model for the scheduling problem of the flexible distributed assembly flow shop under energy consumption constraints. The mathematical model includes an objective function and constraints;

Cluster the workpieces based on their processing time and determine the target workpieces corresponding to each factory;

According to the improved DRL algorithm model, determine the processing sequence of the target workpiece corresponding to each of the factories and the maximum completion time of the processing sequence corresponding to each of the factories;

Obtain the production sub-plan of the products to be produced in each of the factories, and determine the assembly sub-plan corresponding to each of the factories according to the production sub-plan;

Determine the objective function value according to the processing sequence of each factory and the assembly sub-plan;

When the number of iterations is not satisfied, continue to execute the step of determining the processing sequence of the target workpiece corresponding to each factory and the maximum completion time of the processing sequence corresponding to each factory according to the improved DRL algorithm model; in When the number of iterations is met, a scheduling plan corresponding to the objective function value that meets the preset conditions is output.

Optionally, the objective function is: minimizing the maximum completion time and the total energy consumption during the entire manufacturing period; wherein the total energy consumption includes 4 parts: the first part is the energy consumption when the machine is in the processing state. , the second part is the energy consumption during transportation, the third part is the energy consumption when the machine is in standby, and the fourth part is the energy consumption when the machine is in sequence-related settings; the constraints are: each job must be assigned to only one Factory, each job must be processed in an orderly manner in production, each production machine can only process one job at a time, each product must be processed on only one assembly machine, each product must be processed only after all related work has been completed and shipped to It can only be assembled when the corresponding assembly machine is on. Each assembly machine can only process one product at a time, and each assembly machine can only process one product at a time.

Optionally, the step of determining the processing sequence of the target workpiece corresponding to each factory and the maximum completion time of the processing sequence corresponding to each factory according to the improved DRL algorithm model includes:

Model the processing time of each target workpiece in the factory, and convert the processing time encoding of each target workpiece on all machines into a first vector with a fixed dimension;

Model the first vector and convert the encoding into a second vector;

The second vector is input into a decoding network built in advance based on RNN and Attention mechanisms to generate a processing sequence of the target workpiece corresponding to the factory.

Optionally, after the step of determining the processing sequence of the target workpiece corresponding to each factory and the maximum completion time of the processing sequence corresponding to each factory according to the improved DRL algorithm model, the step includes:

Obtain the network model parameters and key factories of the current DRL algorithm model and the target factory with minimized maximum completion time;

Allocate the last workpiece in the processing sequence of the key factory to the target factory, and use the network model parameters as the initial network model parameters of the DRL algorithm model, and then continue to execute the improved DRL Algorithm model, step of determining the processing sequence of the target workpiece corresponding to each of the factories and the maximum completion time of the processing sequence corresponding to each of the factories.

Optionally, train the DRL algorithm model based on a preset search algorithm; wherein the preset search algorithm includes:

The insertion neighborhood operation in the key factory randomly selects a key workpiece and inserts the key workpiece in front and behind all non-critical workpieces;

The exchange neighborhood operation in the key factory randomly selects a key workpiece and exchanges it with all other non-critical workpieces;

Randomly selecting a critical workpiece within the critical plant and swapping locations of the critical workpiece with non-critical workpieces within each non-critical plant;

The insertion neighborhood operation between key factories and non-critical factories randomly selects a key workpiece and inserts the key workpiece into the front and back of each non-critical workpiece in each non-critical factory;

Select a product with the largest total processing time on the assembly machine, and then assign the critical workpiece to another randomly selected assembly machine;

Select two adjacent products with the largest makespan difference and then randomly exchange their associated workpieces;

Swap two adjacent products with the largest makespan difference;

A product with the highest energy consumption is selected on the assembly machine and then the critical workpiece is assigned to another randomly selected assembly machine.

Optionally, the processing time of the workpiece includes: the average processing time of all processing operations of the workpiece, the processing time of the first processing of the workpiece, the processing time of the last processing of the workpiece, and the standard deviation of the processing time of all workpieces; the based on The steps to cluster the workpieces based on their processing time and determine the target workpieces corresponding to each factory include:

Use the processing time of the workpiece as a clustering criterion to construct a workpiece feature set corresponding to each workpiece;

The workpiece feature set is divided into K clusters through the K-means algorithm, where the value of K is determined based on the sum of squared errors;

Starting from the first cluster, the workpiece is assigned to each factory in sequence as the last workpiece until all workpieces are assigned to each factory, thereby determining the target workpiece corresponding to each factory.

Optionally, the step of obtaining the production sub-plan of the product to be produced in each of the factories and determining the assembly sub-plan corresponding to each of the factories according to the production sub-plan includes:

According to the production sub-plan, determine the relevant work of each of the products to be produced and the completion time of the relevant work of each of the products to be produced;

Sort the completion time of each product to be produced according to non-descending rules to obtain a priority sequence of products to be produced;

According to the order of the priority sequence, each product to be produced is sequentially taken out and assigned to the assembly machine that can complete its assembly operation earliest, thereby determining the assembly sub-plan corresponding to each of the factories.

In addition, in order to achieve the above object, the present invention also provides a terminal device. The terminal device includes: a memory, a processor, and a distributed assembly flow workshop stored on the memory and capable of running on the processor. When the scheduler of the distributed assembly flow shop is executed by the processor, the steps of the scheduling method of the distributed assembly flow shop as described above are implemented.

In addition, in order to achieve the above object, the present invention also provides a computer-readable storage medium. The computer-readable storage medium stores a scheduling program for a distributed assembly flow workshop. The scheduling program for a distributed assembly flow workshop When executed by the processor, the steps of implementing the above-mentioned scheduling method for a distributed assembly flow shop are implemented.

The first embodiment of the present invention proposes a scheduling method for a distributed assembly flow shop, terminal equipment and a computer-readable storage medium, and constructs a flexible distributed assembly under energy consumption constraints based on the process parameters of the flexible distributed assembly flow shop. A mathematical model for flow shop scheduling problems. The mathematical model includes objective functions and constraints. The workpieces are clustered based on their processing time to determine the target workpieces corresponding to each factory. Based on the improved DRL algorithm model, the target workpieces corresponding to each factory are determined. The processing sequence and the maximum completion time of the corresponding processing sequence of each factory are obtained, and the production sub-plan of the products to be produced in each factory is obtained. According to the production sub-plan, the corresponding assembly sub-plan of each factory is determined. According to the processing sequence and assembly sub-plan of each factory, Determine the objective function value, and then output the scheduling plan corresponding to the objective function value that meets the preset conditions when the number of iterations is met. When the number of iterations is not met, continue to execute the improved DRL algorithm model to determine the corresponding schedule for each factory. The processing sequence of the target workpiece and the steps of the maximum completion time of each factory corresponding to the processing sequence are achieved to achieve the purpose of solving the flexible distributed assembly flow workshop scheduling problem, improve the efficiency of workshop scheduling, and shorten the total completion time. At the same time, the energy consumption of the entire production process is reduced, and multiple scheduling objectives are reasonably balanced.

Description of the drawings

Figure 1 is a schematic flow chart of the first embodiment of the scheduling method for a distributed assembly flow workshop of the present invention;

Figure 2 is a schematic diagram of the scheduling process of the flexible distributed assembly flow workshop involved in the present invention;

Figure 3 is a network structure diagram of the DRL algorithm model involved in the present invention;

Figure 4 is a model Gantt chart of the DRL algorithm model involved in the present invention;

Figure 5 is a detailed flow chart of step S4 in the second embodiment of the scheduling method for a distributed assembly flow workshop of the present invention;

Figure 6 is a partial operation diagram of the preset search algorithm involved in the present invention;

Figure 7 is a schematic diagram of the right-shift energy-saving strategy involved in the present invention;

Figure 8 is a schematic diagram of the overall flow of the scheduling method of the distributed assembly flow shop involved in the present invention;

Figure 9 is a schematic diagram of the terminal structure of the hardware operating environment involved in the embodiment of the present invention.

The realization of the purpose, functional features and advantages of the present invention will be further described with reference to the embodiments and the accompanying drawings.

Detailed ways

It should be understood that the specific embodiments described here are only used to explain the present invention and are not intended to limit the present invention.

Since in the related technology, DAPFSP assumes only one assembly machine during the assembly stage, which limits the flexibility of distributed production. If multiple assembly machines are used for assembly, productivity and assembly efficiency can be improved, thereby causing the distributed assembly flow shop scheduling problem to evolve into a more complex flexible distributed assembly flow shop scheduling problem (Distributed Flow-Shop With Flexible Assembly Scheduling Problem, DFFASP) , and then it is necessary to propose a scheduling method that can solve the scheduling problem of flexible distributed assembly flow shop, thereby improving production efficiency and assembly efficiency.

In order to solve the above-mentioned defects in related technologies, the present invention proposes a scheduling method for distributed assembly flow workshops. Its main solution steps include the following:

By constructing a mathematical model of the flexible distributed assembly flow shop scheduling problem under energy consumption constraints based on the process parameters of the flexible distributed assembly flow shop, the mathematical model includes the objective function and constraints, and clusters the workpieces based on their processing time. Determine the target workpieces corresponding to each factory. According to the improved DRL algorithm model, determine the processing sequence of the target workpieces corresponding to each factory and the maximum completion time of the corresponding processing sequence of each factory. Obtain the production sub-plan of the products to be produced in each factory. According to the production The sub-plan determines the assembly sub-plan corresponding to each factory, determines the objective function value based on the processing sequence and assembly sub-plan of each factory, and then outputs the scheduling plan corresponding to the objective function value that meets the preset conditions when the number of iterations is met. When the number of iterations is met, continue to execute the step of determining the processing sequence of the target workpiece corresponding to each factory and the maximum completion time of the processing sequence corresponding to each factory according to the improved DRL algorithm model, so as to achieve the solution flexibility The purpose of the distributed assembly flow workshop scheduling problem is to improve the efficiency of workshop scheduling, shorten the total completion time while reducing the energy consumption of the entire production process, and reasonably balance multiple scheduling objectives.

In order to better understand the above technical solutions, exemplary embodiments of the present invention will be described in more detail below with reference to the accompanying drawings. Although exemplary embodiments of the invention are shown in the drawings, it should be understood that the invention may be embodied in various forms and should not be limited to the embodiments set forth herein. Rather, these embodiments are provided to provide a thorough understanding of the invention, and to fully convey the scope of the invention to those skilled in the art.

DAPFSP has been proven to be an optimization problem with NP-hard properties, while the distributed flexible assembly flow shop scheduling problem (DFFASP for short) is more complex than DAPFSP, which means that DFFASP is also a strongly NP-hard problem. Usually mathematical programming methods need to traverse or partially traverse the solution space of the problem, which makes this type of method take a long time to solve medium and large-scale optimization problems, resulting in certain limitations. In recent years, a series of intelligent optimization algorithms have been proposed, including swimming evolutionary calculation algorithm, EDA-based memetic algorithm, hybrid biogeography-based optimization algorithm, backtracking search and construction heuristic and hybrid variable neighborhood search, and hybrid particle seam optimization algorithm. All achieved good results.

Existing optimization methods have the following problems:

First, although intelligent optimization algorithms exhibit satisfactory performance on multiple scheduling problems, the iterative search process of these algorithms often takes a considerable time.

Secondly, the flexible distributed assembly flow shop scheduling problem (Energy-aware DFFASP, EADFFASP) considering energy efficiency is more complex than DFFASP. Therefore, EADFFASP is also a strong NP-hard problem.

Referring to Figure 1, in the first embodiment of the scheduling method of a distributed assembly flow shop of the present invention, the scheduling method of a distributed assembly flow shop includes the following steps:

Step S1: Construct a mathematical model of the flexible distributed assembly flow shop scheduling problem under energy consumption constraints based on the process parameters of the flexible distributed assembly flow shop. The mathematical model includes an objective function and constraints;

The production of flexible distributed assembly flow shop scheduling problem includes two production stages, namely the distributed production stage of multiple flow workshops and the flexible assembly stage; the production stage consists of F containing m heterogeneous machines with the same number of different functions, each A factory is regarded as a flow workshop. After the processing factory is determined for each workpiece, each process must be processed on the machine at one time according to the processing route and scheduled processing time, and regardless of whether the machine is in processing state, standby state or sequence-related setting state, Corresponding energy consumption will be generated, and corresponding energy consumption will be generated when the workpiece is transported to the next machine for processing after the current machine is processed; there are multiple assembly machines in the assembly stage, once all workpieces of a specific product are processed in the production stage After completion, it will be transported to the corresponding assembly machine for assembly. Reference may be made to FIG. 2 , which is a schematic diagram of the scheduling process of the flexible distributed assembly flow workshop involved in the present invention. Among them, Job Set represents the workpiece set and records the process parameters; Ji represents the workpiece. Production Stage represents the production stage, factory i represents the factory, and Mi represents the processing machine. AssemblyStage represents the assembly stage, and AMi represents the assembly machine. Pruduct Set represents a collection of products assembled from workpieces.

In this embodiment, the obtained process parameters of the flexible distributed assembly flow workshop specifically include: the number of workpieces, the number of products, the number of machines, the number of factories, the affiliation between workpieces and products, the distribution method of workpieces, products The processing sequence, the processing route of the workpiece, the processing time of the workpiece on the machine, the transportation time of the workpiece from the current processing machine to the next processing machine, the energy consumption during transportation, the energy consumption per unit time when the machine is in processing state or standby state , Machine program related settings energy consumption.

The objective function is set as: minimizing the maximum completion time and the total energy consumption during the entire manufacturing period. Among them, the set total energy consumption includes four parts: the first part is the energy consumption when the machine is in processing state, the second part is the energy consumption during transportation, the third part is the energy consumption when the machine is in standby, and the fourth part is the energy consumption when the machine is in standby. Part of this is the energy consumption of the machine in program-related settings.

The constraints are set as follows: each job must be assigned to only one factory, each job must be processed in production in an orderly manner, each production machine can only process one job at a time, each product must be processed on only one assembly machine, Each product can only be assembled when all related work has been completed and transported to the corresponding assembly machine. Each assembly machine can only process one product at a time, and each assembly machine can only process one product at a time.

The constraints can be expressed as:

Min(C _max ,TEC) (15)

TEC＝E _b +E _i +E _st +E _tr (16)

C _max 0,C _j,i 0,S _j,i 0,AC _k,s 0,AS _k,s 0,k,j,i,s (18)

Among them, formula (1) ensures that each job must be assigned to only one factory, formula (2) ensures that each job must be processed in order in production, and formula (3-4) ensures that each production machine can only process one job at a time , Formula (5) determines the completion time of all work, Formula (6) ensures that each product must be processed on only one assembly machine, and Formula (7) ensures that each product must be processed only when all related work is completed and shipped to the corresponding assembly machine. time to assemble, formula (8-9) ensures that each assembly machine can only process one product at a time, and formula (10) determines the completion time of all products. (8-9) ensures that each assembly machine can only process one product at a time. Formula (10) determines the completion time of all products. Formula (11-14) calculates the processing, setup, transportation and idle energy consumption respectively. Formula ( 15) is to minimize the total delivery time and total energy consumption. Formula (16) determines the total energy consumption, formula (17) determines the total completion time, and formula (18-19) represents binary decision variables and continuous variables. The parameters and symbols corresponding to the expression formulas of the above constraints can be found in Table 1.

Table 1

Step S2: Cluster the workpieces based on their processing time and determine the target workpieces corresponding to each factory;

In this embodiment, the processing time of the workpiece includes: the average processing time of all processing operations of the workpiece, the processing time of the first processing of the workpiece, the processing time of the last processing of the workpiece, and the standard deviation of the processing time of all workpieces. By using the processing time of the workpiece as a clustering criterion, a workpiece feature set corresponding to each workpiece is constructed, and then the workpiece feature set is divided into K clusters through the K-means algorithm, where the value of K is determined based on the sum of squared errors, starting from the first When the cluster starts, the workpiece is assigned to each factory in turn as the last workpiece until all workpieces are assigned to each factory, thereby determining the target workpiece corresponding to each factory, realizing the distribution of workpieces, and achieving the purpose of balancing the workload of each factory.

The average processing time of all processing operations of the workpiece can be expressed as:

Among them, p _j,i represents the processing time of workpiece j on processing machine i, and m represents the number of machines in each workpiece processing factory.

The processing time of the first processing of the workpiece can be expressed as: pj _,1 .

The processing time of the last processing of the workpiece can be expressed as: p _j,m .

The standard deviation of the processing time of all workpieces can be expressed as:

Therefore, the obtained workpiece feature set can be expressed as All workpiece feature sets can form a total feature set/> When performing further clustering, each workpiece feature set in feature set C is divided into corresponding clusters.

Step S3: According to the improved DRL algorithm model, determine the processing sequence of the target workpiece corresponding to each of the factories and the maximum completion time of the processing sequence corresponding to each of the factories;

In this embodiment, by modeling the processing time of each target workpiece in the factory, the processing time encoding of each target workpiece on all machines is converted into a first vector with a fixed dimension, and then the first vector is modeled , the encoding is converted into a second vector, and finally the second vector is input into the decoding network built in advance based on RNN and Attention mechanisms to generate the processing sequence of the target workpiece corresponding to the factory.

Specifically, reference can be made to Figures 3 and 4. Figure 3 is a network structure diagram of the DRL algorithm model involved in the present invention, and Figure 4 is a model Gantt chart of the DRL algorithm model involved in the present invention. The processing time of the target workpiece on all machines is represented by p _j,i , the first vector is represented by p _j , and the second vector is represented by P.

The modeling process for p _j,i of the workpiece is as follows:

Input p _j,i into the embedding layer to obtain the output y _j,i =W _B ·p _j,i , then input y _j,1 and h ₀ into the first RNN to obtain the hidden layer output h _j,1 =f ( y _j,1 ,h ₀ ;U,W,b), input h _j,i-1 and y _j,i into the first RNN, and get the hidden layer output h _j,i =f(y _j,i ,h _j,i-1 ;U,W,b), i=2,3,…,m, and finally p _j =h _j,m is obtained. Where W _B , h _j,i , h ₀ are all k-dimensional vectors, h ₀ , U, b, W, W _B are network parameters, and f() is the mapping from RNN input to hidden layer output.

The modeling process for all vectors p _j is as follows:

Convert p _j to Input the second RNN and get the hidden layer output/> Then add/> Enter the second RNN with p _j and get the hidden layer output/> The most 7zhon gets/> Among them/> is a d-dimensional vector,/> are network parameters.

The RNN and Attention mechanisms are used to build a decoding network and generate the workpiece sequence π _f ={π ₁ ,...,π _j } for each factory. The specific process is as follows:

Input g and P into the decoding network RNN to get the hidden layer output Where g is a k-dimensional parameter vector, representing the input at the beginning of the decoding network. Then calculate p(π ₁ |π _<1 ,s)=softmax(u ¹ ), For the hidden layer output of the second encoding RNN, and then use roulette to determine π ₁ , // and d ₁ input decoding RNN to get the hidden layer output/> Then substitute the corresponding parameters into the calculation formula of p(π ₂ |π _<2 ,s) to calculate p(π ₂ |π _<2 ,s). Then use the roulette method to determine π ₂ and repeat the above steps to get The complete workpiece processing sequence π _f for each factory. Among them g,/> v, W ₁ and W ₂ are parameters to be trained.

Take the PFSP (Partially Flexible Shop Scheduling Problem) of the first factory, 5 workpieces, and m machines as an example. First, the processing information of the five workpieces is modeled sequentially to obtain five k-dimensional vectors p _i , i = 1, 2,..., 5, and then p _i , i = 1, 2,..., 5 are input into the third Two RNNs get P. Then input P and g together into the decoding network to obtain d ₁ and p (π ₁ |π _<1 ,s), and use roulette method to determine π ₁ (assuming π ₁ = 4); then p ₄ and d ₁ together Input d ₂ and p(π ₂ |π _<2 ,s), and let p(π ₂ |π ₁ =4,s)=0, and then use the roulette method to determine π ₂ (assuming π ₂ =2) , according to the above method, the workpiece sequence π ₁ = (4,2,5,3,1) is finally obtained, that is, an encoded scheduling plan.

Step S4: Obtain the production sub-plan of the product to be produced in each of the factories, and determine the assembly sub-plan corresponding to each of the factories according to the production sub-plan;

In this embodiment, according to the production sub-plan, the related work of each product to be produced and the completion time of the related work of each product to be produced are determined, and then the completion time of each product to be produced is determined according to the non-descending order rule. Time sorting, obtain the priority sequence of the products to be produced, and take out each product to be produced according to the order of the priority sequence and assign it to the assembly machine that can complete its assembly operation at the earliest, thereby determining the assembly sub-plan corresponding to each factory, using assembly The scheduling heuristic algorithm (ASH) decodes the assembly subplan obtained in the previous step and obtains the specific assembly plan of the assembly subplan.

It can be understood that the non-descending order rule refers to the rule that the order of elements does not decrease during the sorting or arrangement process. Specifically, for a set of elements, if they are sorted or arranged according to non-descending rules, the values of the elements will increase one by one or remain unchanged. Under the non-descending order rule, when elements are arranged from left to right, each element is not less than or equal to the element before it. This rule ensures that the elements are arranged in increasing order and does not allow reverse order.

Step S5: Determine the objective function value according to the processing sequence of each factory and the assembly sub-plan;

In this embodiment, after determining the processing sequence and assembly sub-plan of each factory, the corresponding objective function value under the processing sequence and assembly sub-plan can be calculated.

Step S6: When the number of iterations is met, output the scheduling plan corresponding to the objective function value that meets the preset conditions;

Step S7: When the number of iterations is not satisfied, continue to execute the improved DRL algorithm model to determine the processing sequence of the target workpiece corresponding to each factory and the maximum completion time of the processing sequence corresponding to each factory. step.

In this embodiment, every time after the objective function value is determined, if the number of iterations or the termination condition is not met, the iteration will continue until the number of iterations or the termination condition is met, and the scheduling plan with the optimal solution will be output. The preset condition may be that the objective function value is less than the preset threshold, that is, the scheduling plan corresponding to the objective function value less than the preset threshold is output as the optimal solution.

In the technical solution provided by this embodiment, a mathematical model of the flexible distributed assembly flow shop scheduling problem under energy consumption constraints is constructed based on the process parameters of the flexible distributed assembly flow shop. The mathematical model includes an objective function and constraints, based on The processing time of the workpieces is used to cluster the workpieces and determine the target workpieces corresponding to each factory. According to the improved DRL algorithm model, the processing sequence of the target workpieces corresponding to each factory and the maximum completion time of the corresponding processing sequence of each factory are determined to obtain the information in each factory. For the production sub-plan of the product to be produced, the assembly sub-plan corresponding to each factory is determined based on the production sub-plan. According to the processing sequence and assembly sub-plan of each factory, the objective function value is determined, and then when the number of iterations is met, output that meets the preset conditions The scheduling plan corresponding to the objective function value, when the number of iterations is not satisfied, continues to execute the improved DRL algorithm model to determine the processing sequence of the target workpiece corresponding to each of the factories and the processing sequence corresponding to each of the factories. The maximum completion time step achieves the purpose of solving the flexible distributed assembly flow workshop scheduling problem, improves the efficiency of workshop scheduling, shortens the total completion time and reduces the energy consumption of the entire production process, and reasonably balances multiple scheduling objectives.

Referring to Figure 5, in the second embodiment, based on the first embodiment, before step S4, it also includes:

Step S8: Obtain the network model parameters and key factories of the current DRL algorithm model and the target factory that minimizes the maximum completion time;

In this embodiment, the key factory is the first factory to complete the workpiece processing.

Step S9: Assign the last workpiece in the processing sequence of the key factory to the target factory, use the network model parameters as the initial network model parameters of the DRL algorithm model, and then continue to execute the The improved DRL algorithm model is a step of determining the processing sequence of the target workpiece corresponding to each factory and the maximum completion time of the processing sequence corresponding to each factory.

In this embodiment, by saving the training model, the current key factory f ^* and the factory f with the smallest C _max can be recorded. Then take out the last workpiece processed by the key factory f ^* and put it into f, and use the saved network model parameters to regenerate the scheduling plan. This process is repeated until a satisfactory schedule is produced.

AC Network (Actor-Critic Network) is used to learn and optimize scheduling strategies. The AC network consists of two sub-networks: Policy Network (Actor Network) and Value Network (Critic Network).

The policy network (Actor Network) is responsible for generating the probability distribution of decisions and selected actions, that is, under a given current state, based on the learned strategy, it outputs the probability of selecting each action. The goal of the policy network is to optimize the policy parameters so that the generated actions can maximize the expected cumulative reward.

The value network (Critic Network) is responsible for estimating the value of the state and is used to evaluate the quality of the current state. The goal of a value network is to learn a baseline-based estimate, typically represented using a state-value function or a state-action value function. The estimates it outputs can be used to evaluate strategies and guide strategy improvements.

The present invention adopts AC network learning and optimization scheduling strategies. Among them, for the training method of all parameters θ of the policy network, the present invention uses the policy gradient algorithm of reinforcement learning. Among them, the input of the policy network is the processing time of each workpiece on all machines in the factory, and the output is the sequence of processed workpieces.

Specifically, assume that the processing time of a certain scheduling problem s obeys the distribution S, denoted as s~S, and the workpiece sequence π _f generated through the network obeys the distribution π _f ~p(·|s); the following two formulas respectively represent the minimized The training objective function J(θ), and the expectation J(θ|s) of the C _max of the processing sequence output by the scheduling problem s network. Among them, C _max (π|s) represents the C _max obtained by using the NEH method for the processing sequence π _f output by the network for scheduling problem s. The basic idea of the NEN method is to continuously insert jobs into the existing job sequence and select the insertion position that minimizes the total completion time until all jobs are inserted. This method recalculates the completion time of each job after each job is inserted, and finally obtains an optimal job sequence, which corresponds to the preset search algorithm of the present invention.

J(θ)＝E _s～S J(θ|s)

According to the gradient strategy, the gradient is expressed as follows:

in b(s) is the baseline that changes with π _f , which represents the estimate of C _max of problem s to reduce the training variance.

In each iteration, B independent and identically distributed s _i are sampled from the distribution S, that is, s ₁ , s ₂ ,..., s _B ~S, and the workpiece processing sequence is generated for s _i sampling. Then the approximate gradient of the objective function with respect to θ can be obtained:

Among them, the baseline Then the Adam optimization algorithm is used to iteratively optimize the network parameters.

For the selection strategy of the generated solution domain and solution for each plant, the present invention adopts the Tchebycheff (TCH) decomposition method, which is specifically defined as follows:

The reference point RP (C _maxmin , TEC _min ) is defined as the minimum value of C _max and TEC during the entire search process, the weight vector Uniformly distributed in the interval [0, 1], /> PS is the population size. Then associate each solution with eta ^b and define its objective function/> where f _r (x _b ) is the rth target value of x _b and z ^* is the normalized RP. Therefore the neighborhood of x _b is those solutions associated with the nearest weight vector based on NS Euclidean distance, including itself.

According to the above TCH decomposition, in the designed DRL algorithm, the solution update strategy is implemented and used collaboratively as follows:

If x _b and the newly generated solution x' _b satisfy g(x _b |η _b ,z ^* )≥g(x' _b |η _b ,z ^* ), then replace x _b with x' _b , otherwise it remains unchanged. When updating the neighborhood of x _b with x′ _b . If for each neighborhood x _a of x′ _b , g(x _a |η _a ,z ^* )≥g(x' _b |η _b ,z ^* ) is satisfied, then replace x _a with x' _b , and vice versa , x _a remains unchanged.

Optionally, refer to FIG. 6 , which is a partial operation diagram of the preset search algorithm involved in the present invention. The DRL algorithm model can be trained based on a preset search algorithm; wherein the preset search algorithm includes:

The insertion neighborhood operation in the key factory randomly selects a key workpiece and inserts the key workpiece in front and behind all non-critical workpieces;

The exchange neighborhood operation in the key factory randomly selects a key workpiece and exchanges it with all other non-critical workpieces;

Randomly selecting a critical workpiece within the critical plant and swapping locations of the critical workpiece with non-critical workpieces within each non-critical plant;

The insertion neighborhood operation between key factories and non-critical factories randomly selects a key workpiece and inserts the key workpiece into the front and back of each non-critical workpiece in each non-critical factory;

Select a product with the largest total processing time on the assembly machine, and then assign the critical workpiece to another randomly selected assembly machine;

Select two adjacent products with the largest makespan difference and then randomly exchange their associated workpieces;

Swap two adjacent products with the largest makespan difference;

A product with the highest energy consumption is selected on the assembly machine and then the critical workpiece is assigned to another randomly selected assembly machine.

Optionally, as an optional implementation, for a complete schedule, TEC includes processing, setup, transportation and idle energy consumption, and the idle time on each machine can be reduced by delaying the process of certain operations without Increased make time for all products. To this end, the present invention designs a right-shift energy-saving strategy, specifically, after the critical path in the factory, the workpiece processing time of other non-critical paths is delayed or moved to the right without changing the maximum completion time. Reference may be made to FIG. 7 , which is a schematic diagram of the right-shift energy-saving strategy involved in the present invention, showing the schedule modified by the right-shift strategy. Among them, (a) is the original scheduling plan of the right shift strategy, and (b) is the right shift modified schedule. Obviously, the revised plan has a shorter total idle time than the original plan, thus making the TEC smaller.

Reference may be made to FIG. 8 , which is a schematic diagram of the overall flow of the scheduling method of the distributed assembly flow shop according to the present invention. It should be noted that the local enhancement in Figure 8 refers to local search, and the local operations corresponding to the local search can be referred to Figure 6 .

To effectively evaluate the performance of the algorithm, examples are randomly selected from existing datasets. In order to ensure the objectivity of the test results, the maximum completion time of all workpieces processed in each batch of experiments is used as the evaluation index. The smaller the value, the better the scheduling effect. We adopted five widely used scheduling rules (FCFS, STPT, LTPT, SI, LI) to compare with our DRL algorithm, and the experimental results are shown in Table 2. Experimental results show that DRL outperforms scheduling rules in instances of various sizes, and as the problem size increases, DRL gains greater advantages. Furthermore, the trained DRL model solves the problem faster than the compared methods and can quickly generate scheduling solutions for multiple large and small instances.

Table 2

Scale(n,m,F,t) FCFS STPT LTPT SI LI DRL 20,5,2,2 821 848 782 752 954 737 20,5,2,4 1246 1224 1179 1142 1394 1103 20,10,2,4 1682 1867 1703 1607 1947 1476 50,10,2,2 2483 2289 2276 2228 2408 2172 100,5,2,2 3163 3310 3038 3007 3668 2645 100,5,2,4 3647 3602 3685 3467 3965 2987

Further, in order to evaluate the effectiveness of the proposed enhanced algorithm in solving the problem, the DRL algorithm of the present invention was compared with the two algorithms IG and GA. All algorithms are coded by Python3.8 and performed in the same environment. The maximum CPU running time n×m×F×t (seconds) is used as the stopping condition for all experiments. Ten independent experiments were conducted for each test problem, and the optimal results for each problem are shown in bold in Table 3. According to Table 3, we can see that in some small-scale instance cases, IG occasionally presents better results. However, DRL shows better performance on large-scale instances that take longer. The average makespan of each instance obtained through repeated experiments also confirms that DRL has better performance in the stability of the algorithm. Generally speaking, the DRL algorithm outperforms IG and GA on most test problems, which indicates that DRL is an effective algorithm for solving EADFFASP.

table 3

Referring to FIG. 9 , FIG. 9 is a schematic diagram of the terminal structure of the hardware operating environment involved in the embodiment of the present invention.

As shown in Figure 9, the terminal may include: a processor 1001, such as a CPU, a network interface 1004, a user interface 1003, a memory 1005, and a communication bus 1002. Among them, the communication bus 1002 is used to realize connection communication between these components. The user interface 1003 may include a display screen (Display), an input unit such as a keyboard, a mouse, etc. The optional user interface 1003 may also include a standard wired interface or a wireless interface. The network interface 1004 may optionally include a standard wired interface or a wireless interface (such as a WI-FI interface). The memory 1005 may be a high-speed RAM memory or a stable memory (non-volatile memory), such as a disk memory. The memory 1005 may optionally be a storage device independent of the aforementioned processor 1001.

Those skilled in the art can understand that the terminal structure shown in FIG. 9 does not limit the terminal, and may include more or fewer components than shown, or combine certain components, or arrange different components.

As shown in Figure 9, memory 1005, which is a computer storage medium, may include an operating system, a network communication module, a user interface module, and a scheduler for a distributed assembly flow workshop.

In the terminal shown in Figure 9, the network interface 1004 is mainly used to connect to the backend server and communicate with the backend server; the processor 1001 can be used to call the scheduling program of the distributed assembly flow workshop stored in the memory 1005, and execute the following operate:

According to the process parameters of the flexible distributed assembly flow shop, construct a mathematical model for the scheduling problem of the flexible distributed assembly flow shop under energy consumption constraints. The mathematical model includes an objective function and constraints;

Cluster the workpieces based on their processing time and determine the target workpieces corresponding to each factory;

According to the improved DRL algorithm model, determine the processing sequence of the target workpiece corresponding to each of the factories and the maximum completion time of the processing sequence corresponding to each of the factories;

Obtain the production sub-plan of the products to be produced in each of the factories, and determine the assembly sub-plan corresponding to each of the factories according to the production sub-plan;

Determine the objective function value according to the processing sequence of each factory and the assembly sub-plan;

When the number of iterations is not satisfied, continue to execute the step of determining the processing sequence of the target workpiece corresponding to each factory and the maximum completion time of the processing sequence corresponding to each factory according to the improved DRL algorithm model; in When the number of iterations is met, a scheduling plan corresponding to the objective function value that meets the preset conditions is output.

Further, the processor 1001 can call the scheduler of the distributed assembly flow shop stored in the memory 1005, and also perform the following operations:

Model the processing time of each target workpiece in the factory, and convert the processing time encoding of each target workpiece on all machines into a first vector with a fixed dimension;

Model the first vector and convert the encoding into a second vector;

The second vector is input into a decoding network built in advance based on RNN and Attention mechanisms to generate a processing sequence of the target workpiece corresponding to the factory.

Obtain the network model parameters and key factories of the current DRL algorithm model and the target factory with minimized maximum completion time;

The last workpiece in the processing sequence of the key factory is assigned to the target factory, and the network model parameters are used as the initial network model parameters of the DRL algorithm model.

Further, the processor 1001 can call the scheduler of the distributed assembly flow shop stored in the memory 1005, and also perform the following operations:

The insertion neighborhood operation in the key factory randomly selects a key workpiece and inserts the key workpiece in front and behind all non-critical workpieces;

The exchange neighborhood operation in the key factory randomly selects a key workpiece and exchanges it with all other non-critical workpieces;

Randomly selecting a critical workpiece within the critical plant and swapping locations of the critical workpiece with non-critical workpieces within each non-critical plant;

The insertion neighborhood operation between key factories and non-critical factories randomly selects a key workpiece and inserts the key workpiece into the front and back of each non-critical workpiece in each non-critical factory;

Select a product with the largest total processing time on the assembly machine, and then assign the critical workpiece to another randomly selected assembly machine;

Select two adjacent products with the largest makespan difference and then randomly exchange their associated workpieces;

Swap two adjacent products with the largest makespan difference;

A product with the highest energy consumption is selected on the assembly machine and then the critical workpiece is assigned to another randomly selected assembly machine.

Further, the processor 1001 can call the scheduler of the distributed assembly flow shop stored in the memory 1005, and also perform the following operations:

Use the processing time of the workpiece as a clustering criterion to construct a workpiece feature set corresponding to each workpiece;

The workpiece feature set is divided into K clusters through the K-means algorithm, where the value of K is determined based on the sum of squared errors;

Starting from the first cluster, the workpiece is assigned to each factory in sequence as the last workpiece until all workpieces are assigned to each factory, thereby determining the target workpiece corresponding to each factory.

Further, the processor 1001 can call the scheduler of the distributed assembly flow shop stored in the memory 1005, and also perform the following operations:

According to the production sub-plan, determine the relevant work of each of the products to be produced and the completion time of the relevant work of each of the products to be produced;

Sort the completion time of each product to be produced according to non-descending rules to obtain a priority sequence of products to be produced;

According to the order of the priority sequence, each product to be produced is sequentially taken out and assigned to the assembly machine that can complete its assembly operation earliest, thereby determining the assembly sub-plan corresponding to each of the factories.

In addition, in order to achieve the above object, the present invention also provides a terminal device. The terminal device includes: a memory, a processor, and a distributed assembly flow workshop stored on the memory and capable of running on the processor. When the scheduler of the distributed assembly flow shop is executed by the processor, the steps of the scheduling method of the distributed assembly flow shop as described above are implemented.

In addition, in order to achieve the above object, the present invention also provides a computer-readable storage medium. The computer-readable storage medium stores a scheduling program for a distributed assembly flow workshop. The scheduling program for a distributed assembly flow workshop When executed by the processor, the steps of implementing the above-mentioned scheduling method for a distributed assembly flow shop are implemented.

It should be noted that, as used herein, the terms "include", "comprising" or any other variation thereof are intended to cover a non-exclusive inclusion, such that a process, method, article or system that includes a list of elements not only includes those elements, but It also includes other elements not expressly listed or that are inherent to the process, method, article or system. Without further limitation, an element defined by the statement "comprises a..." does not exclude the presence of other identical elements in the process, method, article, or system that includes that element.

The above serial numbers of the embodiments of the present invention are only for description and do not represent the advantages and disadvantages of the embodiments.

Through the above description of the embodiments, those skilled in the art can clearly understand that the methods of the above embodiments can be implemented by means of software plus the necessary general hardware platform. Of course, it can also be implemented by hardware, but in many cases the former is better. implementation. Based on this understanding, the technical solution of the present invention can be embodied in the form of a software product that is essentially or contributes to the existing technology. The computer software product is stored in a storage medium (such as ROM/RAM) as mentioned above. , magnetic disk, optical disk), including several instructions to cause a terminal device (which can be a mobile phone or a computer) to execute the methods described in various embodiments of the present invention.

The above are only preferred embodiments of the present invention, and do not limit the patent scope of the present invention. Any equivalent structure or equivalent process transformation made using the description and drawings of the present invention may be directly or indirectly used in other related technical fields. , are all similarly included in the scope of patent protection of the present invention.

Claims (9)

1. A scheduling method for a distributed assembly flow shop, characterized in that the scheduling method for a distributed assembly flow shop includes: According to the process parameters of the flexible distributed assembly flow shop, construct a mathematical model for the scheduling problem of the flexible distributed assembly flow shop under energy consumption constraints. The mathematical model includes an objective function and constraints; Cluster the workpieces based on their processing time and determine the target workpieces corresponding to each factory; According to the improved DRL algorithm model, determine the processing sequence of the target workpiece corresponding to each of the factories and the maximum completion time of the processing sequence corresponding to each of the factories; Obtain the production sub-plan of the products to be produced in each of the factories, and determine the assembly sub-plan corresponding to each of the factories according to the production sub-plan; Determine the objective function value according to the processing sequence of each factory and the assembly sub-plan; When the number of iterations is not satisfied, continue to execute the step of determining the processing sequence of the target workpiece corresponding to each factory and the maximum completion time of the processing sequence corresponding to each factory according to the improved DRL algorithm model; When the number of iterations is met, a scheduling plan corresponding to the objective function value that meets the preset conditions is output. 2. The method of claim 1, wherein the objective function is: minimizing the maximum completion time and the total energy consumption during the entire manufacturing period; wherein the total energy consumption includes 4 parts: The first part is the energy consumption when the machine is in processing state, the second part is the energy consumption during transportation, the third part is the energy consumption when the machine is in standby, and the fourth part is the energy consumption when the machine is in sequence-related settings; the constraints The conditions are: each job must be assigned to only one factory, each job must be processed in production in an orderly manner, each production machine can only process one job at a time, each product must be processed on only one assembly machine, each Products can only be assembled when all related work has been completed and shipped to the corresponding assembly machines. Each assembly machine can only process one product at a time, and each assembly machine can only process one product at a time. 3. The method of claim 1, wherein the processing sequence of the target workpiece corresponding to each factory and the maximum processing sequence corresponding to each factory are determined according to the improved DRL algorithm model. Completion time steps include: Model the processing time of each target workpiece in the factory, and convert the processing time encoding of each target workpiece on all machines into a first vector with a fixed dimension; Model the first vector and convert the encoding into a second vector; The second vector is input into a decoding network built in advance based on RNN and Attention mechanisms to generate a processing sequence of the target workpiece corresponding to the factory. 4. The method of claim 3, wherein the step of determining the processing sequence of the target workpiece corresponding to each factory and the processing sequence of the target workpiece corresponding to each factory is based on the improved DRL algorithm model. The steps before maximum makespan include: Obtain the network model parameters and key factories of the current DRL algorithm model and the target factory with minimized maximum completion time; The last workpiece in the processing sequence of the key factory is assigned to the target factory, and the network model parameters are used as the initial network model parameters of the DRL algorithm model. 5. The method of claim 4, wherein the DRL algorithm model is trained based on a preset search algorithm; wherein the preset search algorithm includes: The insertion neighborhood operation in the key factory randomly selects a key workpiece and inserts the key workpiece in front and behind all non-critical workpieces; The exchange neighborhood operation in the key factory randomly selects a key workpiece and exchanges it with all other non-critical workpieces; Randomly selecting a critical workpiece within the critical plant and swapping locations of the critical workpiece with non-critical workpieces within each non-critical plant; The insertion neighborhood operation between key factories and non-critical factories randomly selects a key workpiece and inserts the key workpiece into the front and back of each non-critical workpiece in each non-critical factory; Select a product with the largest total processing time on the assembly machine, and then assign the critical workpiece to another randomly selected assembly machine; Select two adjacent products with the largest makespan difference and then randomly exchange their associated workpieces; Swap two adjacent products with the largest makespan difference; A product with the highest energy consumption is selected on the assembly machine and then the critical workpiece is assigned to another randomly selected assembly machine. 6. The method of claim 1, wherein the processing time of the workpiece includes: the average processing time of all processing operations of the workpiece, the processing time of the first processing of the workpiece, the processing time of the last processing of the workpiece, The standard deviation of the processing time of all workpieces; the steps of clustering the workpieces based on the processing time of the workpieces and determining the target workpieces corresponding to each factory include: Use the processing time of the workpiece as a clustering criterion to construct a workpiece feature set corresponding to each workpiece; The workpiece feature set is divided into K clusters through the K-means algorithm, where the value of K is determined based on the sum of squared errors; Starting from the first cluster, the workpiece is assigned to each factory in sequence as the last workpiece until all workpieces are assigned to each factory, thereby determining the target workpiece corresponding to each factory. 7. The method according to claim 1, characterized in that the step of obtaining the production sub-plan of the products to be produced in each of the factories and determining the assembly sub-plan corresponding to each of the factories according to the production sub-plan, include: According to the production sub-plan, determine the relevant work of each of the products to be produced and the completion time of the relevant work of each of the products to be produced; Sort the completion time of each product to be produced according to non-descending rules to obtain a priority sequence of products to be produced; According to the order of the priority sequence, each product to be produced is sequentially taken out and assigned to the assembly machine that can complete its assembly operation earliest, thereby determining the assembly sub-plan corresponding to each of the factories. 8. A terminal device, characterized in that the terminal device includes: a memory, a processor and a scheduler of a distributed assembly flow shop stored on the memory and executable on the processor, the distributed assembly flow workshop When the scheduling program of the distributed assembly flow shop is executed by the processor, the steps of the scheduling method of the distributed assembly flow shop according to any one of claims 1 to 7 are implemented. 9. A computer-readable storage medium, characterized in that the computer-readable storage medium stores a scheduling program for a distributed assembly flow shop. When the scheduler for a distributed assembly flow shop is executed by a processor, the following is implemented: The steps of the scheduling method of a distributed assembly flow shop according to any one of claims 1 to 7.