A brief introduction to workshop scheduling

1. Definition of Shop Scheduling Shop scheduling refers to the allocation of processing shop sequence according to the reasonable demand of product manufacturing, so as to achieve the rational use of product manufacturing resources and improve the economic benefits of enterprises. The shop floor scheduling problem can be described mathematically as having n parts to be processed on M machines. The conditions to be met include that each process of each part shall use each machine no more than once and each part shall be processed in a certain order.

Traditional job shop schedulingTraditional job shop with scheduling instancesThere are a number of workpiece, each workpiece has a number of processes, there are multiple processing machines, but each process can only be processed on one machine. Corresponding to the example in the above table, there are two workpieces, and the workpiece J1 has three processes. The process Q11 can only be processed on M3, and the processing time is 5 hours. A constraint is that the relative order of operations cannot be changed for a workpiece. 11 – > O12 – > O13. Each workpiece can be processed on only one machine at a time; There can be only one work piece per machine. The task of scheduling is to arrange the processing order of the working procedure, and the processing order is determined, because there is only one machine available for each working procedure, and the processing machine is determined. The goal of scheduling is to minimize the total completion time (or any other goal). 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, the current processing time of workpiece J2 is 6 hours. M1 processing O22 takes 9 hours, the current processing time of workpiece J2 is 6+9=15 hours. It takes 5 hours for M3 to process O11 and 5 hours for workpiece J1. M4 O23 processing cost 7 hours, workpiece J2 processing time 15+7=22 hours. M1 processing O12 takes 11 hours, but O12 can be processed only after M1 processes O22, so the current processing time of workpiece J1 is Max (5,9)+11=20 hours. M5 processing O13 consumes 8 hours, the workpiece J2 processing time 20+8=28 hours. The total completion time is Max (22,28)=28 hours.

