CN112016801A - Flexible job shop scheduling method and system with transfer and switching time - Google Patents

Abstract

The invention discloses a flexible job shop scheduling method and system with transmission and switching time, comprising: acquiring parameters of the flexible job shop, the parameters including: the number of machine tools, the number of workpieces, the processing procedure corresponding to each workpiece, the The processing time on the machine tool, the transmission time between the machine tools and the switching time between the workpieces; based on the parameters of the flexible job shop, a flexible job shop scheduling model is constructed, and the flexible job shop scheduling model includes: objective functions and constraints; Based on the improved empire competition algorithm, the flexible job shop scheduling model is solved. In the solution process, it is assumed that a country represents a set of feasible solutions for the flexible job shop scheduling problem; the solution finally outputs the flexible job shop scheduling scheme.

Description

Flexible job shop scheduling method and system with transfer and switching time

technical field

The present application relates to the technical field of production scheduling, in particular to a flexible job shop scheduling method and system with transmission and switching time.

Background technique

The statements in this section merely mention the background art related to the present application and do not necessarily constitute prior art.

Production scheduling is an important part of manufacturing systems and has received much attention in recent years. One of the most difficult problems in this field is the Job Shop Scheduling Problem (JSP), which is the processing of a set of jobs on a set of machine tools. Each job consists of a set of operations and sequences of operations on different machine tools, and each operation is characterized by the required machine tool and the required processing time. A fork of classic JSP is called FJSP, which is closer to the actual production situation.

FJSP is an important research topic in the field of combinatorial optimization and production management. FJSP consists of two sub-problems, the first sub-problem is to assign a sequence of available machine tools to a specified operation, and the second sub-problem is to calculate the completion time of a sequence of operations assigned to a specified machine tool. While it only takes one more step than JSP to assign a range of optional machines to a given process, FJSP still needs considerable improvement to address its individual encoding, decoding, crossover, and mutation problems. So it's much harder to solve the problem with FJSP. Kacem proposes two new methods: a localized approach (AL) and an evolutionary approach controlled by an assignment model to jointly solve assignments and FJSP. By mixing local and global searches reasonably, Xia and Wu proposed a hybrid method for solving multi-objective FJSP problems. For the FJSP problem with sorting flexibility, Vital-Soto et al. proposed a mixed integer linear programming (MILP) formulation that minimizes weighted delays.

Ahmadi et al. used two evolutionary algorithms, a new non-dominated sorting genetic algorithm (NSGA-II) and a non-dominated sorting genetic algorithm (NRGA), to solve the stable scheduling problem of multi-objective FJSP with random machine failures. To solve the FJSP, Singh and Mahapatra used a quantum behavioral particle swarm algorithm (QPSO) with advanced global search capabilities. Gao et al. adopted a two-stage artificial bee colony algorithm (TABC) and improved it to solve the FJSP problem with fuzzy processing time and new job insertion constraints. Gao et al. studied an efficient discrete harmonic search (DHS) algorithm for solving the FJSP problem. Brandimarte et al. proposed a hierarchical FJSP algorithm based on the tabu search meta-heuristic. Pezzella et al. proposed a Genetic Algorithm (GA) for solving the FJSP problem, which integrates different strategies for initial population generation, selection of individuals, and breeding of new individuals. Xing et al. and Bagheri et al. proposed a knowledge-based ant colony optimization algorithm (KBACO) and an ensemble-based artificial immune algorithm (AIA), respectively. Yuan et al. proposed a hybrid differential evolution (HDE) algorithm for solving the FJSP problem. Gao et al. used the variable neighborhood search (VNS) algorithm to solve this problem. Moslehi et al. proposed a hybrid algorithm based on particle swarm optimization and local search algorithm to solve the multi-objective FJSP problem. Sun et al. proposed an efficient hybrid cooperative co-evolutionary algorithm (HCEA) for the fuzzy FJSP problem.

The inventor found that the technical problems existing in the prior art are: the workpiece processing plan is disconnected from the actual production scheduling, and the flexible job shop scheduling problem is not solved.

SUMMARY OF THE INVENTION

In order to solve the deficiencies of the prior art, the present application provides a flexible job shop scheduling method and system with transmission and switching time;

In a first aspect, the present application provides a flexible job shop scheduling method with transmission and switching time;

Flexible job shop scheduling method with transfer and switching times, including:

Obtain the parameters of the flexible job shop, the parameters include: the number of machine tools, the number of workpieces, the processing procedure corresponding to each workpiece, the processing time of the workpiece on the machine tool, the transmission time between the machine tools and the switching time between the workpieces;

Based on the parameters of the flexible job shop, a flexible job shop scheduling model is constructed, and the flexible job shop scheduling model includes: an objective function and constraints;

Based on the improved empire competition algorithm, the flexible job shop scheduling model is solved. In the solution process, it is assumed that a country represents a set of feasible solutions for the flexible job shop scheduling problem; the solution finally outputs the flexible job shop scheduling scheme.

In a second aspect, the present application provides a flexible job shop scheduling system with transmission and switching times;

Flexible job shop scheduling system with transfer and switching times, including:

an acquisition module, which is configured to: acquire parameters of the flexible job shop, the parameters include: the number of machine tools, the number of workpieces, the processing procedure corresponding to each workpiece, the processing time of the workpiece on the machine tool, and the transmission time between the machine tools and the switching time between the workpiece;

a model building module configured to: construct a flexible job shop scheduling model based on the parameters of the flexible job shop, the flexible job shop scheduling model including: an objective function and constraints;

The output module is configured to: solve the flexible job shop scheduling model based on the improved empire competition algorithm, assuming that a country represents a feasible scheme of the flexible job shop scheduling problem during the solving process; the solution finally outputs the flexible job shop scheduling scheme .

In a third aspect, the present application also provides an electronic device, comprising: one or more processors, one or more memories, and one or more computer programs; wherein the processor is connected to the memory, and one or more of the above The computer program is stored in the memory, and when the electronic device runs, the processor executes one or more computer programs stored in the memory, so that the electronic device performs the method described in the first aspect above.

