CN111507523A - An optimization method for cable production scheduling based on reinforcement learning - Google Patents

Abstract

The invention discloses a cable production scheduling optimization method based on reinforcement learning. First, a cable production scheduling optimization model under the constraints of multiple pipelines and complex resources is established. The optimization model aims at minimizing the penalty fee for deadline delay. On the basis, combined with the super-heuristic algorithm framework, the reinforcement learning mechanism is used as the HLH strategy of the super-heuristic algorithm, and according to the characteristics of the cable production scheduling problem, a simple heuristic rule is designed to construct the LLH method set, so as to realize the cable production scheduling problem. The optimization solution of production scheduling problem; the optimization method has low complexity, which can effectively improve the production and management efficiency of the traditional cable industry; it is of great significance for the comprehensive promotion of quality, efficiency, transformation and upgrading of traditional industries.

Description

An optimization method for cable production scheduling based on reinforcement learning

technical field

The invention relates to an optimization method, in particular to a cable production scheduling optimization method based on reinforcement learning.

Background technique

With the continuous improvement of industrial scale and the continuous development of social economy, cable products have been widely used in important industrial fields such as construction, transportation, automobiles, communications, and energy. According to statistics, as early as 2012, the total output value of my country's wire and cable industry has exceeded one trillion, becoming the world's largest wire and cable producer. At the same time, the market competition in the wire and cable industry is becoming increasingly fierce. Enterprises need to reduce their production costs and improve their production, management and service efficiency by reducing inventory, improving equipment utilization, and rationally allocating human resources. Scheduling optimization is the key link to improve the production, management and service efficiency of enterprises. For enterprises, a reasonable production scheduling scheme can not only shorten the product manufacturing cycle, but also effectively improve the work efficiency of personnel, equipment utilization, and reduce energy and material losses. , so as to achieve the purpose of energy saving, emission reduction, cost reduction and economic benefit improvement. Especially with the formation of agile manufacturing ideas and the continuous development of enterprise agile projects, it has become the core idea of production scheduling to attach importance to just-in-time production and realize flexible and efficient allocation of resources to meet the needs of enterprise production and customer service.

Due to the variety of cable products and complex production processes, the modeling and solution of cable production scheduling problems are very challenging. At present, cable manufacturers are still in the stage of relying on manual experience for production scheduling, and there are very few literatures on cable production scheduling. The application number is 201810526733.7 and the title of the invention patent is "An Optimal Scheduling Method for Multi-Type Cable Processing", which discloses an optimal scheduling method for multi-type cable processing, which is used to realize the cable production and processing schedule. However, this invention only considers the situation that all order processes are the same, which is obviously different from the actual production of cable companies.

In addition, as a cross-domain problem solving mode, hyperheuristics manage and manipulate a series of low-level heuristics (LLH) methods through a high-level heuristic (HLH) strategy, dynamically Generating optimal heuristics to solve different problems provides a new way to solve complex and diverse problems. However, the hyperheuristic algorithm has the problem of high computational complexity. One of the main reasons is that the HLH strategy itself needs to spend a lot of time to find the optimal heuristic method. Reducing the algorithm complexity of the HLH strategy can also improve the overall performance of the algorithm. have an important impact.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to provide a cable production scheduling optimization method based on reinforcement learning that is simple and practical, the optimization method has low complexity, and can effectively improve the production and management efficiency of the traditional cable industry.

The invention first establishes a cable production scheduling optimization model under the condition of multi-pipeline and complex resource constraints. The optimization model aims at minimizing the penalty fee for deadline delay. On this basis, combined with the super-heuristic algorithm framework, the reinforcement learning mechanism is used as the According to the HLH strategy of the super-heuristic algorithm, and according to the characteristics of the cable production scheduling problem, a simple heuristic rule is designed to construct the LLH method set, so as to realize the optimal solution to the cable production scheduling problem.

The present invention is achieved through the following technical solutions:

1. A method for optimizing cable production scheduling based on reinforcement learning, the method comprising the following steps:

