CN116703641A - Flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning - Google Patents

Abstract

The invention discloses a flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning, and belongs to the technical field of dynamic scheduling. The implementation method of the invention comprises the following steps: defining a workshop state, a workshop scheduling action and a decision rewarding function; taking the total delay time of all workpieces as an optimization target, and constructing a scheduling target optimization problem for scheduling processing machines of the workpieces and AGVs for transporting the workpieces; constructing a neural network for decision making; and solving the scheduling target optimization problem by using a D3QN method, namely calculating the real-time production state of the workshop based on the neural network at the decision time of the workshop, inputting the production state into the trained neural network, outputting the scheduling action of the workshop by the neural network according to the input state, executing the scheduling action and feeding back a reward to the neural network to reduce the total delay of the workshop workpiece, and improving the production efficiency of the workshop. The invention has the advantages of efficiency and performance.

Description

Flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning

Technical Field

The present invention relates to a flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning, belonging to the technical field of dynamic scheduling.

Background Art

The job shop problem is an early and widely studied problem in production scheduling. It can be briefly described as follows: there are a number of workpieces with established process routes in the workshop. Each process in the process route of each workpiece has a corresponding machine tool for processing. It is necessary to determine the processing process and processing sequence of each machine tool to achieve one or more processing goals. The flexible multi-resource workshop scheduling problem is a more general case of the above problems. Compared with the job shop problem, this problem has more multi-resource constraints and fewer machine processing constraints. Multi-resource means that in addition to workpieces and machine tools, transportation resources such as automated guided vehicles (AGVs) must also be considered. Without the constraints of machine processing, there are multiple machine tools available for each process of the workpiece. With the development of flexible workshops, workshop scheduling algorithms are also constantly enriched and expanded.

At present, traditional scheduling methods can be mainly divided into two types, one is the method based on scheduling rules, and the other is the heuristic algorithm. Scheduling rules can be divided into simple scheduling rules and compound rules. Simple scheduling rules include first come first served, shortest processing time priority, shortest delivery time priority and shortest remaining processing time priority, while compound rules are composed of some simple scheduling rules. The rule-based scheduling method selects a workpiece to a machine for processing at each scheduling moment, and selects an AGV to transport the workpiece. The advantage of this method is high real-time performance and rapid response, but the disadvantage of this method is low efficiency and cannot achieve good results in the long run.

Commonly used heuristic algorithms include genetic algorithm (GA), particle swarm optimization (PSO), simulated annealing (SA) and ant colony optimization (ACO). Heuristic algorithms have high search efficiency and can obtain a better solution in a limited time. However, when facing dynamic problems, heuristic scheduling algorithms can only divide dynamic problems into multi-stage static problems, that is, calculate at the initial moment of scheduling to obtain an initial scheduling plan, and calculate the unscheduled resources at the rescheduling moment to obtain the rescheduling plan. This method requires a lot of computing time and has poor real-time performance, making it difficult to apply to multi-resource scheduling problems with changing environmental conditions.

Therefore, it is necessary to find an algorithm that can take into account both responsiveness and optimization effects. In recent years, learning-based methods have gradually been applied to solve this problem. The Q-learning algorithm is a commonly used algorithm. This method stores the Q-function in a table, where the behavior table states are listed as actions, and the elements are the values of the Q-function corresponding to a certain state and action. Then, at the scheduling time, you only need to find the action with the highest value in the current state in the table. However, in actual workshops, the state space of the workshop is very complex. It is not realistic to establish and maintain a table to store the value function. It will not only reduce the efficiency of the algorithm, but also bring many useless states.

Summary of the invention

In order to solve the problem that the existing technology cannot take into account both efficiency and performance, the main purpose of the present invention is to provide a flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning; this method defines the state of the workshop, the scheduling action of the workshop, and the decision-making reward function, and constructs the architecture and learning method of the neural network for decision-making. At the decision moment of the workshop, the real-time production status of the workshop is calculated, and the production status is input into the trained neural network. The neural network outputs the scheduling action of the workshop according to the input status. The method of executing the scheduling action and feeding back the reward to the neural network can achieve the purpose of reducing the total delay of the workshop workpiece and realizing efficient production of the workshop.

The purpose of the present invention is achieved through the following technical solutions.

The flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning disclosed in the present invention comprises the following steps:

Step 1: Taking minimizing the total delay time of workpieces as the optimization goal, a scheduling target optimization problem is constructed to arrange the processing machine set of the process, the processing sequence on each machine, and the AGV for transporting workpieces.

Step 2: Use the D3QN (Dueling Double DQN) method to solve the scheduling target optimization problem constructed in step 1 to obtain a decision result; the decision result includes selecting the workpiece to be processed at the current time, selecting the machine to process the workpiece, and selecting the AGV to transport the workpiece; by executing the decision result, the total delay time of all workpieces is reduced and the production efficiency of the workshop is improved.