In a fourth aspect, the present application further provides a computer-readable storage medium for storing computer instructions, and when the computer instructions are executed by a processor, the method described in the first aspect is completed.

In a fifth aspect, the present application also provides a computer program (product), including a computer program, which when run on one or more processors, is used to implement the method of any one of the foregoing first aspects.

Compared with the prior art, the beneficial effects of the present application are:

In this application, the simulated annealing algorithm and the distribution estimation algorithm are embedded into the empire competition algorithm to form a hybrid empire competition algorithm, and the hybrid empire competition algorithm is applied to the flexible job shop scheduling problem to solve the flexible job shop scheduling scheme to quickly find the optimal solution. technical problems, improve the efficiency of flexible workshop scheduling, and shorten the completion time.

Description of drawings

The accompanying drawings that form a part of the present application are used to provide further understanding of the present application, and the schematic embodiments and descriptions of the present application are used to explain the present application and do not constitute improper limitations on the present application.

Fig. 1 is the FJSP schematic diagram of the first embodiment of the application;

FIG. 2 is an algorithm flowchart of Embodiment 1 of the present application;

3 is a schematic representation of the solution of Embodiment 1 of the present application;

4(a)-FIG. 4(b) are schematic diagrams of the mutation process of Example 1 of the application;

5(a)-FIG. 5(b) are schematic diagrams of the assimilation process of Example 1 of the application;

6 is a schematic diagram of the imperial invasion of Embodiment 1 of the application;

7(a)-FIG. 7(d) are schematic diagrams of the neighborhood structure of Embodiment 1 of the present application;

FIG. 8(a)-FIG. 8(d) are schematic diagrams showing the main influence of the parameters of the first embodiment of the application;

Figure 9 (a)-Figure 9 (d) are schematic diagrams of variance analysis results of HICA and HICA variants of Example 1 of the application;

Fig. 10(a)-Fig. 10(d) are schematic diagrams showing the comparison of the convergence of HICA and HICA variants of Example 1 of the application;

Fig. 11(a)-Fig. 11(c) are schematic diagrams of the variance analysis results used to compare various algorithms in Example 1 of the present application;

FIG. 12(a)-FIG. 12(d) are schematic diagrams showing the comparison of the convergence between the HICA algorithm of Embodiment 1 of the present application and other algorithms;

FIG. 13 is a schematic diagram of a Gantt chart of the solution of Embodiment 1 of the present application.

Detailed ways

It should be noted that the following detailed description is exemplary and intended to provide further explanation of the application. Unless otherwise specified, all technical and scientific terms used in the examples of this application have the same meaning as commonly understood by one of ordinary skill in the art to which this application belongs.

It should be noted that the terminology used herein is for the purpose of describing specific embodiments only, and is not intended to limit the exemplary embodiments according to the present application. As used herein, unless the context clearly dictates otherwise, the singular is intended to include the plural as well, furthermore, it is to be understood that the terms "including" and "having" and any conjugations thereof are intended to cover the non-exclusive A process, method, system, product or device comprising, for example, a series of steps or units is not necessarily limited to those steps or units expressly listed, but may include those steps or units not expressly listed or for such processes, methods, Other steps or units inherent to the product or equipment.

Embodiments of the invention and features of the embodiments may be combined with each other without conflict.

Terminology Explanation:

SA, simulated annealing algorithm;

EDA, distribution estimation algorithm;

HICA, Hybrid Empire Competition Algorithm;

Example 1

The present embodiment provides a flexible job shop scheduling method with transmission and switching time;

Flexible job shop scheduling method with transfer and switching times, including:

S101: Acquire parameters of the flexible job shop, the parameters include: the number of machine tools, the number of workpieces, the processing procedure corresponding to each workpiece, the processing time of the workpieces on the machine tools, the transmission time between machine tools, and the switching between workpieces time;

S102: Build a flexible job shop scheduling model based on the parameters of the flexible job shop, where the flexible job shop scheduling model includes: an objective function and constraints;

S103: Based on the improved empire competition algorithm, the flexible job shop scheduling model is solved. In the solution process, it is assumed that a country represents a feasible scheme of the flexible job shop scheduling problem; the solution finally outputs the flexible job shop scheduling scheme.

It should be understood that in S101, the machine tools include: metal cutting machine tools, forging machine tools, woodworking machine tools, and the like.

Workpiece refers to: the processing object in machining. It can be a single part or a combination of several parts fixed together.

The processing procedure corresponding to each workpiece refers to the synthesis of continuous production activities performed by a machine tool on a workpiece in a work place, and is the basic unit that constitutes the production process. According to the different nature and tasks, it can be divided into technological process, inspection process, transportation process, etc. An operation is the processing sequence of a job.

Transfer time between machine tools refers to the time it takes for a workpiece to be transported from one machine tool to another.

The switching time between workpieces refers to the time it takes for a machine tool to switch from the processing of one workpiece to the processing of another workpiece.

As one or more embodiments, the S102: construct a flexible job shop scheduling model based on the parameters of the flexible job shop, where the flexible job shop scheduling model includes: an objective function and constraints;

Among them, the objective function specifically refers to:

Minimize the maximum completion time: min C _max

C _max represents a continuous variable of the maximum make-time of the workpiece.

Among them, the constraints specifically refer to:

There is a set of jobs J={J ₁ ,...,J _n } and a set of machine tools M={M ₁ ,...,M _m } that process workpieces in parallel;

Jobs are available and ready at the initial moment;

Each operation can only be processed on one machine at a time;

Once the machine tool starts to execute the task, it cannot be interrupted until the task is completed;

The storage buffer capacity of each machine tool is greater than the set threshold;

Preemption is unavailable, that is, subsequent operations must wait for the preceding operations to complete;

Consider transit time and switchover time;

Determine the machine selected for each operation, and the sequence of operations on each machine, to minimize make-ready time.

Further, the transportation time refers to the transportation time required for a job to be moved from one machine tool to another machine tool;

