Shulou(Shulou.com)06/02 Report--

What this article shares to you is about how to carry out job shop scheduling JSP and genetic algorithm GA and its Python/Java/C++ implementation, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

Problem description

Job shop scheduling (Job shop scheduling problem, JSP) is the most common type of job shop scheduling, and it is one of the most difficult combinatorial optimization problems. It is widely used in a wide range of fields, including aircraft carrier scheduling, airport aircraft scheduling, port cargo ship scheduling, automobile processing assembly line and so on. Scientific and effective production scheduling can not only improve the efficient utilization of workers and equipment resources in the production process, but also shorten the production cycle and reduce the production cost.

Job shop scheduling problem description:

A processing system has M machines, which requires N jobs to be processed, in which job I contains a number of processes. Then L is the total number of processes in the task set. Among them, the processing time of each process has been determined, and each operation must be processed according to the sequence of the process. The task of scheduling is to arrange the scheduling of all jobs, and the performance index can be optimized while the constraints are met. Job shop scheduling needs to consider the following constraints:

1. Each process is processed on a designated machine and can only be started after the previous process has been completed.

two。 One machine can only process one job at a time.

3. Each assignment can only be processed once on one machine.

4. The process sequence and processing time of each job are known and will not change with the change of processing sequence.

The mathematical model of the problem:

Order (iMagazine j) indicates the j process of operation I. S_ij and T_ij denote the processing start time and processing time respectively. Z_ijk indicates whether it is processed on the k-th machine: if it is processed on the k-th machine, Zambiijk is the completion time of the k-th machine, otherwise, the mathematical model of the problem is as follows:

Formula (1) is the objective function, that is, the optimization objective, and the shortest total processing time is used in the system as the optimization objective. Formula (2) indicates that a job can process the latter process only after the completion of the previous process. Formula (3) indicates that the initial processing time of the first process of an operation is greater than or equal to 0. Formula (4) indicates that more than one job will not be processed on one machine tool at the same time.

Genetic algorithm.

With the wide application of genetic algorithm (genetic algorithm (GA)) in combinatorial optimization problems, many people begin to do in-depth research on genetic algorithms. The previous research results show that genetic algorithm has a good effect on solving job shop scheduling problem, so the system uses genetic algorithm to solve this problem. Genetic algorithm is a search algorithm used to solve optimization in computational mathematics. It is a kind of evolutionary algorithm. Evolutionary algorithms were originally developed from some phenomena in evolutionary biology, including heredity, mutation, natural selection, hybridization and so on. The system continuously generates new individuals by simulating biological evolution, including heredity, mutation, selection, etc., and obtains the optimal individual, that is, the optimal solution, when the algorithm is terminated.

The basic steps of genetic algorithm to solve job shop scheduling problem:

1. Initialize a certain number of populations (chromosome coding)

two。 Calculate individual fitness (chromosome decoding)

3. Using the tournament method to select chromosomes and cross to produce new individuals

4. Individual (chromosome) variation

5. Achieve the genetic algebraic termination algorithm and select the individual with the best fitness as the solution to the job shop scheduling problem.

The flow chart is as follows:

Parameters required by genetic algorithm:

1. Population size: the number of individuals in a population, expressed as populationNumber

two。 Chromosome length: the length of an individual's chromosome, expressed as chromosomeSize.

3. Crossover probability: controls the frequency of use of the crossover operator, expressed as crossProbability, with a value of 0.95

4. Mutation probability: controls the frequency of use of the mutation operator, expressed as mutationProbability, with a value of 0.05

5. Genetic algebra: the genetic algebra of a population, used to control the termination of genetic algorithms, expressed in times.

The basic steps and pseudo code of genetic algorithm implementation:

1. Coding and initialization of population

The process real number coding is used to represent the chromosome, that is, M machines, N workpieces, and the number of processes of each workpiece is process_i, then the chromosome length is chromosome=process_1+process_2+..., and the chromosome is encoded as follows:

Chromosome=...,w_i,w_j,w_k,...

Where wrecki represents the number of the first workpiece, and the number of occurrences represents the number of processes of the workpiece. For example, {0meme1pr 2,0,0je 1pr 2}, Zhong 0pi 1jue 2 denotes the number of the workpiece, and the number of times it appears represents the number of processes. Then each randomly generated chromosome individual is added to the population set.

Algorithm pseudo code:

two。 Decoding and calculating fitness

The optimization goal is defined as the shortest total processing time, so the fitness is defined as the reciprocal of the shortest processing time, fitness is the fitness of the corresponding individual, and fulfillTime is the shortest processing time, so

The calculation method of fulfillTime is as follows:

First define the following variables

Then traverse the chromosome sequence of the individual from left to right, which represents the number of the I workpiece, then the corresponding current process is set to p. The machine number used in the current process of the current workpiece is set to m. The processing time corresponding to the current process of the current workpiece is set to t. Then the latest start time of the p th process of the workpiece is

The processing time of the m-th machine is

The end time of the p th process of the workpiece is

Finally, the shortest processing time fulfillTime of all the workpieces is

Thus the fitness fitness is calculated.

PS. The editor feels that the decoding process is similar to dynamic planning.

The pseudo code is as follows:

3. Individual selection operator

The selection of individuals uses the tournament method, and its basic strategy is to randomly select n individuals from the whole population for them to compete, and select the best one. The selection process of the operator is as follows

The pseudo code is as follows:

4. Chromosome crossover operator

Using the Order Crossover (OX) crossover operator, the crossover steps are as follows:

For a pair of chromosomes G1 and G2, a start position start and an end position end are randomly generated, and a progeny prototype is generated from the chromosome sequence from G1 from start to end.

Add the remaining codes in G2 that are not included in the child prototype to both sides of the child prototype

The above steps will produce a child, and exchange G1 and G2 to produce another child

The pseudo code is as follows:

5. Chromosome mutation operator

The main function of mutation is to make the algorithm jump out of the local optimal solution, so different ways of mutation have a great impact on whether the algorithm can obtain the global optimal solution. The position variation method is used as the mutation operator, that is, two positions are randomly generated from the chromosome and the values of the two positions are exchanged.

The pseudo code is as follows:

6. The whole pseudo code of the algorithm is as follows:

Code implementation

The original author wrote three versions of the Java,Python,C++ code, and the editor carefully read the Java code, added some comments and slightly modified it, and shared it with you.

Explain the input part, the input example is written in the code, the example is as follows:

Jop0= [(0rem 3), (1je 2), (2je 2)]

Jop1= [(0rem 2), (2je 1), (1pr 4)]

Jop2= [(1) 4), (2) 3)]

In this example, the operation jop0 has three processes: its first process is marked (0p3), which means that the first process must be processed on the 0th machine and requires 3 units of processing time; its second process is marked (1d2), which indicates that the second process must be processed on the first machine and requires 2 units of processing time; the rest is the same. Overall, there are eight processes in this example.

One of the feasible solutions is shown in the figure.

The above is how to carry out job shop scheduling JSP and genetic algorithm GA and its Python/Java/C++ implementation. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.