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

Four 、 remarks

edition ：2014a