Step 2.1, D3QN algorithm has two neural networks, namely Main Q Network and Target QNetwork. The structures of the two networks are the same, both of which are input layer, hidden layer and dual output subnet structure; the input dimension of the input layer is consistent with the dimension of the workshop state; the hidden layer uses one or more fully connected layers; the dual output subnet includes the state value function network Vn and the advantage function network An. The state value function network Vn is responsible for evaluating the value of the state s, and the advantage function network An is responsible for evaluating the relative advantages and disadvantages of each action a in the current state. The final network value output Q is obtained by linear combination of Vn and An:

Among them, ω represents the network parameters of the current dual-output subnet, α and β represent the parameters of the state value network Vn and the advantage function network An respectively, A represents the set of all actions, a'∈A;

Step 2.2, parameter setting: set the relevant parameters of the flexible multi-resource workshop dynamic scheduling problem, including hyperparameters and neural network parameters;

Step 2.3, initialize the number of training episodes = 0, initialize the current time t = 0, and initialize the state of the workshop resources;

Step 2.4: Determine whether the current round is over. If it is over, execute the next round and initialize the time and workshop resource status. Otherwise, continue to execute. The judgment condition for the end of the round is: whether all workpieces have been processed;

Step 2.5, determine whether the current moment is a decision point. The definition of a decision point is: at the current moment, there are new workpieces arriving and workpieces to be processed that have completed the previous process; if it is a decision point, make a decision and proceed to step 2.6; if it is not a decision point, jump to step 2.15;

Step 2.6, calculate the three types of state characteristic values of the current workshop, namely the state of the workpiece that has arrived, the state of the machine, and the state of the AGV; the three types of state characteristic values have a total of 14 states, which are as follows:

(1) Average completion rate of workpieces that have been reached:

f ₁ =mean{jcr}

Workpiece completion rate

Where OP _i is the total number of processes for workpiece Ji _i , and OC _i is the number of completed processes for workpiece Ji _i ;

(2) The standard deviation of the average completion rate of the workpieces has been reached:

f ₂ = std{jcr}

(3) The average process completion rate has been reached:

(4) Average waiting rate of transportation that has arrived at the process

f ₄ =mean{otwr}

Transportation waiting rate of the process

Where wtt _ij is the transportation waiting time of process O _ij , tt _ijr is the transportation time of process O _ij on AGV A _r , O _i ={O _ij |O _i1 ,O _i2 ,...,O _ij } is the process set of workpiece _Ji ;

(5) Average processing waiting rate of the process that has arrived

f ₅ =mean{opwr}

Processing waiting rate of the process

Where wpt _ij is the processing waiting time of process O _ij , pt _ijk is the processing time of process O _ij on machine M _k , and M _ij is the set of machines available for process O _ij ;

(6) Average expected delay rate of workpieces that have arrived at the current process:

f ₆ =mean{cotr}

The expected delay rate of the current process of the workpiece

Where ct _ic is the completion time of process O _ic , dt _ic is the process delivery time of process O _ic , C _i is the delivery time of workpiece Ji _i , O _ic is the process that workpiece Ji _i is currently processing, and at _i is the arrival time of workpiece Ji _i ;

(7) Standard deviation of the average expected delay rate of the arrived workpieces:

f ₇ = std{cotr}

(8) The maximum value of the average expected delay rate of the workpiece has been reached:

f ₈ = max{cotr}

(9) Average machine utilization:

f ₉ =mean{mur}

The machine utilization rate is

Where RT _k is the cumulative working time of machine M _k , and t is the current time;

(10) Standard deviation of the average utilization rate of the machine:

f ₁₀ = std{mur}

(11) Average remaining workload of the machine:

Where rpt _ij is the remaining processing time of process O _ij , x _ijk is used to determine whether process O _ij is processed on machine M _k , and m is the number of machines;

(12) Average utilization rate of AGV:

f ₁₂ =mean{aur}

The utilization rate of AGV is

Where a is the number of AGVs, RT _r is the cumulative working time of AGVA _r ;

(13) Standard deviation of average utilization of AGV:

f ₁₃ = std{aur}

(14) Average remaining task volume of AGV:

Where rtt _ij is the remaining transportation time of process O _ij , and y _ijr is used to determine whether process O _ij is transported on AGVA _r ;

The final workshop state input to the neural network is:

s＝{f ₁ ,f ₂ ,f ₃ ,f ₄ ,f ₅ ,f ₆ ,f ₇ ,f ₈ ,f ₉ ,f ₁₀ ,f ₁₁ ,f ₁₂ ,f ₁₃ ,f ₁₄ }

Step 2.7, make a decision: randomly generate a decimal between 0 and 1. If the decimal is less than or equal to the current exploration rate, a composite scheduling rule will be randomly selected; otherwise, the current workshop status value is input into MainQNetwork for calculation, and the composite scheduling rule with the greatest value is selected;

The composite scheduling rule is generated by arranging and combining three types of scheduling rules to generate a set of composite scheduling rules; each individual composite scheduling rule can directly select the corresponding workpiece, machine and AGV;

The three types of scheduling rules are rules for selecting workpieces to be processed, rules for selecting processing machines, and rules for selecting transport AGVs;

The rules for selecting workpieces to be processed are:

(1) Select the workpiece with the shortest processing time in the current process