Step 1. Establish a constrained optimization mathematical model for the cable production scheduling problem;

The raw material copper rod or aluminum rod for cable production is wire and cable production through wire drawing annealing, wire bundle/stranded wire, extrusion, cabling, sheath extrusion, armoring and other process links. The flexibility of the wire after drawing. Equipment in different processes requires corresponding supporting molds to realize the production of a specific type of cable. On a certain machine in a process, the production of different types of products requires switching corresponding molds, and it takes a certain amount of time to switch molds. Cable products will be produced after the process links such as annealing, stranding/stranding, extrusion, cabling, and sheath extrusion are completed. There are m machines in the cable production line, and there are N orders {J ₁ ,J ₂ ,…,J _N } to be produced, and each order J _i (i=1,2,…,N) is based on the cable product The production process requirements of the model correspond to n process sets O _i ={O _i1 ,O _i2 ,...,O _in }; an order contains only one cable product specification, which is set for the process link g (g=1,2 ,...,6) The set of machines produced is M _g , G _gh represents the h-th production specification in the process link g, Gi _g is the production specification corresponding to the order J _i in the process link g, and G' _gh is the production cable specification The corresponding number of mold sets available at G _gh ; produced on the machine M _k ( _k =1,2,...,m), if it is necessary to switch from order Ji to another order _Ji' , and both _Ji and _Ji' The cable specifications corresponding to each order are different, the time required to replace the mold is S _ii′k ; set the start of the process O _ij (i=1,2,...,N; j=1,2,...,n) The time and completion time are B _ij and C _ij respectively; the start time and completion time of the production order J _i on machine k are set as B _i ′ _k and C _i ″ _{k respectively} ; the optimization goal is to minimize the penalty cost of deadline delay , and reasonably arrange the processing equipment and timing of the corresponding processes of different jobs; the objective function of the cable production scheduling problem is:

Among them, D _i is the delivery deadline corresponding to order J _i , C _i is the completion time of order J _i , and _wi is the urgency weight factor of each order in the deadline;

The constraints are as follows:

Among them, constraint (2) specifies that the start time of the next process in the same order J _i must be completed after the previous process is completed; constraint (3) specifies that the process after the machine k is tightened must be in the previous process. Processing can only be started after a process is completed, which considers the time to replace the mold; constraint (5) gives the limit of the number of molds in a certain process in cable production; the cable production scheduling model established in this step also considers multiple Model cable production, different types of mold switching, mold resource constraints, etc., are more in line with the actual situation of enterprise cable production.

Step 2. Initialize the optimization algorithm and reinforcement learning parameters;

2.1. Initialization algorithm parameters: the current number of iterations t, the maximum number of iterations maxT, and the number of periodic iterations T;

2.2. Initialize the reinforcement learning action set: construct the global search operator set Λ={a ₁ ,a ₂ ,…,a _λ } and the domain search operator set Γ={a′ ₁ ,a′ ₂ ,…,a′ _γ }, and use A=Λ∪Γ as the action set, where the Λ operator is based on the crossover operation, and the Γ operator is based on the exchange operation;

2.3. Generate initial solution: randomly generate an initial solution consisting of N order corresponding processes, namely X _t =Ruffled{O ₁ ,O ₂ ,...,O _N }, Ruffled( ) is a random shuffling operation;

Step 3. Randomly select the initial state s _t and a certain action χ _t (χ _t ∈ A) corresponding to the initial state s _t ;

Step 4. Apply χ _t as a search operator to X _t , and run it continuously for T times. In each operation, use the minimum completion time priority as the standard to generate a scheduling scheme. The specific steps are as follows:

4.1. Traverse all machines to determine whether the process O _ij can be processed on the machine. If so, calculate the completion of the process O _ij on each machine on the basis of satisfying the constraints given by formulas (2)-(6). time;

4.2. Select the machine with the smallest completion time as the processing assignment machine of _Oij ;

4.3. Generate the production scheduling plan of the order on the machine, and use the formula (1) to calculate the objective function value F(·);

