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

This article mainly introduces how to use matlab genetic algorithm to solve the job shop scheduling problem, which has a certain reference value. Interested friends can refer to it. I hope you will gain a lot after reading this article.

A brief introduction to Job Shop scheduling 1 definition of Job Shop scheduling

Job shop scheduling refers to allocating the sequence of processing workshops according to the reasonable needs of product manufacturing, so as to achieve the purpose of making rational use of product manufacturing resources and improving the economic benefits of enterprises. The job shop scheduling problem can be described mathematically as there are n parts to be processed on m machines. The conditions that the problem needs to meet include that each process of each part is used no more than once per machine, and each part is processed in a certain order.

2 traditional job shop scheduling

Traditional job shop with scheduling example

There are several workpieces, each workpiece has several processes, there are multiple processing machines, but each process can only be processed on one machine. Corresponding to the example in the table above, there are two workpieces, workpiece J1 has three processes, process Q11 can only be processed on M3, and the processing time is 5 hours.

Constraint is that for an artifact, the relative order of processes cannot be changed. O11-> O12-> O13. Each workpiece can only be processed on one machine at a time; there can be only one workpiece on each machine.

The task of scheduling is to arrange the processing order of the process, which is determined, because there is only one machine available for each process, and the processing machine is determined.

The purpose of scheduling is to minimize the total completion time (which can also be other goals). For example, after determining the processing order of O21-> O22-> O11-> O23-> O12-> O13, we can calculate the total processing time according to the constraints of the processing machine.

M2 processing O21 takes 6 hours, and the current processing time of workpiece J2 is 6 hours.

M1 processing O22 takes 9 hours, and the current processing time of workpiece J2 is 6: 9: 15 hours.

M3 processing O11 takes 5 hours, and the current processing time of workpiece J1 is 5 hours.

The processing time of M4 O23 is 7 hours, and the processing time of workpiece J2 is 15-7-22 hours.

M1 processing O12 takes 11 hours, but the processing of O12 does not start until M1 has finished processing O22, so the current processing time of workpiece J1 is max (5mem9) + 1120 hours.

The processing time of M5 O13 is 8 hours, and the processing time of workpiece J2 is 28 hours.

The total completion time is max (22 minutes 28) = 28 hours.

2 flexible job shop scheduling

Flexible Job Shop with scheduling example (refer to teacher's thesis from highlight)

"improved genetic algorithm for flexible Job Shop scheduling problem"-- Journal of Mechanical Engineering)

Compared with traditional job shop scheduling, flexible job shop scheduling relaxes the constraints on processing machines, which is more in line with the actual production situation. Each process has become multiple optional processing machines, which can be processed by one of multiple processing machines. For example, in the example in the table above, the O12 process of J1 can choose M2 and M4 processing, and the processing time is 8 hours and 4 hours respectively, but M4 processing is not necessarily selected, so the total completion time is even shorter. Scheduling algorithm is needed to solve the optimization.

Compared with the traditional job shop, the scheduling task of flexible job shop scheduling needs to determine not only the processing sequence of the process, but also the machine allocation of each process. For example, the processing sequence of O21-> O22-> O11-> O23-> O12-> O13 is determined, so we should also determine the corresponding machine combinations of [M1, M3, M5]-> [M1, M2, M3, M4, M5]-> [M2, M3, M4, M5]-> [M2, M4]-> [M1, M3, M4, M5]. The purpose of scheduling is to have the shortest total completion time (or other goals, such as the shortest maximum machine load and the shortest total machine load).

Introduction of genetic algorithms 1 Overview of genetic algorithms

Genetic algorithm (Genetic Algorithm,GA) is a part of evolutionary computation, which simulates Darwin's genetic selection and natural elimination of biological evolution process. It is a method to search the optimal solution by simulating natural evolution process. The algorithm is simple, universal, robust and suitable for parallel processing.

2 characteristics and application of genetic algorithm

Genetic algorithm is a kind of robust search algorithm which can be used for complex system optimization. Compared with traditional optimization algorithms, genetic algorithm has the following characteristics:

The main results are as follows: (1) the coding of decision variables is taken as the operation object. Traditional optimization algorithms often directly use the actual value of the decision variable itself for optimization calculation, but the genetic algorithm uses some form of coding of the decision variable as the operation object.

(2) using fitness as search information directly. The traditional optimization algorithm not only needs to use the value of the objective function, but also the search process is often constrained by the continuity of the objective function, and may also need to meet the requirement that "the derivative of the objective function must exist" to determine the search direction. The genetic algorithm only uses the fitness function value transformed from the objective function value to determine the further search range without other auxiliary information such as the derivative value of the objective function. The direct use of the objective function value or individual fitness value can also concentrate the search scope to the search space with higher fitness, so as to improve the search efficiency.

(3) the search information of multiple points is used, which has implicit parallelism. Traditional optimization algorithms often start the iterative search process of the optimal solution from an initial point in the solution space. The search information provided by a single point is not much, so the search efficiency is not high, and it is possible to get stuck in the local optimal solution; genetic algorithm starts the search process of the optimal solution from the initial population composed of many individuals, not from a single individual. The operations of selection, crossover and mutation on the initial population produce a new generation of population, including a lot of group information. This information can avoid searching some unnecessary points, so as to avoid falling into the local optimal solution and gradually approach the global optimal solution.

(4) use probabilistic search instead of deterministic rules. Traditional optimization algorithms often use deterministic search methods, and the transfer from one search point to another has a definite transfer direction and transfer relationship, which may make the search unable to reach the optimal store and limit the scope of application of the algorithm. Genetic algorithm is a kind of adaptive search technology, and its selection, crossover and mutation operations are carried out in a probabilistic way, which increases the flexibility of the search process, and can converge to the optimal solution with high probability. It has a good ability of global optimization. However, parameters such as crossover probability and mutation probability will also affect the search results and search efficiency of the algorithm, so how to select the parameters of genetic algorithm is an important problem in its application.

In summary, because the overall search strategy and optimization search method of genetic algorithm do not rely on gradient information or other auxiliary knowledge, it only needs to solve the objective function and the corresponding fitness function that affect the search direction. therefore, genetic algorithm provides a general framework for solving complex system problems. It does not depend on the specific domain of the problem, and has strong robustness to the types of problems, so it is widely used in various fields, including function optimization, combinatorial optimization production scheduling problem, automatic control.

, robotics, image processing (image restoration, image edge feature extraction.) , artificial life, genetic programming, machine learning.

3 basic flow and implementation technology of genetic algorithm

Basic genetic algorithm (Simple Genetic Algorithms,SGA) only uses three kinds of genetic operators: selection operator, crossover operator and mutation operator. The evolution process is simple and is the basis of other genetic algorithms.

3.1 basic flow of genetic algorithm

A number of initial groups encoded by a certain length (length related to the accuracy of the problem to be solved) are randomly generated.

Each individual is evaluated by the fitness function, and the individuals with high fitness values are selected to participate in the genetic operation, and the individuals with low fitness are eliminated.

A new generation of population is formed by genetic manipulation (replication, crossover, mutation) until the stopping criterion is met (evolutionary algebra GEN > =?)

The best realized individuals in the offspring are taken as the execution result of the genetic algorithm.

Where GEN is the current algebra, M is the population size, and I represents the population size.

3.2 implementation technology of genetic algorithm

The basic genetic algorithm (SGA) consists of coding, fitness function, genetic operator (selection, crossover, mutation) and running parameters.

3.2.1 Encoding

(1) binary coding

The length of the binary encoded string is related to the accuracy of the problem. It is necessary to ensure that each individual in the solved space can be encoded.

Advantages: easy to encode and decode, easy to realize heredity and crossover

Disadvantages: large length

(2) other coding methods

Gray code, floating point coding, symbol coding, multi-parameter coding, etc.

3.2.2 fitness function

The fitness function should effectively reflect the gap between each chromosome and the optimal solution of the problem.

3.2.3 selection operator

3.2.4 crossover operator

Crossover operation means that two paired chromosomes exchange some of their genes in some way to form two new individuals. Crossover operation is an important feature that distinguishes genetic algorithms from other evolutionary algorithms and is the main way to generate new individuals. Individuals in the population need to be matched before crossover, and the principle of random pairing is generally adopted.