Where J _d is the selected workpiece, L _t is the set of workpieces to be scheduled at the current time t, pt _ick is the processing time of process O _ic on machine M _k , M _ic is the set of machines available for process O _ic , and am _ic is the number of machines available for process O _ic ;

(2) Select the workpiece with the longest processing time in the current process

(3) Select the workpiece with the shortest remaining processing time

M _ij is the set of machines available for process O _ij , and am _ij is the number of machines available for process O _ij.

(4) Select the workpiece with the largest remaining processing time

(5) Select the workpiece with the shortest delivery time

Where D _i is the delivery date of workpiece _Ji ;

Rules for selecting processing machines:

(1) Select the machine with the shortest remaining working time among the available machines

Where M _d is the selected machine, mrt _k is the remaining working time of machine M _k ;

(2) Select the machine with the lowest utilization rate among the available machines

(3) Choose the fastest machine among the available machines

Rules for selecting AGV for transporting workpieces:

(1) Select the AGV with the shortest remaining transport time

Where A _d is the selected AGV, art _r is the remaining working time of AGVA _r ;

(2) Select the AGV with the lowest utilization rate

The above five rules for selecting workpieces to be processed, three rules for selecting processing machines, and two rules for selecting AGVs to transport workpieces are used to generate thirty composite scheduling rules through permutations and combinations;

Step 2.8, execute the scheduling rules: select the corresponding workpiece, machine and AGV according to the composite rules decided;

Step 2.9, using the method in step 2.6 to calculate the state characteristic value of the workshop after the scheduling rule is executed;

Step 2.10, calculate the reward: the optimization goal is to minimize the total delay time (Total Delay Time, TDT), so the design of the reward function should ensure that the trend of maximizing the reward is consistent with the optimization trend of the optimization goal. The specific reward function is as follows: if the estimated process completion time of the workpiece selected by the decision is less than the delivery date of the process, the reward is 0; otherwise, the reward is the difference between the estimated process completion time and the delivery date of the workpiece;

_rij = max(0, _{ctij -dtij} )

Where TDT is the total delay, _Ci is the completion time of workpiece _Ji , _Di is the delivery date of workpiece _Ji , r _ij represents the reward obtained from this decision, ct _ij represents the completion time of process O _ij , and dt _ij represents the delivery date of process O _ij ;

Step 2.11: Determine whether the current decision is the last decision of this round. If so, done = 1; otherwise, done = 0;

Step 2.12, store each scheduling experience in the experience pool in the form of (s _t , a _t , s _t+1 , r, done) to provide experience for subsequent neural network learning and training; where s _t represents the workshop state value before the decision, a _t represents the scheduling rule decided, r represents the reward obtained for this decision, s _t+1 represents the workshop state value after the decision result is executed, and done represents whether this step decision is the last step decision;

Step 2.13, experience playback: determine whether the number of experiences stored in the current experience pool is greater than the minimum batch number. If it is greater, randomly select a batch size of experience from the experience pool for neural network training and updating; if it is less than or equal to, do not perform any operation;

Step 2.14: Update the Main Q Network in D3QN: Input the state s _t into the Main Q Network and estimate its Q value. Input the state s _t+1 into the Target Q Network and combine it with the reward value r to get the target value Y. The parameters of the Main Q Network are updated by gradient descent. The parameters of the Target Network are obtained by copying the parameters of the Main Q Network at regular intervals. Therefore, the weights of the Target Q Network are updated every twenty decisions.

Y＝r+γQ ^t (s _t+1 ,argmaxQ(s _t+1 ,a ^m ;ω,α,β);ω ^t ,α ^t ,β ^t )*(1-done)

Where Ε[] ² represents the mean square error, (s _t ,a _t ,s _t+1 ,r,done)~U(B) represents the data extracted from the sample, γ is the discount factor, argmax _a Q(s _t+1 , ^am ;ω,α,β) represents the action a ^m with the greatest value in the next state s _t+1 evaluated by the Main Q Network;

Step 2.15, update the status of the workshop workpiece, machine and AGV, and update the current time to t=t+1;

Step 2.16: Determine whether the number of training times has been reached. If it has been completed, save the parameters of the neural network to obtain the trained neural network; otherwise, jump to step 2.4;

Step 2.17, input the current state of the workshop into the trained neural network obtained in step 2.16 to obtain a decision result; the decision result includes selecting the workpiece to be processed at the current time, selecting the machine to process the workpiece, and selecting the AGV to transport the workpiece; by executing the decision result, the total delay time of all workpieces is reduced and the production efficiency of the workshop is improved.

Beneficial effects:

1. The present invention discloses a method for calculating the real-time production status of a workshop, which designs different status characteristics for the workpieces, machines and AGVs in the workshop. Through these status characteristic values, the production status of the workshop can be quickly grasped, providing support for workshop decision-making.

2. The present invention discloses a set of composite workshop scheduling rules, which generate composite scheduling rules by combining the scheduling rules of single resources. Each individual scheduling rule can be directly used for workshop decision-making to directly select the corresponding workpieces, machines and AGVs. A variety of composite scheduling rules can be selected and used in different situations to improve the flexibility of scheduling.