Further, the transportation time further includes: inputting the transportation time between the warehouse and the first machine tool. Define a virtual machine with zero machining time.

Further, the switching time refers to the time for switching from executing one job to executing another job on the same machine tool.

As one or more embodiments, the improved empire competition algorithm is obtained by embedding the simulated annealing algorithm SA and the distribution estimation algorithm EDA into the empire competition algorithm.

As one or more embodiments, in S103, based on the improved empire competition algorithm, the flexible job shop scheduling model is solved, and in the solution process, it is assumed that one country represents a feasible solution for a group of flexible job shop scheduling problems; the final output of the solution is obtained. Flexible job shop scheduling scheme; specific steps include:

S1031: Set the parameters of the empire competition algorithm to solve the flexible shop scheduling problem;

S1032: Generate initial population, empire initialization, assuming that a country represents a set of solutions to a flexible job shop scheduling problem; each solution consists of two parts, the machine selection sequence (the available machines selected when the job is processed; the machine selection sequence , which stores the number of available machine tools selected by the job) and operation sequence (sequence of job processing; operation sequence, which stores the workpiece number);

S1033: mutation operation: mutate the solution to increase the diversity of the solution;

S1034: Determine whether the number of countries is greater than the set threshold. If it is greater than the set threshold, change the assimilation strategy to judge whether good colonies are obtained. If good colonies are obtained, use simulated annealing algorithm to solve the problem; if no good colonies are obtained , use the distributed estimation algorithm to solve; if it is less than or equal to the set threshold, execute the assimilation strategy and enter S1035;

S1035: Imperial Invasion;

S1036: Empire Update;

S1037: Empire Destruction;

S1038: Determine whether the termination condition is reached, if yes, end, and output the flexible job shop scheduling plan; if not, return to S1034.

As one or more embodiments, in the S1031, parameters for solving the flexible shop floor scheduling problem by the empire competition algorithm are set; the specific parameters include:

The number of imperialist countries, the number of colonial countries, the number of iterations and the proportion of colonies.

Further, in the S1032, generating an initial population specifically refers to:

Determine the number of jobs, the number of machines, and the sequence of operations in a flexible job shop scheduling problem.

Further, in the S1032, the initialization of the empire specifically refers to:

An empire consists of imperialist countries and their colonies;

According to the strength of the imperialist countries, imperialist countries are allocated colonies of imperialist countries, each imperialist country and its colonies constitute an empire.

Further, in the S1033, the mutation operation specifically refers to: performing mutation on the solution according to the mutation probability to increase the diversity of the solution.

The probability formula for mutation is as follows:

where η is the mutation probability of the individual, F is the fitness of the individual, _Favg is the fitness of the average individual, and _Fmin is the fitness of the worst individual.

It should be understood that mutation is a strategy adopted by imperialist countries to reduce duplication and increase diversity. Different individuals may have different mutation probabilities.

The better the individual fitness, the greater the mutation probability, which expands the individual search space, avoids premature convergence, and the poor individuals have a lower probability of mutation, and better individuals can be obtained through mutation. During the mutation process, for the machine tool selection part, random replacement of available machine tools can be realized. For the operation sequence part, use the swap operation to achieve.

Further, in the S1034, the assimilation strategy refers to the process of the imperialist country making the colonies move closer to itself, that is, the process of optimizing the poor solution in the flexible shop floor scheduling problem.

For empire i, choose a strategy at random:

First select all colonies in empire i to assimilate;

The second is to randomly select colonies in Empire i for the assimilation strategy;

For the colonies of the rest of the empire, assimilate by learning from any other imperialist country.

In the assimilation process, for the machine tool selection part, a two-point crossover strategy is used to randomly select two points of the imperialist country, the elements between the two points are inserted into the corresponding positions of the new colony, and the rest are inserted into the old colony elements.

During the assimilation process, for the part of the operation sequence (the order in which the jobs are processed; the workpiece number is stored in the operation sequence), the POX crossover strategy is adopted, and the jobs are randomly selected, and the jobs selected from the imperialist countries are inserted into the new colonies, while The remaining jobs are inserted into the new colony based on the location of the old colony.

The assimilation strategy produces a new solution, usually implemented in the same way (implementing the same strategy for all nations to assimilate). In the embodiment of the present application, the diversification operation of the assimilation strategy is used.

Further, in the S1034, changing the assimilation strategy means: for empire j, randomly select a strategy:

First select all colonies in empire j for assimilation;

The second is to randomly select colonies in empire j for the assimilation strategy;

For the colonies of the rest of the empire, assimilate by learning from any other imperialist country.

Further, in the S1034, judging whether to obtain a better colony specifically refers to:

In the flexible shop floor scheduling problem, the less time it takes for the current solution to complete the job, the better the colony is.

Further, in the S1034, the simulated annealing algorithm is used to solve the problem, which specifically includes:

Create new solutions for the simulated annealing algorithm by constructing four neighborhood structures to improve the optimal solution.

Further, in the S1034, the simulated annealing algorithm is used to solve the problem, and the detailed steps include:

Using four neighborhood structures N1, N2, N3, N4 to improve the solution in the simulated annealing algorithm;

Neighborhood structure N1 is done by replacing randomly selected position elements of machine tool selection parts;

The neighborhood structure N2 acts on the operation sequence (the order of job processing; the workpiece number is stored in the operation sequence), and the operation sequence part is realized by randomly selecting two job numbers and exchanging the two job numbers;

The neighborhood structure N3 is completed by randomly selecting two positions r ₁ and r ₂ in the machine tool selection part, where r ₁ <r ₂ , and inserting the element at r ₂ at the position before r ₁ ;

Neighborhood structure N4 generates new solutions by executing an exchange structure twice in the sequence of operations part.

Further, in the S1034, using a distributed estimation algorithm to solve, specifically includes:

Two different probabilistic models are embedded in the distributed estimation algorithm to optimize the inferior solution.

Further, in the S1034, a distributed estimation algorithm is used to solve the problem, and the detailed steps include:

Two probability matrices P1 and P2 are designed for the machine selection part and the operation sequence part.

The element M _j,q,i (L) of the probability matrix P1 of the machine selection part represents the probability of processing the operation O _j,q on machine i in the L generation. m _j,q represents the available machine tool array for the qth operation of job j.

The probability matrix P1 is initialized as follows:

Element H _j,f (L) of the probability matrix P2 of the operation sequence part represents the probability of job j appearing at position f of the P2 matrix in the Lth generation. Q represents the total number of all operations in the operation sequence part. Initializing the probability matrix P2 to H _j,f (0)=1/q ensures uniform sampling of the entire solution space.

Then, the probability matrices P1 and P2 are updated by the following formulas.

M _j,q,i (L+1)=(1-θ)M _j,q,i (L)

H _j,f (L+1)=(1-τ)H _j,f (L)

where θ, τ∈(0, 1) are the learning rates of P1 and P2, respectively;

Then sampling through the probability models P1 and P2 to generate new individuals.

Further, the S1035: Imperial Invasion; specifically includes:

The power of each empire is constantly changing, when the power of the empire reaches a set level, it starts to implement an invasion strategy against the weak and small empires, that is, the strong empire occupies the colonies of the weak and small empires. Strong empires occupy colonies of weaker empires, and the occupied colonies become colonies of stronger empires.

In order to gain more powerful rights, some empires may experience the phenomenon of imperial invasion, that is, when the empire's power reaches a set level, it starts to invade the weak and small empires, and when the powerful empire occupies the colonies of the weak and small empires, the invasion is successful. to change the power of the empire.

Further, the S1036: Empire Update; specifically includes:

First, in each empire, colonies may gain more rights than their imperialist state, at which point the most powerful colony becomes the new imperialist state. Colonies under the rule of the old imperialism were placed under the ownership of the new imperialism, and the old imperialist countries became colonies of the new imperialism. Then, the worst empire's colonies are updated by implementing a distributed estimation algorithm.

Further, the S1037: Empire Destruction; specifically includes:

In the empire, the colonies under imperialism no longer exist. Implement the strategy of empire demise and imperialism will be assigned to other empires to become colonies.

Further, the S1038: determine whether a termination condition is reached, and the termination condition here refers to whether the optimization of all flexible shop floor scheduling solutions is completed.

The algorithm parameters were calibrated by Taguchi method. The adopted location-based mathematical model was validated by CPLEX. To verify the effectiveness of the strategy, three variants of HICA are constructed. The content in HICA1 does not contain the SA strategy, but the rest of the content is still consistent with HICA. The difference between HICA2 and HICA is the removal of EDA from HICA. HICA3 shares similarities with HICA, except for the imperial aggression strategy. The parameters have been set, and the operating environment is the same as HICA. Each computing example is run independently for 30 times, and the effectiveness of the algorithm strategy is verified by experimental data. In order to further test the performance of the proposed algorithm, the embodiments of this application compare the HICA algorithm with other currently popular algorithms, including ICA, Improved Genetic Algorithm (IGA), Distribution Estimation Algorithm (EDA), Artificial Immune Algorithm (AIA) , to verify the effectiveness of the proposed algorithm.

Considering the above considerations, the embodiment of the present application adopts a hybrid algorithm named HICA for FJSP. The main contributions are as follows: (1) SA and EDA are embedded ICA based on solution quality; (2) A new empire invasion strategy ICA is introduced to change the power of empire. (3) Four neighborhood structures are proposed to construct new solutions for SA, and different probabilistic models are applied to EDA; (4) Each solution consists of two parts containing different information; (5) The transit time and establishment The two realistic constraints of time bring the studied problem closer to reality.

Aiming at a meta-heuristic knowledge fusion method to solve the flexible workshop scheduling problem with transit and switching time, based on the knowledge fusion meta-heuristic algorithm, considering the FJSP problem with transit time and setting time constraints, a hybrid method is proposed. The Imperial Competition Algorithm HICA, in which the Imperial Competition Algorithm (ICA) is used as the backbone, the Simulated Annealing (SA) algorithm and the Distribution Estimation Algorithm (EDA) are used to improve the quality of the solution. The goal is to minimize the maximum makepan. First, each solution consists of two parts, the machine selection and the sequence of operations, which contain different information. Then, a new strategy of Imperial Invasion was adopted in the ICA to change the power of the Empire. Four neighborhood structures are constructed to create new solutions for SA to improve the optimal solution, and two different probabilistic models are embedded in EDA to optimize the inferior solution. Finally, the operators and parameters of the algorithm are calibrated using Taguchi method. The adopted location-based mathematical model was validated by CPLEX. The algorithm is tested on a large-scale randomly generated benchmark instance set, and it is verified that the algorithm can solve the considered problems well.

Flexible shop floor scheduling optimization problem description with transfer and switching time:

In FJSP, there is a set of jobs and a set of machine tools. Each independent job consists of O _i operations, each of which can be processed in a certain order on a set of available machine tools. The operation of one job moving another machine tool requires transit time, and when the front and rear jobs on the machine tool are inconsistent, switching time between the two jobs is required. Considering the transit time between the input warehouse and the first machine tool, a virtual machine with zero processing time, such as machine 0, is defined. Embodiments of the present application require simultaneous determination of the machine tool selection for each operation and the sequence of operations on each machine tool to minimize the completion time. Figure 1 is a schematic diagram of the FJSP currently studied. In the proposed model, the following assumptions are made:

· All jobs are available and ready at time zero.

·Each operation can only be processed on one machine at a time.

·Once the machine tool starts to execute the task, it cannot be interrupted until the task is completed.

·The storage buffer capacity of each machine tool is large enough.

Preemption is not available, that is, subsequent operations must wait for the preceding operations to complete.

·Transport time and switching time are considered.

1.1 Modeling of the optimization problem of flexible shop floor scheduling with transmission and switching time

The parameters and symbols are represented as follows:

index:

j,w The index of the job.