Common crossover methods:

Single point crossing

Two-point intersection (multi-point crossing, the more crossing points, the greater the possibility of individual structure being destroyed, generally, the way of multi-point crossing is not adopted)

Uniform crossover

Arithmetic crossover

3.2.5 mutation operator

The mutation operation in genetic algorithm refers to replacing the gene values of some loci in the individual chromosome coding string with other alleles of the locus to form a new individual.

In terms of the ability to generate new individuals in the operation process of genetic algorithm, crossover operation is the main method to generate new individuals, which determines the global search ability of genetic algorithm, while mutation operation is only an auxiliary method to generate new individuals. but it is also an indispensable operation step, which determines the local search ability of genetic algorithm. The cooperation of crossover operator and mutation operator completes the global search and local search of the search space, so that the genetic algorithm can complete the optimization process with good search performance.

3.2.6 operating parameters

4 the basic principle of genetic algorithm 4.1 pattern theorem

4.2 Building block hypothesis

A pattern with low order, short definition length and a fitness value higher than the population average fitness value is called a gene block or a building block.

The building block hypothesis: individual gene blocks can be spliced together to form individual coding strings with higher fitness through the action of genetic operators such as selection, crossover and mutation.

The building block hypothesis illustrates the basic idea of using genetic algorithm to solve all kinds of problems, that is, the building blocks can be directly spliced together to produce a better solution.