3. A reward function disclosed by the present invention achieves the purpose of reducing the total delay time of the workpiece by minimizing the delay time of each process.

4. The method for dynamic scheduling of flexible multi-resource workshops based on deep reinforcement learning disclosed in the present invention calculates the state characteristic values of the workshop, inputs the state values of the workshop into the neural network, combines the D3QN algorithm, decides the corresponding composite scheduling rules, executes the scheduling rules and calculates the reward function to obtain rewards to achieve dynamic scheduling of flexible multi-resource workshops, which can reduce the total delay time of workpieces to a certain extent and improve the production efficiency of the workshop.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 shows the D3QN reward curve;

Figure 2 is a flow chart of the flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning disclosed in the present invention.

Specific implementation method

The present invention will be described in detail below with reference to the accompanying drawings and embodiments. The technical problems solved by the technical solution of the present invention and the beneficial effects are also described. It should be noted that the described embodiments are only intended to facilitate the understanding of the present invention and do not have any limiting effect on it.

The flexible job shop scheduling problem of this embodiment is described as follows: There are 10 machines in the workshop for processing workpieces, and 7 automated guided vehicles (AGVs) for performing transportation tasks. There are 60 workpieces in a batch of processing requirements, of which 15 are initial workpieces at the initial moment, and 45 workpieces will arrive in succession in the subsequent period of time. There is a predetermined process route for the processing of each workpiece, and a process route has several processes. These processes need to be completed one at a time in a certain order, and the transportation task of the workpiece needs to be completed by AGV. At the initial moment, the AGV starts from the warehouse, and the initial position of the workpiece is also in the warehouse. As time goes by, the workpieces that arrive later enter the workshop. The arrival time, process route and processing time, optional processing machines and other information of these workpieces cannot be known in advance, but only after the workpiece enters the workshop.

The information of the artifact is shown in the following table:

Table Artifact Information Table

Where dt _ij' is the delivery date of process O _ij' .

Among them, the locations of warehouses and machines are shown in the following table:

Table Workshop Facility Location Table

Based on the location of the workshop facilities, the driving distance and driving time between the facilities can be calculated:

t _kk' =d _kk' =|x _k -x _k' |+|y _k -y _k' |

where t _kk' and d _kk' are the distance and AGV travel time between machine M _k and machine M _k', respectively, and x _k and y _k are the position coordinates of machine M _k .

In the above scheduling problem in the flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning algorithm disclosed by the present invention, in order to distinguish it from other scheduling problems that consider different factors, the following explanation is made:

A. The processing time of the process and the driving time of the AGV are determined;

B. The processing preparation time of the workpiece has been considered in the process processing time, and the loading and unloading time of the workpiece has been considered in the transportation time of the AGV;

C. The processing of workpieces on the machine is continuous and cannot be preempted by other workpieces; the transportation of workpieces on the AGV is also continuous and cannot be preempted by other workpieces;

D. Each machine can only process one workpiece at a time; each AGV can only transport one workpiece at a time;

E. The performance of each AGV is exactly the same. For the same transportation task, any one of the AGVs can be selected to complete it.

F. Each machine and AGV has a buffer large enough to accommodate the workpiece

G. A flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning without considering problems such as machine failure, machine shutdown, AGV power shortage, AGV failure and AGV congestion is characterized by comprising the following steps:

Step 1: Taking minimizing the average tardiness rate (ATR) as the optimization goal, reasonably arrange the processing machine set of the process, the processing sequence on each machine and the AGV for transporting the workpiece, so that the scheduling goal is optimized;

Step 2: Use the D3QN (Dueling Double DQN) method to solve the problem in step 1:

1. The D3QN algorithm has two neural networks, namely Main Q Network and Target Q Network. The structures of these two networks are the same, both of which are input layer, hidden layer and dual output subnet structure. The input dimension of the input layer is consistent with the dimension of the workshop state. The hidden layer uses one or more fully connected layers. The dual output subnet includes the state value function network Vn and the advantage function network An. The state value function network Vn is responsible for evaluating the value of the state s, and the advantage function network An is responsible for evaluating the relative advantages and disadvantages of each action a in the current state. The final network value output Q is obtained by linear combination of Vn and An:

2. Parameter setting: Set the relevant parameters of the problem, including the parameters and hyperparameters of the neural network. D3QN has two neural networks, Main Q Network and Target Q Network. The structures of these two networks are the same. They both use an input layer, three fully connected layers and an output layer. The nodes of each layer of the fully connected layer are set to 256, and the activation function is set to ReLU. In the hyperparameters, the size of the experience pool is set to 4000, the sampling batch is 32, the discount factor is set to 0.99, the initial exploration rate is set to 1, the decay rate of the exploration rate is set to 0.999, the minimum exploration rate is set to 0.04, the learning rate is set to 0.00005, and the number of training times is set to 5000.

3. Initialize the number of training episodes = 0, initialize the current time t = 0, and initialize the status of workshop resources;

4. Determine whether the current round is over. If it is over, execute the next round and initialize the time and workshop resource status, otherwise continue to execute; the judgment condition for the end of the round is: whether all workpieces have been processed;