i,k,t The index of the machine.

The index of the f,s position.

The index of the q,g operation.

n Number of jobs.

m Number of machines.

parameter:

n _j operands for job j.

O _j,q The qth operation of job j.

P _j,q,i O _j,q processing time on machine i.

T _j,k,i The transport time of workpiece j from machine k to machine i.

E _j,q,i is a binary variable that is 1 if O _j,q can be processed at machine i, and 0 otherwise.

S _i,w,j switching time between w and j for i job on machine tool.

The number of operands that R _i can process on machine i.

The completion time of C _j,q O _j,q .

M is a large positive number.

Decision variables:

Wi _,w,j is a binary variable that takes the value 1 if there is a switching time between job j on machine i and job w; otherwise takes the value 0.

X _j,q,i,f,k A binary variable that takes the value 1 if the job j is processed on machine k and the next operation O _j,q is processed at position f of machine k; otherwise, it takes the value 0.

The objective function is to minimize makepan.

Constraints (1) and (2) ensure that each operation selects a selected location of the available machine tool for processing.

Constraint (3) forces each position of the machine to be occupied once.

Constraints (4) and (5) guarantee that each operation of each job should operate on its own qualified machine tool.

Constraints (6) and (7) specify the machine tool used for the job operation.

Constraints (8) and (9) are logical priority constraints that take into account transfer times between machines and setup times between jobs on the machines.

Constraints (10)-(17) enforce that each machine only processes one operation at a time.

Constraint (18) defines the completion time. Constraints (19) define the values of the decision variables.

Metaheuristic Algorithm Knowledge Fusion

In order to improve the performance of the algorithm, the embodiment of the present application adopts meta-heuristic algorithm knowledge fusion, that is, embedding EDA and SA in ICA to form HICA. Figure 2 shows the framework of the algorithm.

Compared with other algorithms, ICA has the advantages of fast convergence speed, high convergence accuracy, and strong global convergence, so ICA is selected as the backbone algorithm. By giving the search process a time-varying probability jump that eventually tends to zero, the simulated annealing algorithm can effectively avoid falling into a local optimal algorithm. EDA adopts the macro-evolution method based on search space and has strong global search ability. Therefore, after the assimilation strategy of ICA, SA and EDA are embedded to improve the superior and inferior solutions. Finally, the algorithm is evaluated on a large-scale randomly generated set of benchmark instances, and the results show that the algorithm solves the considered problem more efficiently than other algorithms.

Convergence of Empire Competitive Algorithms:

ICA is a new type of intelligent optimization algorithm inspired by the competitive behavior of empires, which belongs to the population-based random optimization search algorithm. The ICA divides the country into what are called imperialist countries and colonies. The countries with the shorter completion times in each empire are called imperialist countries, and the rest are called colonies.

Coding Scheme:

The coding scheme used in the embodiments of the present application takes less time in the entire iterative process. The coding scheme consists of two parts, the first part is machine tool selection (MS), and the second part is operation sequence (OS). in the array. For the OS part, the job number is stored in the OS array. In the first part, the embodiments of the present application use a local selection strategy. In the second part, the order of operations is randomly determined.

Initialization of the Empire

In the algorithm, countries with shorter durations are called imperialists, and the rest are colonies attached to imperialism. Country size (pop) includes several imperialist countries (Nim) and their colonies (Ncol).

POP=Nim+Ncol.

The number of colonies per empire is denoted by Ncx, and x = 1, 2, ..., Nim.

Through the roulette selection process, calculate the power of imperialist countries.

Calculate the size of the colonies acquired by each imperialist country based on its strength.

Mutation operation:

Mutation is a strategy adopted by imperialist countries to reduce duplication and increase diversity. Different individuals may have different mutation probabilities. The probability formula for mutation is as follows.

where η is the mutation probability of the individual, F is the fitness of the individual, _Favg is the fitness of the average individual, and _Fmin is the fitness of the worst individual. The better the individual fitness, the greater the mutation probability, which expands the individual search space and avoids premature convergence. The probability of mutation of poor individuals is lower, and better individuals can be obtained through mutation.

During the mutation process, for the MS part, this is achieved by randomly replacing the available machine tools. For the operating system part, it is implemented using the swap operation. The mutation process is shown in Fig. 4(a)-Fig. 4(b).

Diversification of assimilation strategies

The assimilation strategy produces a new solution, usually implemented in the same way. In the embodiment of the present application, the embodiment of the present application uses the diversification operation of the assimilation strategy. For Empire 1, this embodiment of the present application randomly selects a strategy: first, all colonies in Empire 1 are selected for assimilation; second, colonies in Empire 1 are randomly selected for the assimilation strategy. For other colonies of empire x, assimilation can be done by learning from any other imperialist country.

During the assimilation process, for the MS part, two points of the imperialist country are randomly selected using a two-point crossover, the elements between the two points are inserted into the corresponding positions of the new colony, and the rest are inserted into the old colony elements. The OS part adopts POX crossover, jobs are randomly selected, the jobs selected from the imperialist countries are inserted into the new colonies, while the remaining jobs are inserted into the new colonies according to the positions of the old colonies (see Fig. 5(a)-Fig. 5 (b)).

好的殖民地通过SA策略改进，

差的殖民地通过EDA的全局搜索改进，其中α和β分别表示通过SA和EDA改进的殖民地比例。After assimilation, the knowledge fusion meta-heuristic is used to improve the generated solution, namely

Good colonies are improved by SA strategies,

Poor colonies were improved by a global search of EDA, where α and β denote the proportion of colonies improved by SA and EDA, respectively.

Imperial Invasion

In order to gain stronger power, some empires may experience the phenomenon of imperial invasion, that is, invaders occupy the colonies of other empires at will to change the power of the empire. The imperial invasion process is shown in Figure 6.

Renewal and Destruction of Empires

First, in each empire, colonies may gain more rights than their imperialist states, and under their rule the most powerful colonies become new imperialist states. Colonies under the rule of the old imperialist countries were placed under the ownership of the new imperialist countries. The old imperialist countries have also become colonies of the new imperialist countries. Then, update the colonies of the worst empires by implementing EDA strategies.

