### [job shop scheduling] solve the replacement flow shop scheduling problem based on Matlab genetic algorithm [including MATALB source code phase 176]

Matlab scientific research 2021-08-10 09:14:33 阅读数:318

job shop scheduling solve replacement

## One 、 background  Algorithm design
( One )
Suppose that the machining sequence of the workpiece on the machine is the same , At the same time, it is assumed that each workpiece is ready , As soon as the machine starts, it goes into production , The commencement time is 0, Then the maximum completion time is equal to the maximum process time . meanwhile 3 Flow shop scheduling with more than one machine is NP Difficult problem , So this paper only considers 2 platform 、3 The situation of this machine , solve 3 Artificial intelligence algorithms can also be used to solve the problems of more than one machine , The quality of the solution is higher , However, this kind of algorithm needs good software programming ability , Therefore, this paper does not explore .n A workpiece is in m The processing sequence on this machine is the same . The processing time of the workpiece on the machine is given . The goal of the problem is to find n The maximum completion time of a workpiece on each machine is equal to the maximum process time . This pipeline scheduling problem should meet the following two constraints , So that all
Take as little time as possible ：
1、 Workpiece constraints
Each workpiece is machined exactly once on each machine , Each workpiece is processed in the same sequence on each machine . No loss of generality , It is assumed that each workpiece is processed according to the machine
device 1 to m Process in the order of . The processing time of each workpiece on each machine is known .
2、 Machine constraints
Each machine can process at most one workpiece at any time , The order of each workpiece processed by each machine is the same .
The essence of permutation pipeline scheduling problem is how to adjust the sequence of processing jobs , The problem of improving the utilization of machines , That is, the more machine grabs are being processed at the same time , The greater the utilization rate of the machine, according to this principle , We arrange according to the following rules
Machining sequence of workpiece :
(l) In front, the machining time is short 、 The workpiece that takes a long time to be processed by the later machine , Before the sequence . In this way, the machine behind can work as soon as possible , And the machine behind doesn't need to wait ,
(2) Workpieces with average machining time and long machining time , In the middle of the sequence . This will allow each machine to operate in the medium term .
(3〕 The front processing time is long , Add one after 〔 The last women's volleyball team with a short time is at the end of the sequence . This allows the machine in front to “ Delay ” to be finished , The back machine will be finished as soon as possible .

## Two 、 Source code

``````function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P)
% Input parameter list
% M Number of genetic evolution iterations
% N Population size ( Take even number )
% Pm Mutation probability
% T m×n Matrix , Storage m Pieces n Processing time of one operation
% P 1×n Vector ,n In one process , Number of machine tools per process
% Output parameter list
% Zp The most optimal Makespan value
% Y1p In the optimal scheme , Start time of each process of each workpiece , You can draw a Gantt chart based on it
% Y2p In the optimal scheme , The end time of each process of each workpiece , You can draw a Gantt chart based on it
% Y3p In the optimal scheme , Machine number used in each process of each workpiece
% Xp The value of the optimal decision variable , The decision variable is a real coded m×n matrix
% LC1 Convergence curve 1, Record of optimal individual fitness of each generation
% LC2 Convergence curve 2, Record of average fitness of each generation
% Last , The program will also draw three pictures ： Two convergence curves and Gantt Chart （ Scheduling sequence diagram of each workpiece ）
% First step ： Variable initialization
[m,n]=size(T);%m Is the total number of workpieces ,n Is the total number of processes
Xp=zeros(m,n);% Optimal decision variables
LC1=zeros(1,M);% Convergence curve 1
LC2=zeros(1,N);% Convergence curve 2
% The second step ： Random generation of the initial population
farm=cell(1,N);% The cell structure is used to store the population
for k=1:N
X=zeros(m,n);
for j=1:n
for i=1:m
X(i,j)=1+(P(j)-eps)*rand;
end
end
farm{k}=X;
end
counter=0;% Set the iteration counter
while counter<M% The stop condition is that the maximum number of iterations is reached
% The third step ： cross
newfarm=cell(1,N);% The cross generated new species groups exist in
Ser=randperm(N);
for i=1:2:(N-1)
A=farm{Ser(i)};% Parent individual
Manner=unidrnd(2);% Randomly select the crossing mode
if Manner==1
cp=unidrnd(m-1);% Randomly choose the intersection
% Parent Gemini single point intersection
a=[A(1:cp,:);B((cp+1):m,:)];% Offspring individuals
b=[B(1:cp,:);A((cp+1):m,:)];
else
cp=unidrnd(n-1);% Randomly choose the intersection
b=[B(:,1:cp),A(:,(cp+1):n)];
end
newfarm{i}=a;% The offspring after crossing are stored in newfarm
newfarm{i+1}=b;
end
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
```

## 3、 ... and 、 Running results edition ：2014a