5. Determine whether the current moment is a decision point. The definition of a decision point is: at the current moment, there are new workpieces arriving and workpieces to be processed that have completed the previous process; if it is a decision point, make a decision and proceed to step 6; if it is not a decision point, jump to step 15;

6. Calculate the three types of state characteristic values of the current workshop, namely the state of the workpiece that has arrived, the state of the machine, and the state of the AGV; there are a total of 14 states of the three types of state characteristic values, which are as follows:

(1) Average completion rate of workpieces that have been reached:

f ₁ =mean{jcr}

Workpiece completion rate

Where OP _i is the total number of processes for workpiece Ji _i , and OC _i is the number of completed processes for workpiece Ji _i ;

(2) The standard deviation of the average completion rate of the workpieces has been reached:

f ₂ = std{jcr}

(3) The average process completion rate has been reached:

(4) Average waiting rate of transportation that has arrived at the process

f ₄ =mean{otwr}

Transportation waiting rate of the process

Where wtt _ij is the transportation waiting time of process O _ij , tt _ijr is the transportation time of process O _ij on AGV A _r , O _i ={O _ij |O _i1 ,O _i2 ,...,O _ij } is the process set of workpiece _Ji ;

(5) Average processing waiting rate of the process that has arrived

f ₅ =mean{opwr}

Processing waiting rate of the process

Where wpt _ij is the processing waiting time of process O _ij , pt _ijk is the processing time of process O _ij on machine M _k , and M _ij is the set of machines available for process O _ij ;

(6) Average expected delay rate of workpieces that have arrived at the current process:

f ₆ =mean{cotr}

The expected delay rate of the current process of the workpiece

Where ct _ic is the completion time of process O _ic , dt _ic is the process delivery time of process O _ic , C _i is the delivery time of workpiece Ji _i , O _ic is the process that workpiece Ji _i is currently processing, and at _i is the arrival time of workpiece Ji _i ;

(7) Standard deviation of the average expected delay rate of the arrived workpieces:

f ₇ = std{cotr}

(8) The maximum value of the average expected delay rate of the workpiece has been reached:

f ₈ = max{cotr}

(9) Average machine utilization:

f ₉ =mean{mur}

The machine utilization rate is

Where RT _k is the cumulative working time of machine M _k , and t is the current time;

(10) Standard deviation of the average utilization rate of the machine:

f ₁₀ = std{mur}

(11) Average remaining workload of the machine:

Where rpt _ij is the remaining processing time of process O _ij , x _ijk is used to determine whether process O _ij is processed on machine M _k , and m is the number of machines;

(12) Average utilization rate of AGV:

f ₁₂ =mean{aur}

The utilization rate of AGV is

Where a is the number of AGVs, RT _r is the cumulative working time of AGVA _r ;

(13) Standard deviation of average utilization of AGV:

f ₁₃ = std{aur}

(14) Average remaining task volume of AGV:

Where rtt _ij is the remaining transportation time of process O _ij , and y _ijr is used to determine whether process O _ij is transported on AGVA _r ;

The final workshop state input to the neural network is:

s＝{f ₁ ,f ₂ ,f ₃ ,f ₄ ,f ₅ ,f ₆ ,f ₇ ,f ₈ ,f ₉ ,f ₁₀ ,f ₁₁ ,f ₁₂ ,f ₁₃ ,f ₁₄ }

7. Make a decision: randomly generate a decimal between 0 and 1. If the decimal is less than or equal to the current exploration rate, a composite scheduling rule will be randomly selected; otherwise, the current workshop status value is input into the Main Q Network for calculation, and the composite scheduling rule with the greatest value is selected;

The composite scheduling rule is generated by arranging and combining three types of scheduling rules to generate a set of composite scheduling rules; each individual composite scheduling rule can directly select the corresponding workpiece, machine and AGV;

The three types of scheduling rules are rules for selecting workpieces to be processed, rules for selecting processing machines, and rules for selecting transport AGVs;

The rules for selecting workpieces to be processed are:

(6) Select the workpiece with the shortest processing time in the current process

Where J _d is the selected workpiece, L _t is the set of workpieces to be scheduled at the current time t, pt _ick is the processing time of process O _ic on machine M _k , M _ic is the set of machines available for process O _ic , and am _ic is the number of machines available for process O _ic ;

(7) Select the workpiece with the longest processing time in the current process

(8) Select the workpiece with the shortest remaining processing time

M _ij is the set of machines available for process O _ij , and am _ij is the number of machines available for process O _ij.

(9) Select the workpiece with the largest remaining processing time

(10) Select the workpiece with the shortest delivery time

Where D _i is the delivery date of workpiece _Ji ;

Rules for selecting processing machines:

(4) Select the machine with the shortest remaining working time among the available machines

Where M _d is the selected machine, mrt _k is the remaining working time of machine M _k ;

(5) Select the machine with the lowest utilization rate among the available machines

(6) Choose the fastest machine among the available machines

Rules for selecting AGV for transporting workpieces:

(3) Select the AGV with the shortest remaining transport time