In the empire, the colonies under imperialism no longer exist. Implement the strategy of empire demise and imperialism will be assigned to other empires to become colonies.

The simulated annealing algorithm starts from a higher initial temperature (T), and with the continuous decrease of the temperature parameter, combined with the probability jump characteristic when the temperature reaches the termination temperature (ΔΤ), it randomly finds the global optimal solution of the objective function in the solution space.

A new solution is generated by randomly selecting two neighborhood structures of the four neighborhood structures, and the fitness between the new solution and the current optimal solution is calculated. If the new solution is better, accept the new solution, otherwise accept the new solution according to a certain proportion, the annealing rate has a significant relationship with the acceptance probability of the suboptimal solution, which directly affects the speed and accuracy of SA. Terminate when the temperature falls back to the specified temperature. In general, the annealing rate function is as follows

T(λ)=δ×T(λ-1)

where δ∈(0,1) is the annealing rate coefficient. and T(λ-1)T(λ) are the current annealing temperature and the previous annealing temperature, respectively; λ is the number of iterations.

neighborhood structure

The neighborhood structures N1, N2, N3, N4 are described below. Neighborhood structure N1 is completed by replacing randomly selected position elements of MS parts. Neighborhood structure N2 acts on the OS part, which selects two job numbers and swaps them in a random fashion. Neighborhood structure N3 is accomplished by randomly selecting two positions R1 and R2, where r ₁ < r ₂ , inserting an element at position r ₂ before r ₁ in the MS part. Neighborhood fabric N4 generates new solutions by executing a switch fabric twice on the OS part (Fig. 7(a)-Fig. 7(d)).

Fusion of distribution estimation algorithms

EDA is a relatively new paradigm in the field of evolutionary computing that uses statistical information to build a probabilistic model of the most promising regions, which is then used to sample and generate new individuals. At the same time, the probability model is updated in each generation with potential individuals of the new population. EDA is sampled according to a probabilistic model. Therefore, the probabilistic model has a great influence on the performance of EDA.

In this embodiment of the present application, two probability matrices P1 and P2 are designed for the MS part and the OS part. The element M _j,q,I (L) of the probability matrix P1 of the MS part represents the probability of processing the operation O _j,q on the machine k in the L generation. m _j,q represents the available machine tool array for the qth operation of job j. The probability matrix P1 is initialized as follows:

The element H _j,f (L) of the OS probability matrix P2 represents the probability of job j appearing at position f of the OS matrix in the Lth generation. Q represents the total number of all operations in the OS section. Initializing the probability matrix P2 to H _j,f (0)=1/q ensures uniform sampling of the entire solution space. Then, the probability matrices P1 and P2 are updated by the following formulas.

M _j,q,i (L+1)=(1-θ)M _j,q,i (L)

H _j,f (L+1)=(1-τ)H _j,f (L)

where θ, τ∈(0, 1) are the learning rates of P1 and P2, respectively.

Sampling through probabilistic models P1 and P2 to generate new individuals.

experiment analysis

In order to test the performance of the proposed HICA algorithm, the embodiment of the present application simulates the scheduling process. All numerical experiments are performed on a Lenovo PC running Windows 7 with a 3.3GHz processor and 4GB of memory. The FJSP method is written in C++ for speed and robustness.

The algorithm has four important parameters: country size POP, the ratio of imperialism to country Nim/POP, the proportion of good colonies improved by SA, α, and the proportion of bad colonies improved by EDA. In order to study the influence of these parameters on the performance of HICA, Taguchi method was introduced, and the orthogonal table L ₁₆ was constructed by this method.

Then for each parameter combination, run 30 times independently, and collect the average fitness value of the algorithm as the response variable. Table 1 lists the levels of each parameter. Finally, factor level trend graphs for the four parameters are plotted based on the obtained data. As shown in Fig. 8(a)-Fig. 8(d), the proposed algorithm achieves the best performance when POP is at level 2, Nim/POP is at level 1, α is at level 2, and β is at level 1.

Table 1: Key parameter levels

To evaluate the proposed optimization model, the present embodiments use the exact solver IBM ILOGCPLEX 12.7.1 to compute the proposed MIP model. The settings for the precision solver are configured as follows: the maximum number of threads is 3 and the time limit is 3h. Since HICA can obtain a satisfactory solution within an acceptable time, the maximum CPU time of 30s is used as the stopping criterion. Then 18 small-scale instances are randomly generated: the number of jobs n ∈ {2, 3, 4, 5}, the number of machines m ∈ {2, 3}, and the number of operands q ∈ {2, 3, 4}.

Table 2. Comparison of deviation values for CPLEX and HICA

Table 2 presents the comparison results between the proposed algorithm and the CPLEX solver. The first column represents the instance name, the second column provides the scaled size of the algorithm (where X-Y-Z represent X jobs, Y operations, and Z machines, respectively), and the third column contains the best value for each instance. The fourth and fifth columns of HICA and CPLEX provide the target value for each instance. The sixth and seventh columns represent the mean square error of the two algorithms.

From Table 2 the following observations can be seen. (1) For the given 18 instances, the proposed algorithm obtains higher quality solutions than the CPLEX solver. (2) CPLEX cannot better solve large-scale problems.

Three variants of HICA are constructed, the content in HICA1 does not contain the SA policy, but the rest of the content is still consistent with HICA. The difference between HICA2 and HICA is the removal of EDA from HICA. HICA3 shares similarities with HICA, except for the imperial aggression strategy. The parameters have been set, and the operating environment is the same as HICA. Each calculation example is run independently for 30 times. The results are shown in Table 3. The instance name is in the first column, and the scale of the instance is in the second column (where X×Y represents X jobs and Y machine tools, respectively). The third column contains the best value for the instance. The next four columns describe the target values collected from the four algorithms, respectively. The mean square errors obtained by the four compared algorithms are listed in the last four columns, respectively.

