[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

本文一共[544]字,预计阅读时长:1分钟~
job shop scheduling solve replacement

One 、 background

 Insert picture description here
 Insert picture description here
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

 Insert picture description here

Four 、 remarks

edition :2014a

版权声明:本文为[Matlab scientific research]所创,转载请带上原文链接,感谢。 https://car.inotgo.com/2021/08/20210810091259273A.html