If the new solution obtained is better, replace the original solution, and calculate the λ value according to formula (7) after T times of running;

Step 5. Select the corresponding state s _t according to the λ value, that is, λ∈{s|s=θ ₁ ,θ ₂ ,θ ₃ }, where θ ₁ =[0.9,1], θ ₂ =[0.5,0.9), θ ₃ = [0, 0.5) is the interval threshold of the state space;

Step 6. Generate a random number r (r∈[0,1]), and obtain the next execution action χ _t based on the reinforcement probability ε calculated by formula (8); when r < ε, select the state s _t corresponding to the highest Q value action; otherwise, randomly select state s _t to operate corresponding to a certain action;

In formula (8), maxT is the maximum number of iterations set;

Step 7: Evaluate the utility of the execution result of the current action χ _t to guide the search direction of the hyperheuristic algorithm, and define the utility value function r _t of the execution action χ _t as:

According to the learning function shown in formula (10), update the Q values of all actions χ′ _t in the action set to which χ _t belongs, and determine the next state according to the state expression mechanism;

In formula (10), Q _t (s _t , χ _t ) represents the Q value of the state s _t corresponding to the action χ _t in the t-th iteration, α is the learning rate, γ is the discount factor, where γ=0.8, α adopts the formula ( 11) Adaptive adjustment is performed in the manner shown;

Step 8. Determine whether t≤maxT is established, if so, go to step 4 to continue execution, otherwise output the optimal scheduling scheme and its corresponding Gantt chart.

The beneficial effect of the invention is that a cable production scheduling model can be established under multi-pipeline and complex resource constraint conditions according to the actual production situation of the cable enterprise, with the optimization goal of minimizing the penalty fee for deadline delay. On this basis, a hyper-heuristic scheduling optimization method based on reinforcement learning is proposed. Under the framework of hyper-heuristic algorithm, a set of LLH methods with global and local search capabilities is designed; under the reinforcement learning mechanism, the set of LLH methods is used as the Action set, dynamically select the corresponding LLH method for single solution iterative optimization. The method adopts a single-column coding and a single-solution iteration scheme, which is simple and practical, and has low algorithm complexity. It can effectively improve the production and management efficiency of the traditional cable industry, and is of great significance for the comprehensive promotion of quality, efficiency, transformation and upgrading of traditional industries.

Description of drawings

For ease of description, the present invention is described in detail by the following specific embodiments and accompanying drawings.

Figure 1 is a schematic diagram of the cable production process.

Figure 2 is a flowchart of the hyperheuristic scheduling optimization algorithm based on reinforcement learning.

Figure 3 is a Gantt chart for scheduling solutions.

Detailed ways

The preferred embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings, so that the advantages and features of the present invention can be more easily understood by those skilled in the art, so that the protection scope of the present invention can be more clearly defined;

The schematic diagram of the production process of cable companies is shown in Figure 1. The copper rods or aluminum rods, the raw materials for cable production, are produced through wire drawing and annealing, bundling/stranding, extrusion, cabling, sheath extrusion, armoring and other processes to achieve wire and cable production. , the annealing link is mainly for the copper rod material to increase the flexibility of the wire after drawing. Equipment in different processes requires corresponding supporting molds to realize the production of a specific type of cable. On a certain machine in a process, the production of different types of products requires switching corresponding molds, and it takes a certain amount of time to switch molds. Cable products will be produced after the process links such as annealing, stranding/stranding, extrusion, cabling, and sheath extrusion are completed. In the cable industry, customer orders usually stipulate a deadline for product delivery, and delayed delivery will lead to increased default costs. Based on the above considerations, the embodiment is described by taking the minimization of the penalty fee for deadline extension as an example.