Table 3. Comparison of dev values of HICA and three variants of HICA

From Table 3, the following points are observed for the examples of the present application, (1) For 35 examples with different problem sizes, HICA obtains 29 better results, outperforming all other examples. (2) The last row in the table shows that the average value of HICA is 0.004, which is better than other algorithms.

In order to determine whether there is a significant difference in the comparison of the results, a multivariate analysis of variance (ANOVA) was performed in the examples of the present application. In this embodiment of the present application, the confidence level is set to 95%. When p-value<0.05, the difference between algorithms is large, and it can be seen from Fig. 9(a)-Fig. 9(d) that the strategy of the embodiment of the present application is effective. Fig. 10(a)-Fig. 10(d) show the convergence curves of different types of instances, and the simulation results show that HICA has an effective convergence ability for solving the studied problem.

To further evaluate the performance of the proposed algorithm, the present embodiment compares HICA with other currently popular algorithms, including ICA, Improved GA (IGA), EDA, and AIA. The embodiments of the present application encode these five algorithms, and run each algorithm in the same environment. Examples run from 30 iterations to thousands of iterations, and all comparison algorithms use the same stopping criteria. Table 4 shows the average performance comparison of various algorithms.

Table 4. Comparison of various algorithms

From Table 4, the following points can be observed. (i) For the given 35 instances, the HICA algorithm obtains 32 optimal solutions, and the suboptimal algorithm ICA obtains only 3 optimal values, indicating that the HICA algorithm is superior to all other algorithms. (ii) The last row of Table 4 shows that, on average, the proposed algorithm achieves a value of 0.002, which is much larger compared to the results of the other considered algorithms. (iii) Overall, HICA performs significantly better than the other four algorithms.

Fig. 11(a)-Fig. 11(c) show the variance analysis results of the best solution, the average solution and the worst solution of the five comparison algorithms, from which it can be concluded that HICA is in solving the researched problem. The problem aspect has better performance. Figure 11(a)-Figure 11(c) show the convergence process for instances with different problem sizes. For each instance in Fig. 12(a)-Fig. 12(d), convergence data was collected from the best solution of 30 runs according to the running time of each algorithm. Figure 13 shows the Gantt chart of the solution obtained using the optimization strategy. By considering the transport time of workpieces between machines and the installation time between workpieces, the studied problem is closer to the real situation.

According to the experimental results in the previous section, the performance of the newly proposed HICA algorithm is better than other algorithms.

The main reasons can be summarized as: (I) four neighborhood structures are used in SA to improve the solution of SA, the use of SA prevents premature convergence, and the convergence speed is stable to obtain better optimization; ii) Empire invasion strategy by changing the empire The right to increase the diversity of understanding; iii) Two probabilistic models are used in EDA, which enhances the global search ability of the algorithm.

The present invention provides a meta-heuristic knowledge fusion method for solving the flexible workshop scheduling problem with transmission and switching time. Based on the knowledge fusion meta-heuristic algorithm, considering the FJSP problem with transit time and setup time constraints, a hybrid imperialist competition algorithm HICA is proposed, in which the imperialist competition algorithm (ICA) is used as the backbone and the simulated annealing (SA) algorithm is used. And distribution estimation algorithm (EDA) is used to improve the quality of the solution. The goal is to minimize the maximum makepan. First, each solution consists of two parts, the machine selection and the sequence of operations, which contain different information. Then, a new strategy of Imperial Invasion was adopted in the ICA to change the power of the Empire. Four neighborhood structures are constructed to create new solutions for SA to improve the optimal solution, and two different probabilistic models are embedded in EDA to optimize the inferior solution. Finally, the operators and parameters of the algorithm are calibrated using Taguchi method. The adopted location-based mathematical model was validated by CPLEX. The algorithm is tested on a large-scale randomly generated benchmark instance set, and it is verified that the algorithm can solve the considered problems well.

Embodiment 2

This embodiment provides a flexible job shop scheduling system with transmission and switching time;

Flexible job shop scheduling system with transfer and switching times, including:

an acquisition module, which is configured to: acquire parameters of the flexible job shop, the parameters include: the number of machine tools, the number of workpieces, the processing procedure corresponding to each workpiece, the processing time of the workpiece on the machine tool, and the transmission time between the machine tools and the switching time between the workpiece;

a model building module configured to: construct a flexible job shop scheduling model based on the parameters of the flexible job shop, the flexible job shop scheduling model including: an objective function and constraints;

The output module is configured to: solve the flexible job shop scheduling model based on the improved empire competition algorithm, assuming that a country represents a feasible scheme of the flexible job shop scheduling problem during the solving process; the solution finally outputs the flexible job shop scheduling scheme .

It should be noted here that the above acquisition module, model building module and output module correspond to steps S101 to S103 in the first embodiment, and the above modules and corresponding steps have the same examples and application scenarios, but are not limited to the above embodiments a published content. It should be noted that the above modules may be executed in a computer system such as a set of computer-executable instructions as part of the system.

The description of each embodiment in the foregoing embodiments has its own emphasis. For the part that is not described in detail in a certain embodiment, reference may be made to the relevant description of other embodiments.

The proposed system can be implemented in other ways. For example, the system embodiments described above are only illustrative. For example, the division of the above modules is only a logical function division. In actual implementation, there may be other division methods. For example, multiple modules may be combined or integrated into Another system, or some features can be ignored, or not implemented.

Embodiment 3

This embodiment also provides an electronic device, including: one or more processors, one or more memories, and one or more computer programs; wherein the processor is connected to the memory, and the one or more computer programs are Stored in the memory, when the electronic device runs, the processor executes one or more computer programs stored in the memory, so that the electronic device executes the method described in the first embodiment.

Embodiment 4

This embodiment also provides a computer-readable storage medium for storing computer instructions, and when the computer instructions are executed by a processor, the method described in the first embodiment is completed.

The above descriptions are only preferred embodiments of the present application, and are not intended to limit the present application. For those skilled in the art, the present application may have various modifications and changes. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of this application shall be included within the protection scope of this application.