Part of the source code clc;clear%% download data% processing data including processing time, processing machines, number of machines, weight of each machine, number of workpieces, load data operation_time operation_machine num_machine machine_weight num_job num_op%% basic parameters MAXGEN = 200;% maximum number of iterations Ps = 0.8;% selection rate Pc = 0.7 % cross rate Pm = 0.3;% mutation rate sizepop = 200;% number of individuals e = 0.5;% target value weight trace = zeros (2MAXGEN);%% = population initialization = = total_op_num=sum (num_op); chroms=initialization (num_op,num_job,total_op_num,sizepop,operation_machine,operation_time) ] = fitness (chroms,num_machine,e,num_job,num_op);% = = iterative process = = for gen=1:MAXGEN fprintf ('current iterations:'), disp (gen)% roulette choice chroms_new=selection (chroms,Z,Ps);% cross operation chroms_new=crossover (chroms_new,Pc,total_op_num,num_job,num_op) % mutation operation chroms_new=mutation (chroms_new,total_op_num,Pm,num_machine,e,num_job,num_op,operation_machine,operation_time);% calculate the fitness of the individual after selecting crossover mutation [Zero new journal] = fitness (chroms_new,num_machine,e,num_job,num_op) % according to fitness, select sizepop better individuals from the original population and genetically operated population [chroms,Z,chrom_best] = update_chroms (chroms,chroms_new,Z,Z_new,sizepop);% record the optimal fitness and average fitness of each generation trace (1, gen) = Z (1); trace (2, gen) = mean (Z) % Update global optimal fitness if gen==1 | | MinVal > trace (1Magnegen) MinVal=trace (1jiggen); function [Zmachinemachineweightweight] = fitness (chroms,num_machine,e,num_job,num_op) sizepop=size (chroms,1); pvals=cell (1memsizepop); Z1=zeros (1Powersizepop); Z2fitness Z1transferability totaltalsizepop numnumfitness sum (num_op);% total number of processes for k=1:sizepop chrom=chroms (kLING:); machine=zeros (1MNM machine) % record the change time of each machine (job=zeros); record the change time of each workpiece (machine_time=zeros); calculate the actual processing time of each machine pval=zeros (2) % record the start and end time of each process for i=1:total_op_num% Machine time is greater than workpiece time if machine (chrom (total_op_num+i)) > = job (chrom (I)) pval (1memi) = machine (chrom (total_op_num+i)) % record artifact start time machine (chrom (total_op_num+i)) = machine (chrom (total_op_num+i)) + chrom (total_op_num*2+i); job (chrom (I)) = machine (chrom (total_op_num+i)); pval (2) = machine (chrom (total_op_num+i)) % record workpiece end time% Machine time is less than workpiece time else pval (1Magi) = job (chrom (I)); job (chrom (I)) = job (chrom (I)) + chrom (total_op_num*2+i); machine (chrom (total_op_num+i)) = job (chrom (I)); pval (2Magi) = job (chrom (I)) End machine_time (chrom (total_op_num+i)) = machine_time (chrom (total_op_num+i)) + chrom (total_op_num*2+i); end Z1 (k) = max (machine);% maximum machine time value, corresponding to makespan% machine_weight=machine_time/sum (machine_time);% calculate machine load machine_weight=machine_time; Z2 (k) = max (machine_weight)-min (machine_weight) Pvals {k} = pval;end% min_makespan=min (Z1);% optimal value of makespan for all chromosomes% max_makespan=max (Z1);% min_weight=min (Z2);% load optimal value% max_weight=max (Z2);% Zambie* ((Z1-min_makespan). / (max_makespan-min_makespan)) + (1mure) * ((Z2-min_weight). / (max_weight-min_weight));% calculated fitness ZambieFirstZ1 + (1REE) * Z2 Function [chroms_new] = crossover (chroms,Pc,total_op_num,num_job,num_op) size_chrom=size (chroms,1);% chromosome number chroms_new=chroms;%% crossover operation for sequence codes for i=1:2:size_chrom-1 if Pc > rand% parent chromosome parent1=chroms (iMagazine:); parent2=chroms (iMagnum:); Job=randperm (num_job) % randomly divide the artifact into two sets: J1=Job (1:round (num_job/2)); J2=Job (length (J1) + 1:end);% progeny chromosome child1=parent1; child2=parent2; op_p1= []; op_p2= [] For j=1:length (J2)% find the corresponding position of J2 fragment in the parent op_p1= [op _ p1 1:total_op_num find (parent1 (1:total_op_num) = = J2 (j)]; op_p2= [op _ p2 find (parent2 (1:total_op_num) = = J2 (j))]; end op_s1=sort (op_p1); op_s2=sort (op_p2) % progeny 1 exchanges the gene of J2 fragment, the gene corresponding to machine code, the gene corresponding to working time code child1 (op_s1) = parent2 (op_s2), child1 (total_op_num+op_s1) = parent2 (total_op_num+op_s2), child1 (total_op_num*2+op_s1) = parent2 (total_op_num*2+op_s2) % progeny 2 isomorph child2 (op_s2) = parent1 (op_s1); child2 (total_op_num+op_s2) = parent1 (total_op_num+op_s1); child2 (total_op_num*2+op_s2) = parent1 (total_op_num*2+op_s1); chroms_new (iMagery:) = child1; chroms_new (iLimel:) = child2 Endend%% is oriented to machine code crossover operation for k=1:2:size_chrom-1 if Pc > rand parent1=chroms_new (kjingl:); parent2=chroms_new (kumb1gle:); child1=parent1; child2=parent2;% randomly generates 0meme 1 sequence rand0_1=randi which is equal to the length of chromosome ([0mem1], 1memery opposinum) For n=1:num_job ind_0=find (rand0_1 (num_op (n) * (NMur1) + 1:num_op (n) * n) = 0); if ~ isempty (ind_0) temp1=find (parent1 (1:total_op_num) = = n); temp2=find (parent2 (1:total_op_num) = = n) Child1 (total_op_num+temp1 (ind_0)) = parent2 (total_op_num+temp2 (ind_0)); child2 (total_op_num+temp2 (ind_0)) = parent1 (total_op_num+temp1 (ind_0)); child1 (total_op_num*2+temp1 (ind_0)) = parent2 (total_op_num*2+temp2 (ind_0)) Child2 (total_op_num*2+temp2 (ind_0)) = parent1 (total_op_num*2+temp1 (ind_0)); endend chroms_new (KJE:) = child1; chroms_new (Kwon 1:) = child2; endendend 4, running result

Thank you for reading this article carefully. I hope the article "how to use matlab genetic algorithm to solve Job Shop scheduling problem" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.