Where A _d is the selected AGV, art _r is the remaining working time of AGVA _r ;

(4) Select the AGV with the lowest utilization rate

The above five rules for selecting workpieces to be processed, three rules for selecting processing machines, and two rules for selecting AGVs to transport workpieces generate thirty composite scheduling rules through permutations and combinations;

8. Execute scheduling rules: select the corresponding workpiece, machine and AGV through the composite rules decided;

9. Use the method in step 6 to calculate the state characteristic value of the workshop after the scheduling rules are implemented;

10. Calculate rewards: The optimization goal of this paper is to minimize the total delay time (TDT). Therefore, the design of the reward function should ensure that the trend of maximizing the reward is consistent with the optimization trend of the optimization goal. The specific reward function is as follows: if the estimated process completion time of the workpiece selected by the decision is less than the delivery date of the process, the reward is 0; otherwise, the reward is the difference between the estimated process completion time and the delivery date of the workpiece;

_rij = max(0, _{ctij -dtij} )

Where TDT is the total delay, _Ci is the completion time of workpiece _Ji , _Di is the delivery date of workpiece _Ji , r _ij represents the reward obtained from this decision, ct _ij represents the completion time of process O _ij , and dt _ij represents the delivery date of process O _ij ;

11. Determine whether the current decision is the last decision of this round. If so, done = 1; otherwise done = 0;

12. Store each scheduling experience in the experience pool in the form of (s _t , a _t , s _t+1 , r, done) to provide experience for subsequent neural network learning and training; where s _t represents the workshop state value before the decision, a _t represents the scheduling rule decided, r represents the reward obtained for this decision, s _t+1 represents the workshop state value after the decision result is executed, and done represents whether this step of decision is the last step of decision;

13. Experience playback: Determine whether the number of experiences stored in the current experience pool is greater than the minimum batch number. If it is greater, randomly select a batch size of experience from the experience pool for training and updating the neural network; if it is less than or equal to, do not perform any operation;

14. Update the Main Q Network in D3QN: Input the state s _t into the Main Q Network and estimate its Q value. Input the state s _t+1 into the Target Q Network and combine it with the reward value r to get the target value Y. The parameters of the Main Q Network are updated by gradient descent. The parameters of the Target Network are obtained by copying the parameters of the MainQNetwork at regular intervals. Therefore, the weights of the Target Q Network are updated every 20 decisions.

Y＝r+γQ ^t (s _t+1 ,argmaxQ(s _t+1 ,a ^m ;ω,α,β);ω ^t ,α ^t ,β ^t )*(1-done)

Where Ε[] ² represents the mean square error, (s _t ,a _t ,s _t+1 ,r,done)~U(B) represents the data extracted from the sample, γ is the discount factor, argmax _a Q(s _t+1, a ^m ; ω,α,β) represents the action a ^m with the greatest value in the next state s _t+1 evaluated by the Main Q Network;

15. Update the status of workshop workpieces, machines and AGVs, and update the current time to t = t + 1;

16. Determine whether the training times have been reached. If so, save the parameters of the neural network to obtain the trained neural network; otherwise, jump to step 4.

17. Input the current state of the workshop into the trained neural network obtained in step 16 to obtain a decision result; the decision result includes selecting the workpiece to be processed at the current time, selecting the machine to process the workpiece, and selecting the AGV to transport the workpiece; by executing the decision result, the effect of reducing the total delay time is achieved and the production efficiency of the workshop is improved.

Calculation results and analysis:

Under the conditions of the above embodiment, the reward graph obtained by the method proposed in this article is shown in the following figure:

From Figure 1, we can see that the reward curve continues to rise with the increase in the number of training times, and finally converges stably. The effect of the D3QN algorithm is compared with the effects of the thirty composite scheduling rules designed in this paper, as shown in the following table:

Table Algorithm effect comparison table

Analysis from the table shows that in the problem of Example 1, the effect of the D3QN algorithm is improved by about 19% compared with the optimal composite rule. It can be seen that the effect of the D3QN algorithm is significantly improved compared with the composite rule, and the total delay can be effectively reduced. For the flexible multi-resource workshop scheduling problem proposed in Example 1, the D3QN algorithm can take into account both responsiveness and optimization effect.

When analyzing the scheduling of multiple resources such as workpieces, machines and AGVs in a flexible multi-resource job shop, the present invention takes into account process flexibility constraints and dynamic events of emergency insertion, proposes a scheduling method based on deep reinforcement learning, and optimizes the allocation scheme of AGV handling tasks and machine processing tasks. It can converge quickly and the results are relatively stable when solving related problems. It has certain advantages over traditional algorithms, improves production efficiency and reduces total delay.

The specific description above further illustrates the purpose, technical solutions and beneficial effects of the invention in detail. It should be understood that the above description is only a specific embodiment of the present invention and is not intended to limit the scope of protection of the present invention. Any modifications, equivalent substitutions, improvements, etc. made within the spirit and principles of the present invention should be included in the scope of protection of the present invention.

Claims (1)