为订单J_i在工艺环节g上对应的生产规格，G′_gh为生产线缆规格G_gh时相应的可用模具套数；在机器M_k(k＝1,2,…,m)上生产，若需要从订单J_i切换到另一订单J_i′，且J_i和J_i′两个订单对应的线缆规格不同，则所需更换模具的时间为S_ii′k。此外，设定工序O_ij(i＝1,2,…,N；j＝1,2,…,n)的开始时间和完工时间分别为B_ij和C_ij；设定机器k上生产订单J_i的开始时间和完工时间分别为B′_ik和C″_ik；以截止期延期惩罚费用最小化为优化目标，合理安排不同作业相应工序的加工设备和时序。Step 1. Set a total of m machines in the cable production line that can be used for the production of the above process links. There are N orders to be produced {J ₁ ,J ₂ ,...,J _N }, and each order J _i (i=1,2 ,...,N) corresponds to n process sets O _i ={O _i1 ,O _i2 ,...,O _in } according to the production process requirements of its product model. An order contains only one cable product specification, and the set of machines used for the production of process link g (g=1,2,...,6) is set to be Mg , and G _gh represents the hth production specification on process link _g ,

is the production specification corresponding to the order J _i in the process link g, G′ _gh is the corresponding number of available mold sets when producing the cable specification G _gh ; produced on the machine M _k (k=1,2,...,m), if It is necessary to switch from order J _i to another order J _i′ , and the cable specifications corresponding to the two orders J _i and J _i′ are different, then the time required to replace the mold is S _ii′k . In addition, set the start time and finish time of the process O _ij (i=1,2,...,N; j=1,2,...,n) as B _ij and C _ij respectively; set the production order J on the machine k The start time and finish time of _i are B′ _ik and C″ _ik respectively; the optimization goal is to minimize the penalty cost of deadline delay, and the processing equipment and sequence of the corresponding procedures of different operations are reasonably arranged.

Its objective function is:

Among them, D _i is the delivery deadline corresponding to the order J _i , C _i is the completion time of the order J _i , and _wi is the urgency weight factor of each order in the deadline.

The constraints are as follows:

Among them, constraint (2) specifies that the start time of the next process in the same order J _i must be completed after the previous process is completed; constraint (3) specifies that the process after the machine k is tightened must be in the previous process. Processing can only be started after a process is completed, which takes into account the time to replace the mold; constraint (5) specifies the limit on the number of molds in a process in cable production.

The specific application examples of the super-heuristic scheduling optimization algorithm based on reinforcement learning to solve the cable production scheduling problem are as follows:

A given example of a cable production scheduling problem is shown in Table 2. The example contains 7 orders, 34 processes and 10 machines. Each order has a corresponding delivery deadline, and each process has corresponding production specifications and mold quantities. Limits, production time, available machines, and mold switching time between different specifications are shown in Table 3.

Table 1 Examples of cable production scheduling problems

Table 2 Timetable for mold replacement between different specifications

G₁₁ G₁₂ G₂₁ G₂₂ G₃₁ G₃₂ G₄₁ G₄₂ G₅₁ G₅₂ G₆₁ G₆₂ G₁₁ 0 3 - - - - - - - - - - G₁₂ 1 0 - - - - - - - - - - G₂₁ - - 0 4 - - - - - - - - G₂₂ - - 2 0 - - - - - - - - G₃₁ - - - - 0 1 - - - - - - G₃₂ - - - - 2 0 - - - - - - G₄₁ - - - - - - 0 3 - - - - G₄₂ - - - - - - 3 0 - - - - G₅₁ - - - - - - - - 0 1 - - G₅₂ - - - - - - - - 3 0 - - G₆₁ - - - - - - - - - - 0 3 G₆₂ - - - - - - - - - - 6 0

Therefore, N=7, m=10. The specific steps of solving the cable production scheduling problem by the hyperheuristic scheduling optimization algorithm based on reinforcement learning are as follows:

Step 2. Initialize the optimization algorithm and reinforcement learning parameters.

2.1. Initialization algorithm parameters: the current number of iterations t=1, the maximum number of iterations maxT=300, the number of periodic iterations T=3, and all data in the Q value table are initialized to 0;