Flexible job shop schedulingFlexible Job Shop with Scheduling Example (reference from Gao Liang’s paper “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 and is more in line with the reality of production. The optional processing machines in each process become multiple, which can be processed by one of multiple processing machines. For example, as shown in the above table, THE O12 process of J1 can be processed by M2 and M4, and the processing time is 8 hours and 4 hours respectively. However, M4 process is not always selected, and the final total completion time is shorter. Therefore, scheduling algorithm is needed to solve and optimize.

Compared with traditional job shop, the scheduling task of FLEXIBLE job shop scheduling not only needs to determine the processing sequence of each process, but also needs to determine the machine allocation of each process. For example, determine the processing order of O21->O22->O11->O23->O12->O13, we can not process the machine corresponding to the process, Therefore, the corresponding machine combination of [M1, M3, M5]->[M1, M2, M3]->[M1, M2, M3, M4, M5]->[M2, M3, M4, M5]->[M2, M4]->[M1, M3, M4, M5] should also be determined. The goal of scheduling is still the shortest total completion time (it can also be other goals, such as the shortest maximum machine load, the shortest total machine load).

Introduction to genetic algorithm

Genetic Algorithm (GA) is a part of evolutionary computing. It is a computational model that simulates Darwin’s Genetic selection and natural selection of biological evolution process. It is a method to search for 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 algorithm, it has the following characteristics: (1) The encoding of decision variables is taken as the operation object. Traditional optimization algorithms often directly use the actual value of the decision variable itself to optimize the calculation, but genetic algorithm uses a certain form of the decision variable encoding as the operation object. This method of encoding decision variables makes it possible for us to use the concepts of chromosomes and genes in biology for reference in optimization calculation, to imitate the genetic and evolutionary incentives of organisms in nature, and to easily apply genetic operators. (2) Directly use fitness as search information. The traditional optimization algorithm not only needs to use the value of the objective function, but also needs to satisfy the requirement of “the derivative of the objective function must exist” in order to determine the search direction. Genetic algorithm can only use the fitness function value transformed from the objective function value to determine the further search range, without the derivative value of the objective function and other auxiliary information. The objective function value or individual fitness value can be directly used to concentrate the search scope into the search space with higher fitness, so as to improve the search efficiency. (3) Search information of multiple points is used with implicit parallelism. Traditional optimization algorithms usually start from an initial point in the solution space to search the optimal solution iteratively. The search information provided by a single point is not much, so the search efficiency is not high, and there may be local optimal solution and stagnation. Genetic algorithms start the search process for optimal solutions from an initial population consisting of many individuals rather than from a single individual. The operation of selection, crossover and mutation on the initial population produces a new generation of population, which contains a lot of population 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 rather than deterministic rules. Traditional optimization algorithms often use deterministic search methods, the transfer of a search point to another search point has a certain direction and transfer relationship, such deterministic search may not reach the optimal shop, limit the scope of application of the algorithm. Genetic algorithm (GA) is a kind of adaptive search technology. Its selection, crossover, mutation and other operations are carried out in a probabilistic way, which increases the flexibility of the search process, and can converge to the optimal solution with a large probability, and has a good global optimization capability. However, crossover probability, mutation probability and other parameters can also affect the search results and search efficiency of the algorithm, so how to choose the parameters of genetic algorithm is a relatively important problem in its application. To sum up, genetic algorithm provides a general framework for solving complex system problems because the overall search strategy and optimal search mode of genetic algorithm do not depend on gradient information or other auxiliary knowledge in calculation, but only require the solution of objective function that affects the search direction and the corresponding fitness function. It is not dependent on the specific domain of the problem and has strong robustness to the type of the problem, so it is widely used in a variety of 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.

Simple Genetic Algorithms (SGA) only uses selection operator, crossover operator and mutation operator. It is the basis of other Genetic Algorithms because of its Simple evolution process.

3.1 The basic process of genetic algorithm generates a number of initial populations encoded by a certain length (length is related to the accuracy of the problem to be solved) in a random way; Each individual was evaluated by fitness function, and the individuals with high fitness were selected to participate in genetic operation, while the individuals with low fitness were eliminated. The collection of genetically manipulated individuals (replication, crossover, mutation) forms a new generation of population until the stop criterion (evolutionary algebra GEN>=?) is satisfied. ; The best cashed individual in the offspring is taken as the execution result of the genetic algorithm.Where GEN is the current algebra; M is population size and I is population size.

3.2 Implementation technology of Genetic Algorithm Basic genetic algorithm (SGA) is composed of coding, fitness function, genetic operator (selection, crossover, variation) and operating parameters. 3.2.1 Encoding (1) Binary encoding The length of the string encoded in binary is related to the accuracy of the problem solved. It is necessary to ensure that every individual in the solved space can be coded. Disadvantages: large length (2) Other coding methods gray code, floating point coding, symbol coding, multi-parameter coding, etc. 3.2.2 Fitness function Fitness function should effectively reflect the gap between each chromosome and the optimal solution of the problem chromosome. 3.2.3 Selecting the operator3.2.4 Crossover Operator Crossover operation refers to the exchange of part of genes between two mutually paired chromosomes in a certain way, so as to form two new individuals; Crossover operation is an important feature of genetic algorithm which is different from other evolutionary algorithms and is the main method to generate new individuals. Before crossover, individuals in the group need to be matched, generally adopting the principle of random pairing. Common crossover methods: Single point crossing double point crossing (multi-point crossing, the more points of crossing, the more likely the individual’s structure will be destroyed, Arithmetic crossover 3.2.5 mutation operator Mutation operation in genetic algorithm refers to the replacement of gene values at some loci in the coding string of individual chromosome with other alleles of that loci, thus forming a new individual.

In terms of the ability to generate new individuals in the process of genetic algorithm, crossover operation is the main method to generate new individuals, which determines the global search ability of genetic algorithm. Mutation operation is only an auxiliary method to generate new individuals, but it is also an essential operation step, which determines the local search ability of genetic algorithm. The combination 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 Parameters4 Basic principle of genetic algorithm 4.1 Pattern theorem4.2 Building blocks Assume that patterns with low order, short definition length, and fitness values higher than the population average fitness value are called gene blocks or building blocks. Building block hypothesis: individual gene blocks can be spliced together to form individual coding strings with higher fitness through selection, crossover, mutation and other genetic operators. The building block hypothesis illustrates the basic idea of solving all kinds of problems with genetic algorithms, that is, better solutions can be produced by directly joining the building blocks together.

Three, some source code

clc; Processing data includes processing time, processing machine, number of machines, weight of each machine, number of work pieces, Load data operation_time operation_machine num_machine machine_weight num_job num_op %% Basic parameter MAXGEN =200; % Maximum number of iterations Ps =0.8; % Selection rate Pc =0.7; % cross rate Pm =0.3; % variation rate sizepop =200; % number of individuals e =0.5; % trace = zeros(2,MAXGEN); % % = = = = = = = = = = = = = = = = = = = = = = = = = = = population initialization = = = = = = = = = = = = = = = = = = = = = = = = = = = = total_op_num = sum (num_op); chroms=initialization(num_op,num_job,total_op_num,sizepop,operation_machine,operation_time); [Z,~,~]=fitness(chroms,num_machine,e,num_job,num_op); % % = = = = = = = = = = = = = = = = = = = = = = = = = = = = iterative process = = = = = = = = = = = = = = = = = = = = = = = = = = = = =for gen=1:MAXGEN
    fprintf('Current iteration number:'Chroms_new =selection(chroms,Z,Ps); % chroms_new=crossover(chroms_new,Pc,total_op_num,num_job,num_op); Chroms_new =mutation(chroms_new, total_OP_num,Pm,num_machine,e,num_job,num_op, operation_MACHINE,operation_time); % Calculate the fitness of individuals after selecting crossover mutation [Z_new,~,~]= FITNESS (CHROMS_new, NUM_MACHINE, E, NUM_JOB, NUM_op); % Select a better sizePOP from the original population and the genetically modified population according to fitness [chroms,Z,chrom_best]=update_chroms(chroms,chroms_new,Z,Z_new, sizePOP); % Recorded the optimal fitness and average fitness trace(1, gen)=Z(1);       
    trace(2, gen)=mean(Z); % Update global optimal fitnessif gen==1 || MinVal>trace(1,gen)
        MinVal=trace(1,gen);
function [Z,machine_weight,pvals] = fitness(chroms,num_machine,e,num_job,num_op)
sizepop=size(chroms,1);
pvals=cell(1,sizepop);
Z1=zeros(1,sizepop); Z2=Z1; total_op_num=sum(num_op); % Total number of ordersfor k=1:sizepop
    chrom=chroms(k,:);
    machine=zeros(1,num_machine); % job=zeros(1,num_job); Machine_time =zeros(1,num_machine); % Calculate the actual processing time of each machine pval=zeros(2,total_op_num); % Record the start and end time of each processfor i=1:total_op_num % The machine time is greater than the workpiece timeif machine(chrom(total_op_num+i))>=job(chrom(i))
            pval(1,i)=machine(chrom(total_op_num+i)); 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,i)=machine(chrom(total_op_num+i)); % Record artifact end time % Machine time is less than artifact timeelse
            pval(1,i)=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(2,i)=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); Makespan % machine_weight=machine_time/sum(machine_time); Machine_weight =machine_time; Z2(k)=max(machine_weight)-min(machine_weight); pvals{k}=pval; end % min_makespan=min(Z1); % Max_makespan = Max (Z1); % min_weight=min(Z2); % max_weight= Max (Z2); % Z=e*((Z1-min_makespan)./(max_makespan-min_makespan))+(1-e)*((Z2-min_weight)./(max_weight-min_weight)); % Calculate the fitness Z=e*Z1+(1-e)*Z2;

function [ chroms_new] = crossover(chroms,Pc,total_op_num,num_job,num_op)
size_chrom=size(chroms,1); Chroms_new =chroms; %% cross operation for process codefor i=1:2:size_chrom- 1 
    ifPc>rand % parent1=chroms(I,:); parent2=chroms(i+1, :); Job=randperm(num_job); J1=Job(1:round(num_job/2));
        J2=Job(length(J1)+1:end); % Offspring chromosome CHILD1 =parent1; child2=parent2; op_p1=[]; op_p2=[];for j=1Op_p1 =[op_p1,find(parent1(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); % offspring1Genes of J2 fragment exchange, genes of machine code corresponding position, genes of time code corresponding position 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); % offspring2Similarly 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(i,:)=child1;
        chroms_new(i+1,:)=child2; End end %% Machine code oriented crossover operationfor k=1:2:size_chrom- 1
    if Pc>rand
        parent1=chroms_new(k,:);
        parent2=chroms_new(k+1, :); child1=parent1; child2=parent2; % randomly generated to be the same length as the chromosome0.1Sequence rand0_1 = randi ([0.1].1,total_op_num);
        for n=1:num_job
            ind_0=find(rand0_1(num_op(n)*(n- 1) +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));
            end
        end
        chroms_new(k,:)=child1;
        chroms_new(k+1,:)=child2;
    end
end
end
Copy the code

4. Operation results

Matlab version and references

1 matlab version 2014A

[1] Yang Baoyang, YU Jizhou, Yang Shan. Intelligent Optimization Algorithm and Its MATLAB Example (2nd Edition) [M]. Publishing House of Electronics Industry, 2016. [2] ZHANG Yan, WU Shuigen. MATLAB Optimization Algorithm source code [M]. Tsinghua University Press, 2017.