A list,
Job Shop Scheduling (JSP) is one of the most classic NP-hard problems. Its application fields are extremely wide, involving aircraft carrier scheduling, airport aircraft scheduling, port and dock cargo ship scheduling, automobile processing assembly line and so on.
A processing system has M machines and requires N jobs to be processed. Among them, job I contains the number of procedures for Li. , then L is the total working number of the task set. Among them, the processing time of each process has been determined, and each operation must be processed in accordance with the sequence of the process. The task of scheduling is to arrange the processing scheduling of all jobs, so that the performance index can be optimized when the constraints are satisfied.
Job shop scheduling needs to consider the following constraints:
Cons1: Each process is processed on the designated machine and can only begin after the completion of its previous process;
Cons2: A machine can process only one job at a time;
Cons3: Each job can only be processed 1 time on 1 machine;
Cons4: The working sequence and processing time of each job are known and will not change with the change of processing sequencing.
Problem instances
The following is an example of the job-shop scheduling problem, where each process is marked with a pair of values (m, P), where M means that the current process must be processed on the MTH machine, and P means the processing time required by the MTH machine to process the current process. (Note: Machine and job numbers start from 0)
Jop0 = [(0, 3), (1, 2), (2)]
Jop1 = [(0, 2), (2, 1), (1, 4)]
Jop2 = [(1, 4), (2, 3)]
In this example, job JOP0 has three processes: its first process is labeled (0,3), which means that the first process must be processed on machine 0 and requires 3 units of processing time; Its second process is marked with (1,2), which means that the second process must be processed on the first machine, and requires 2 units of processing time; Same thing with the rest. In total, there are eight processes in this example.
A feasible solution of the problem is that L= a permutation of 8 process start times, which satisfies the constraints of the problem. Here is an example of a possible solution (note: this solution is not optimal) :
Leapfrog algorithm (SFLA) is a new post-heuristic group evolution algorithm with high computational performance and excellent global search ability. In this paper, the basic principle of hybrid leapfrog algorithm is described, and an improved leapfrog algorithm based on threshold selection strategy is proposed to solve the problem that individual spatial position changes greatly before and after update operation caused by local update strategy, which reduces the convergence speed. The individual spatial differences are reduced and the performance of the algorithm is improved through the policy of not updating individual components that do not meet the threshold conditions. Numerical experiments show that the improved algorithm is effective and the threshold parameters of the improved algorithm are calibrated
Characteristics SFLA was first proposed by Eusuff and Lansey in 2003 to solve combinatorial optimization problems. As a new biology-imitating intelligent optimization algorithm, SFLA combines the meme algorithm based on meme evolution (MA, Memeticalgorithm and PSO (Particle swarm optimization) 2 population intelligent optimization algorithm. The algorithm has the characteristics of simple concept, less parameters to adjust, fast computing speed, strong global search ability and easy to implement. Hybrid leapfrog algorithm is mainly used to solve multi-objective optimization problems, such as water resource allocation, bridge pier maintenance, workshop operation flow arrangement and other practical engineering applications.
The idea of the leapfrog algorithm is that a group of frogs live in a wetland. There are many stones scattered in the wetland, and the frog jumps by looking for different stones to find more food. Information is exchanged between individual frogs through cultural exchange. Each frog has its own culture. The culture of each frog is defined as a solution to the problem. The entire frog population of the wetland is divided into different subgroups, each with its own culture, performing a local search strategy. Each individual in a subgroup has its own culture that influences, is influenced by, and evolves as the subgroup evolves. When the subgroups evolve to a certain stage, each subgroup will exchange ideas (global information exchange) to achieve the hybrid operation between the subgroups, until the set conditions are satisfied.
Parameters of mathematical model Algorithm Like other optimization algorithms, SFLA also has some necessary calculation parameters, including F: number of frogs; M: The number of ethnic groups; N: the number of frogs in the population; Smax: maximum allowed runout step. Px: global best solution; Pb: local best solution; Pw: local worst solution; Q: The number of frogs in the subgroup; LS: local metaevolution times and SF: global thought exchange times. For the frog population, the solution with the best global fitness is U g. For each subpopulation, the solution with the best fitness was expressed as UB, and the solution with the worst fitness was expressed as UW. Firstly, a local search was performed for each subpopulation, that is, the frog with the worst fitness in the subpopulation was updated. The update strategy was as follows: frog update distance Ds= RAND ()*(Pd-PW) (1) newDw=oldPw+Ds (-dmax ≦Ds≦Dmax) (2) Ds represents the adjustment vector of the individual frog, and Dmax represents the maximum stride length that the individual frog is allowed to change. Uw=[1 3 5 4 2], UB=[2 1 5 3 4], Dmax =3, rand=0.5, U q(1) =1+min{int[0.5 × (2−1)],3}=1; U q (2) = 3 + Max {int [0.5 x (1-3)], – 3} = 2; A new solution U q=[1 2 5 4 3] can be obtained after updating the policy by following the same operation.
Procedure Global search procedure step L initializes. Determine the number of frogs in the group, the population, and the number of frogs in each population. Step 2 Randomly generate the initial population of frogs and calculate the fitness values of each frog. Step 3 Sort the frogs in descending order according to the size of adaptation value, record the best solution Px, and divide the frog population into groups. Divide F frogs into m groups Y, Y, Y… , Y, each group contains n frog, making Yk = [X (j), f (j) | X (j) = X (k + m * (j – 1), f (j) = f (k + m * (j – 1), j = 1,…, n, k = 1,…, m). Here X (j) represents the JTH frog in the frog group, and f(j) represents the objective function value of the JTH frog. Step 4 According to the SFLA algorithm formula, meta-evolution was carried out in each population. Step 5 Mix the groups. After a round of meta-evolution for each population, the frogs in each population were sorted and divided again, and the global best solution Px was recorded. Step 6 Check and calculate the stop conditions. If the convergence conditions are met, stop the algorithm execution. Otherwise, go to Step 3. In general, the algorithm is stopped if the best solution does not improve significantly after several consecutive global ideas are exchanged. In some cases, the maximum number of function evaluations can also be used as the stop criterion of the algorithm. Step 4-1 Set im=O, where IM is the counter of the group. Used to compare with the total population m. Let iN=0, where iN is the counter of local evolution, used to compare with Ls. Step 4-2 According to Formula (1), select Q frogs from l,, 1 population into subpopulation, determine Pb and Pw and set im= IM +1. Step 4-3 Set iN=iN+1. Step 4-4 Improve the position of the worst frog in the subgroup according to Equations (2) and (3). Step 4-5 If step 4-4 improves the position of the worst frog (solution), replace the position of the worst frog with the newly generated position. Otherwise, Px is used to replace PB in Formula (2) and update the position of the worst frog. Step 4-6 If step 4-5 does not improve the position of the worst frog, randomly create a frog in any position in the wetland to replace the worst frog. Step 4-7 If iN
Ii. Source code
CLC clear all close all % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % problem: N workpieces,M machines do shape flow shop scheduling problem % number of workpieces N=20, number of machines M=10, the optimal solution of finite number fval=14.9263,
% x = [16 4 18 15 12 11 2 1 6 7 3 5 20. %10 8 14 13 19 17 9]
N = 20% Number of jobs (solution vector length) M =10% number of machines rand('state',N+M); % T = rand(M,N); % generation time matrix, row M1 is the number of machines, column N is the number of jobs rand('state',sum(100*clock)); Seed recovery randomly % % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % popsize = necessary parameters50; % population size maxgen =50; % Maximum evolution algebra method =4% method selection,1- Pseudoparallel niche Adaptive Genetic algorithm (PPNSA)2- Hybrid frog jump algorithm + mutation operator (SFLA+MO) %3- Batch leapfrog algorithm (BFLA), an improved algorithm % of SFLA4-ppNSA + perturbation operator (last selection algorithm, convergence speed, easy to jump out of the local minimum) %5-sfla +MO+ perturbation operator (secondary algorithm, fast convergence, the most easy to fall into local minimum) %6-bfla + perturbation operator (preferred algorithm, convergence speed, may fall into local minimum) type =1; % initialization mode,1- Random initialization (default) %2Heuristic initialization % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % function call X, fval, F = SFLA(T,popsize,maxgen,method,type); Shuffled Frog-leaping (SFLA) input parameters: % T - time matrix % POPSize - Population size % MaxGen - Maximum evolution algebra % Method - Method selection1- Pseudoparallel niche Adaptive Genetic algorithm (PPNSA)2- Hybrid frog jump algorithm + mutation operator (SFLA+MO) %3- Batch leapfrog algorithm (BFLA), an improved algorithm % of SFLA4-ppNSA + perturbation operator (last selection algorithm, convergence speed, easy to jump out of the local minimum) %5-sfla +MO+ perturbation operator (secondary algorithm, fast convergence, the most easy to fall into local minimum) %6-bfla + perturbation operator (preferred algorithm, convergence speed, may fall into local minimum) % type - initialization mode,1- Random initialization (default) %2- Heuristic initialization % output parameter: The corresponding solution of % X - optimal fitness % fval - optimal fitness value % F - optimal, average, worst fitness % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % results drawing figure (1)
FigSche(X,T);
figure(2);
plot(1:maxgen,F,'-'); grid on;
legend('the best'.'average'.'worst'.3);
xlabel('Evolutionary algebra'); ylabel('Fitness');
set(gcf,'position'[700 200 500 400])
set(gca,'XLim'[1 maxgen]);
title([Number of Jobs:,num2str(N),'Machine number :',num2str(M),', optimal value :',num2str(fval)]);
Copy the code3. Operation results
Fourth, note
Version: 2014 a