2.2. Initialize the reinforcement learning action set: construct the global search operator set Λ={a ₁ ,a ₂ ,…,a _λ } and the domain search operator set Γ={a′ ₁ ,a′ ₂ ,…,a′ _γ }, and use A=Λ∪Γ as the action set, where the Λ operator is mainly based on the crossover operation, and the Γ operator is mainly based on the exchange operation;

2.3. Generate initial solution: randomly generate an initial solution composed of 7 orders corresponding to the process, namely X _t =Ruffled{O ₁ ,O ₂ ,...,O ₇ }, Ruffled( ) is a random order shuffling operation.

Step 3. Randomly select the initial state s _t and a certain action χ _t (χ _t ∈ A) corresponding to the initial state s _t ;

Step 4. Apply χ _t as a search operator to X _t , and run it continuously for T times. In each run, if the new solution obtained is better, replace the original solution. After the T times of running, follow formula (7) Calculate the λ value;

Step 5. Select the corresponding state s _t according to the λ value, that is, λ∈{s|s=θ ₁ ,θ ₂ ,θ ₃ }, where θ ₁ =[0.9,1], θ ₂ =[0.5,0.9), θ ₃ = [0, 0.5) is the interval threshold of the state space.

Step 6: Generate a random number r (r∈[0,1]), and obtain the next execution action χ _t based on the reinforcement probability ε calculated by the formula (8). When r<ε, select the state _st corresponding to the action with the highest Q value; otherwise, randomly select the state _st to operate corresponding to a certain action.

In formula (8), maxT is the set maximum number of iterations.

Step 7. Evaluate its utility for the execution result of the current action χ _t to guide the search direction of the hyperheuristic algorithm, the present invention defines the utility value function r _t of the execution action χ _t as:

On this basis, the Q values of all actions χ' _t in the action set to which χ _t belongs are updated according to the learning function shown in formula (10), and the next state is determined according to the state expression mechanism.

In formula (10), Q _t (s _t , χ _t ) represents the Q value of the state s _t corresponding to the action χ _t in the t-th iteration, α is the learning rate, γ is the discount factor, where γ=0.8, α adopts the formula ( 11) Adaptive adjustment is performed in the manner shown.

Step 8. Determine whether t≤maxT is established, if so, go to step 4 to continue execution, otherwise output the optimal scheduling solution X _best . The objective function value obtained in this example is 39, corresponding to the Gantt chart, and the result is shown in Figure 3, where the interval indicated by A is the mold replacement time.

The above are only specific embodiments of the present invention, but the protection scope of the present invention is not limited to this, and any changes or substitutions that are not thought of without creative work should be covered within the protection scope of the present invention; therefore, The protection scope of the present invention should be based on the protection scope defined by the claims.

Claims (5)

1. a cable production scheduling optimization method based on reinforcement learning, is characterized in that, this method comprises the steps: Step 1. Establish a constrained optimization mathematical model for the cable production scheduling problem; There are m machines in the cable production line, and there are N orders {J ₁ ,J ₂ ,…,J _N } to be produced, and each order J _i (i=1,2,…,N) is based on the cable product The production process requirements of the model correspond to n process sets O _i ={O _i1 ,O _i2 ,...,O _in }; an order contains only one cable product specification, which is set for the process link g (g=1,2 ,...,6) The set of machines produced is M _g , where G _gh represents the h-th production specification on the process link g,

is the production specification corresponding to the order J _i in the process link g, G′ _gh is the corresponding number of available mold sets when producing the cable specification G _gh ; produced on the machine M _k (k=1,2,...,m), if It is necessary to switch from order J _i to another order J _i′ , and the cable specifications corresponding to the two orders J _i and J _i′ are different, then the time required to replace the mold is S _ii′k ; set the process O _ij ( i=1,2,...,N; j=1,2,...,n) start time and finish time are B _ij and C _ij respectively; set the start time and finish time of production order J _i on machine k, respectively are B′ _ik and C′ _i′k ; take the minimization of deadline delay penalty costs as the optimization goal, reasonably arrange the processing equipment and timing of the corresponding procedures of different jobs; the objective function of the cable production scheduling problem is:

Among them, D _i is the delivery deadline corresponding to order J _i , C _i is the completion time of order J _i , and _wi is the urgency weight factor of each order in the deadline; The constraints are as follows:

Among them, constraint (2) specifies that the start time of the next process in the same order J _i must be completed after the previous process is completed; constraint (3) specifies that the process after the machine k is tightened must be in the previous process. Processing can only start after a process is completed; Step 2. Initialize the optimization algorithm and reinforcement learning parameters; 2.1. Initialization algorithm parameters: the current number of iterations t, the maximum number of iterations maxT, and the number of periodic iterations T; 2.2. Generate initial solution: randomly generate an initial solution consisting of N order corresponding processes, namely X _t =Ruffled{O ₁ ,O ₂ ,...,O _N }, Ruffled( ) is a random shuffling operation; Step 3. Randomly select the initial state s _t and a certain action χ _t (χ _t ∈ A) corresponding to the initial state s _t ; Step 4. Apply χ _t as a search operator to X _t , and run it continuously for T times. In each operation, use the minimum completion time priority as the standard to generate a scheduling scheme, If the new solution obtained is better, replace the original solution, and calculate the λ value according to formula (7) after T times of running;

Step 5. Select the corresponding state s _t according to the λ value, that is, λ∈{s|s=θ ₁ ,θ ₂ ,θ ₃ }, where θ ₁ =[0.9,1], θ ₂ =[0.5,0.9), θ ₃ = [0, 0.5) is the interval threshold of the state space; Step 6. Generate a random number r (r∈[0,1]), and obtain the next execution action χ _t based on the reinforcement probability ε calculated by formula (8); when r < ε, select the state s _t corresponding to the highest Q value action; otherwise, randomly select state s _t to operate corresponding to a certain action;

In formula (8), maxT is the maximum number of iterations set; Step 7: Evaluate the utility of the execution result of the current action χ _t to guide the search direction of the hyperheuristic algorithm, and define the utility value function r _t of the execution action χ _t as:

According to the learning function shown in formula (10), update the Q values of all actions χ′ _t in the action set to which χ _t belongs, and determine the next state according to the state expression mechanism;

In formula (10), Q _t (s _t , χ _t ) represents the Q value of the state s _t corresponding to the action χ _t in the t-th iteration, α is the learning rate, γ is the discount factor, where γ=0.8, α adopts the formula ( 11) Adaptive adjustment is performed in the manner shown;

Step 8. Determine whether t≤maxT is established, if so, go to step 4 to continue execution, otherwise output the optimal scheduling scheme and its corresponding Gantt chart. 2. The cable production scheduling optimization method according to claim 1, wherein a step is added after step 2.1 and before step 2.2, the step is to initialize the reinforcement learning action set: constructing a global search operator set Λ={ a ₁ ,a ₂ ,…,a _λ } and domain search operator subset Γ={a′ ₁ ,a′ ₂ ,…,a′ _γ }, and take A=Λ∪Γ as the action set, where Λ calculates The neutron is based on the crossover operation, and the Γ neutron is based on the exchange operation. 3. The cable production scheduling optimization method according to claim 1, wherein the specific steps of generating a scheduling scheme described in step 4 are as follows: 4.1. Traverse all machines to determine whether the process O _ij can be processed on the machine. If so, calculate the completion of the process O _ij on each machine on the basis of satisfying the constraints given by formulas (2)-(6). time; 4.2. Select the machine with the smallest completion time as the processing assignment machine of _Oij ; 4.3. Generate the production scheduling plan of the order on the machine, and use the formula (1) to calculate the objective function value F(·). 4. The cable production scheduling optimization method according to claim 3, characterized in that: in step 4.2, if there are different machines with the same minimum completion time, the processing and assigning machines are randomly selected among them. 5. The cable production scheduling optimization method according to claim 1, characterized in that: in step 1, the constraint (3) considers the time to replace the mold; The number of molds is limited.

Images