The background,





Algorithm design

(一)

Assuming that the processing sequence of the workpiece on the machine is the same, and assuming that all the workpiece is ready, the machine will be put into production as soon as it starts, and the start time is 0, the maximum completion time is equal to the maximum process time. At the same time, flow shop scheduling with more than 3 machines is NP difficult problem, so this paper only considers the situation of 2 and 3 machines. Artificial intelligence algorithm can also be used to solve the problem with more than 3 machines, and the solution quality is higher, but because this kind of algorithm requires good software programming ability, so this paper does not explore. N workpieces are processed in the same order on m machines. The processing time of the workpiece on the machine is given. The goal of the problem is to find the maximum completion time of n pieces per machine equal to the maximum process time. This kind of pipeline scheduling problem must satisfy the following two constraints on the premise of processing all

As little time as possible is spent on the artifacts:

1, workpiece constraints

Each workpiece is processed exactly once on each machine, and each workpiece is processed in the same order on each machine. Without loss of generality, it is assumed that each workpiece press the machine

Machine 1 to M in the order of processing. The processing time of each workpiece on each machine is known.

2. Machine constraints

Each machine processes no more than one workpiece at any time, and each machine processes each workpiece in the same order.

The essence of the displacement line scheduling problem is how to adjust the sequence of the processed workpiece and improve the utilization rate of the machine, that is, the more the number of the machine being processed at the same time, the larger the utilization rate of the machine. According to this principle, we arrange according to the following rules

Processing sequence of workpiece:

(l) The workpiece with short processing time in front and long processing time in back shall be arranged in front of the sequence. This allows the following machines to work as quickly as possible, and the latter machines do not have to wait.

(2) The workpiece with relatively average processing time and longer processing time is arranged in the middle of the sequence. This will allow each machine to be operational in the medium term.

(3) the front processing time is longer, after the addition of a short time on the female row in the tail of the sequence. This allows the front machine to be “delayed” and the back machine to be completed as quickly as possible.

Ii. Source code

Function [Zp, Y1p Y2p Y3p, Xp, LC1, LC2] = JSPGA (M, N, Pm, T, P) % input parameter list genetic evolution iterations % N % M population size Pm mutation probability (even) % % T M * N matrix, Store the processing time % P of M workpieces and N processes1In n processes, the number of machine tools in each process % output parameter list % Zp optimal Makespan value % Y1p The start time of each process of each workpiece in the optimal scheme can be used to draw gantt chart % Y2p optimal scheme, the end time of each process of each workpiece, According to it, we can draw the value of the optimal decision variable of machine number % Xp for each workpiece in each procedure in the optimal scheme % Y3p of Gantt chart. The decision variable is a real coded M × N matrix % LC1 convergence curve1% LC2 convergence curve of optimal individual fitness of each generation2Finally, the program will draw three pictures: two convergence curves and Gantt diagram (scheduling sequence diagram of each workpiece) % First step: variable initialization [m,n]=size(T); %m is the total number of jobs,n is the total number of jobs Xp= Zeros (m,n); % Optimal decision variable LC1=zeros(1,M); % convergence curve1
LC2=zeros(1,N); % convergence curve2% step 2: Randomly generate initial population farm=cell(1,N); Use cell structure to store populationfor 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; % sets the iteration counterwhileCounter <M% stop condition to reach the maximum number of iterations %1,N); Ser= Randperm (N);for i=1:2:(N- 1) A=farm{Ser(i)}; % parent person Manner=unidrnd(2); % Select the crossover mode at randomif Manner==1
            cp=unidrnd(m- 1); % random crossover % parental single point crossover a=[a (1:cp,:); B((cp+1):m,:)]; % progenitor b=[b (1:cp,:); A((cp+1):m,:)];
        else
            cp=unidrnd(n- 1); % select intersections b=[b (:,1:cp),A(:,(cp+1):n)]; end newfarm{i}=a; % Crossed children are saved to newfarm newfarm{I +1}=b;
    end
Copy the code

3. Operation results

Fourth, note

Version: 2014 a