1. A flexible multi-resource workshop dynamic scheduling method based on deep reinforcement learning, characterized in that: comprising the following steps, Step 1. With the optimization goal of minimizing the total delay time of workpieces, construct a scheduling objective optimization problem, which is used to arrange the set of processing machines for the process, the processing sequence on each machine and the AGV for transporting the workpieces; Step 2, using the D3QN method to solve the scheduling target optimization problem constructed in step 1, and obtain a decision result; the decision result includes selecting the workpiece to be processed at the current time, selecting the machine for processing the workpiece, and selecting the AGV for transporting the workpiece; Execute the decision result, reduce the total delay time of the workpiece, and improve the production efficiency of the workshop; Step 2.1, the D3QN algorithm has two neural networks, namely Main Q Network and Target Q Network. The structures of the two networks are the same, both of which are input layer, hidden layer and double output subnetwork structure; the input dimension of the input layer and The dimension of the workshop state remains consistent; the hidden layer adopts one or more fully connected layers; the dual output subnetwork includes the state value function network Vn and the advantage function network An, the state value function network Vn is responsible for evaluating the value of the state s, and the advantage function The network An is responsible for evaluating the relative advantages and disadvantages of each action a in the current state, and the final value output Q of the network is obtained by the linear combination of Vn and An: Among them, ω represents the network parameters of the current dual-output subnetwork, α and β represent the parameters of the state-value network Vn and the advantage function network An, respectively, and A represents the set of all actions, a'∈A; Step 2.2, parameter setting: set the relevant parameters of the flexible multi-resource workshop dynamic scheduling problem, including hyperparameters and neural network parameters; Step 2.3, initialize the number of training times episode=0, initialize the current time t=0, initialize the state of workshop resources; Step 2.4. Determine whether the current round is over. If it is over, execute the next round and initialize the time and workshop resource status, otherwise continue to execute; the judgment condition for the end of the round is: whether all workpieces have been processed; Step 2.5. Determine whether the current moment is a decision point. The definition of a decision point is: there are new workpieces coming at the current moment and workpieces to be processed that have completed the previous process; if it is a decision point, make a decision and proceed to step 2.6; if not decision point, skip to step 2.15; Step 2.6. Calculate the three types of state eigenvalues of the current workshop, that is, the state of the workpiece that has arrived, the state of the machine, and the state of the AGV; the three types of state eigenvalues have a total of 14 states, as follows: (1) The average completion rate of the workpieces that have been reached: f ₁ = mean{jcr} Workpiece completion rate Among them, OP _i is the total number of processes of workpiece _Ji , and OC _i is the number of completed processes of workpiece _Ji ; (2) The standard deviation of the average completion rate of the workpiece has been reached: f ₂ =std{jcr} (3) The average completion rate of the reached process: (4) The average transportation waiting rate of the already arrived process f ₄ = mean{otwr} Transport waiting rate of process Where wtt _ij is the transportation waiting time of process O _ij , tt _ijr is the transportation time of process O _ij on AGV A _r , O _i ={O _ij |O _i1 ,O _i2 ,...,O _ij } is the workpiece J _i 's process set; (5) The average processing waiting rate of the reached process f ₅ = mean{opwr} Process waiting rate Where wpt _ij is the processing waiting time of process O _ij , pt _ijk is the processing time of process O _ij on machine M _k , and M _ij is the machine set available for process O _ij ; (6) The average estimated delay rate of the workpieces that have arrived: f ₆ = mean{cotr} The estimated delay rate of the current operation of the workpiece Among them, ct _ic is the completion time of process O _ic , dt _ic is the process delivery date of process O _ic , C _i is the delivery date of workpiece J _i , O _ic is the current process of workpiece J _i , and at _i is workpiece J the arrival time of _i ; (7) The standard deviation of the average estimated delay rate of the arrived workpieces: f ₇ =std{cotr} (8) The maximum value of the average projected delay rate of the workpiece has been reached: f ₈ =max{cotr} (9) The average utilization rate of the machine: f ₉ = mean{mur} The utilization rate of the machine is Among them, RT _k is the accumulative working time of machine M _k , and t is the current time; (10) The standard deviation of the average utilization of the machine: f ₁₀ =std{mur} (11) The average remaining tasks of the machine: Where rpt _ij is the remaining processing time of process O _ij , x _ijk is to judge whether process O _ij is processed on machine M _k , and m is the number of machines; (12) Average utilization rate of AGV: f ₁₂ = mean{aur} The utilization rate of AGV is Where a is the number of AGVs, RT _r is the cumulative working time of AGVA _r ; (13) The standard deviation of the average utilization rate of AGV: f ₁₃ =std{aur} (14) The average remaining tasks of AGV: Among them, rtt _ij is the remaining transportation time of process O _ij , and y _ijr is to judge whether process O _ij is transported on AGVA _r ; The final workshop state input to the neural network is: s={f ₁ , f ₂ , f ₃ , f ₄ , f ₅ , f ₆ , f ₇ , f ₈ , f ₉ , f ₁₀ , f ₁₁ , f ₁₂ , f ₁₃ , f ₁₄ } Step 2.7, make a decision: randomly generate a decimal between 0 and 1, if the number is less than or equal to the current exploration rate, a composite scheduling rule will be randomly selected; otherwise, the current workshop state value will be input to the Main Q Network Calculate in and select the composite scheduling rule with the greatest value; The compound dispatching rule generates a set of compound dispatching rules by arranging and combining the three types of dispatching rules; each individual compound dispatching rule can directly select the corresponding workpiece, machine and AGV; The three types of scheduling rules are the rules for selecting workpieces to be processed, the rules for selecting processing machines, and the rules for selecting transport AGVs; The rules for selecting workpieces for processing are as follows: (1) Select the workpiece with the shortest processing time in the current process Among them, J _d is the selected workpiece, L _t is the set of workpieces to be scheduled at the current time t, pt _ick is the processing time of process O _ic on machine M _k , M _ic is the set of machines available for process O _ic , am _ic is the number of machines available for process O _ic ; (2) Select the workpiece with the longest processing time in the current process (3) Select the workpiece with the smallest remaining processing time M _ij is the set of machines available for process O _ij , and am _ij is the number of machines available for process O _ij (4) Select the workpiece with the largest remaining processing time (5) Select the workpiece with the shortest delivery time where D _i is the delivery date of job J _i ; Rules for selecting processing machines: (1) Select the machine with the smallest remaining working time among the available machines Among them, M _d is the selected machine, and mrt _k is the remaining working time of the machine M _k ; (2) Choose the machine with the smallest machine utilization rate among the available machines (3) Choose the fastest processing machine among the available machines Rules for selecting AGV for transporting workpieces: (1) Select the AGV with the smallest remaining transportation time Where A _d is the selected AGV, art _r is the remaining working time of AGVA _r ; (2) Select the AGV with the lowest utilization rate The above five rules for selecting processing workpieces, three rules for selecting processing machines, and two rules for selecting AGVs for transporting workpieces, generate 30 compound scheduling rules by means of permutation and combination; Step 2.8, execute scheduling rules: select the corresponding workpieces, machines and AGVs through the composite rules determined by the decision; Step 2.9, using the method of step 2.6 to calculate the state characteristic value of the workshop after executing the scheduling rule; Step 2.10, calculate the reward: the optimization goal is to minimize the total delay time TDT, so the design of the reward function should ensure that the trend of reward maximization is consistent with the optimization trend of the optimization goal. The specific reward function is as follows: If the estimated process completion time is less than the delivery date of the process, the reward is 0; otherwise, the reward is the difference between the estimated process completion time and the delivery date of the workpiece; r _ij ＝max(0,ct _ij -dt _ij ) Among them, TDT is the total delay, C _i is the completion time of workpiece _Ji , D _i is the delivery date of workpiece _Ji , r _ij represents the reward obtained by this decision, ct _ij represents the completion of process O _ij Time, dt _ij represents the delivery date of process O _ij ; Step 2.11. Determine whether the current decision is the last decision of the round, if yes, done=1; otherwise done=0; Step 2.12, store each scheduling experience in the form of (st _t , a _t , _st+1 , r, done) in the experience pool to provide experience for the subsequent learning and training of the neural network; where _st represents the The meaning is the status value of the workshop before the decision, a _t represents the dispatching rule made by the decision, r represents the reward obtained by this decision, st ₊₁ represents the status value of the workshop after the execution of the decision result, and done represents the Whether the decision-making step is the last decision-making step; Step 2.13, experience playback: judge whether the number of experiences stored in the current experience pool is greater than the minimum Batch number, if greater, then randomly select a Batch-sized experience from the experience pool for training and updating of the neural network; if less than or equals, do nothing; Step 2.14, update the Main Q Network in D3QN: input the state s _t into the Main Q Network and estimate its Q value, input the state s _t+1 into the Target Q Network and combine the reward value r to get the target value Y, Main Q Network The parameters of the are updated by gradient descent; the parameters of the Target Network are obtained by copying the parameters of the MainQNetwork at a certain interval; therefore, the weights of the Target Q Network are updated every 20 times of decision-making; Y=r+γQ ^t (s _t+1 ,argmaxQ(s _t+1 ,a ^m ;ω,α,β);ω ^t ,α ^t ,β ^t )*(1-done) Among them, Ε[] ² represents the mean square error, (st _t ,a _t ,st _t+1 ,r,done)~U(B) represent the data extracted from the sample, γ is the discount factor, argmax _a Q(s _t+1 , a ^m ; ω, α, β) represents the action a ^m with the greatest value under the evaluation of the next state s _t+1 by the Main Q Network; Step 2.15, update the status of the workshop workpiece, machine and AGV, and update the current time as t=t+1; Step 2.16, judge whether the number of training times has been reached, if it has been completed, save the parameters of the neural network, and obtain the trained neural network; otherwise, skip to step 2.4; Step 2.17, input the current state of the workshop to the trained neural network obtained in step 2.16, and obtain the decision result; the decision result includes selecting the workpiece to be processed at the current time, selecting the machine for processing the workpiece and selecting the AGV for transporting the workpiece; By implementing the results of this decision, the total delay time of all workpieces is reduced and the production efficiency of the shop floor is improved.