Claims (10)

1. The flexible job shop scheduling method with transmission and switching time is characterized in that, comprising: Obtain the parameters of the flexible job shop, the parameters include: the number of machine tools, the number of workpieces, the processing procedure corresponding to each workpiece, the processing time of the workpiece on the machine tool, the transmission time between the machine tools and the switching time between the workpieces; Based on the parameters of the flexible job shop, a flexible job shop scheduling model is constructed, and the flexible job shop scheduling model includes: an objective function and constraints; Based on the improved empire competition algorithm, the flexible job shop scheduling model is solved. In the solution process, it is assumed that a country represents a set of feasible solutions for the flexible job shop scheduling problem; the solution finally outputs the flexible job shop scheduling scheme. 2. The method according to claim 1, wherein a flexible job shop scheduling model is constructed based on the parameters of the flexible job shop, and the flexible job shop scheduling model comprises: an objective function and a constraint condition; Among them, the objective function specifically refers to: minimizing the maximum completion time; Among them, the constraints specifically refer to: the job is available and ready at the initial moment; each operation can only be processed on one machine tool at a time; once the machine tool starts to execute the task, it cannot be interrupted until the task is completed; The storage buffer capacity is greater than the set threshold; preemption is not available, that is, subsequent operations must wait for the previous operation to complete; consider the transportation time and switching time; determine the machine tool selected for each operation and the sequence of operations on each machine tool to maximize significantly reduce the completion time. 3. The method of claim 1, wherein the improved empire competition algorithm is obtained by embedding the simulated annealing algorithm SA and the distribution estimation algorithm EDA into the empire competition algorithm. 4. The method according to claim 1, wherein, based on an improved empire competition algorithm, the flexible job shop scheduling model is solved, and in the solution process, it is assumed that a country represents a feasible solution for a group of flexible job shop scheduling problems; Finally, output the flexible job shop scheduling scheme; the specific steps include: (1) Set the parameters of the empire competition algorithm to solve the flexible workshop scheduling problem; (2) Generate an initial population, empire initialization, assuming a country represents a set of solutions to a flexible job shop scheduling problem; each solution consists of two parts, a machine tool selection sequence and an operation sequence; (3) Mutation operation: mutate the solution to increase the diversity of the solution; (4) Determine whether the number of countries is greater than the set threshold. If it is greater than the set threshold, change the assimilation strategy to determine whether a good colony is obtained. If a good colony is obtained, use the simulated annealing algorithm to solve it; Colony, use the distributed estimation algorithm to solve; if it is less than or equal to the set threshold, execute the assimilation strategy and enter (5); (5) Imperial invasion; (6) Empire update; (7) Empire destruction; (8) Judging whether the termination condition is reached, if so, end, and output the flexible job shop scheduling scheme; if not, return to (4). 5. The method according to claim 4, wherein the assimilation strategy refers to: the process of the imperialist country making the colonies close to itself, that is, the process of optimizing the difference solution in the flexible shop scheduling problem; For empire i, choose a strategy at random: first select all colonies in empire i for assimilation; second, randomly choose colonies in empire i for assimilation strategy; for colonies of the remaining empire, assimilate by learning from any other imperialist country ; During the assimilation process, for the machine tool selection part, use the two-point crossover strategy to randomly select two points of the imperialist country, the elements between the two points are inserted into the corresponding positions of the new colony, and the rest are inserted into the old colony elements; During the assimilation process, for the operation sequence part, a POX crossover strategy is adopted, jobs are randomly selected, the jobs selected from the imperialist countries are inserted into the new colonies, and the remaining jobs are inserted into the new colonies according to the positions of the old colonies. 6. The method according to claim 4, characterized in that, using a simulated annealing algorithm to solve, specifically comprising: Create new solutions for the simulated annealing algorithm by constructing four neighborhood structures to improve the optimal solution; or, The simulated annealing algorithm is used to solve the problem, and the detailed steps include: Using four neighborhood structures N1, N2, N3, N4 to improve the solution in the simulated annealing algorithm; Neighborhood structure N1 is done by replacing randomly selected position elements of machine tool selection parts; The neighborhood structure N2 acts on the operation sequence part, and the operation sequence part is realized by randomly selecting two job numbers and exchanging the two job numbers; The neighborhood structure N3 is completed by randomly selecting two positions r ₁ and r ₂ in the machine tool selection part, where r ₁ <r ₂ , and inserting the element at r ₂ at the position before r ₁ ; Neighborhood structure N4 generates new solutions by executing an exchange structure twice in the sequence of operations part. 7. The method of claim 4, wherein Use distributed estimation algorithm to solve, specifically including: Two different probabilistic models are embedded in the distributed estimation algorithm to optimize the inferior solution. 8. A flexible job shop scheduling system with transmission and switching time, characterized in that it includes: an acquisition module, which is configured to: acquire parameters of the flexible job shop, the parameters include: the number of machine tools, the number of workpieces, the processing procedure corresponding to each workpiece, the processing time of the workpiece on the machine tool, and the transmission time between the machine tools and the switching time between the workpiece; a model building module configured to: construct a flexible job shop scheduling model based on the parameters of the flexible job shop, the flexible job shop scheduling model including: an objective function and constraints; The output module is configured to: solve the flexible job shop scheduling model based on the improved empire competition algorithm, assuming that a country represents a feasible solution to a set of flexible job shop scheduling problems during the solution process; the solution finally outputs the flexible job shop scheduling scheme . 9. An electronic device, characterized in that it comprises: one or more processors, one or more memories, and one or more computer programs; wherein the processor is connected to the memory, and the one or more computer programs are Stored in a memory, when the electronic device is running, the processor executes one or more computer programs stored in the memory to cause the electronic device to perform the method of any one of claims 1-7 above. 10 . A computer-readable storage medium, characterized in that it is used for storing computer instructions, and when the computer instructions are executed by a processor, the method according to any one of claims 1-7 is completed. 11 .

Images