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

The leapfrog algorithm is based on the idea that there are a group of frogs living 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.

The global search procedure step L is initialized. 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

CLC clear all close all % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % problem: When the number of jobs N=20 and the number of machines M=10, the optimal solution of finite number fval=14.9263, % x = [16 4 18 15 12 11 2 16 7 3 5 20... % 10 8 14 13 19 17 9] N = 20% M = 10% machine count rand('state',N+M); % T = rand(M,N); Rand ('state',sum(100*clock)); Seed recovery randomly % % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % required parameter popsize = 50; % population size maxgen = 50; % maximum evolutionary algebraic method = 4% method selection,1 - pseudoparallel niche adaptive genetic algorithm (PPNSA) % 2 - mixed frog jump algorithm + mutation operator (SFLA+MO) % 3 - batch frog jump algorithm (BFLA), is an improved SFLA algorithm % 4 - PPNSA+ perturbation operator (last selection algorithm, convergence speed, easy to jump out of local minimum) % 5-sfla +MO+ perturbation operator (secondary selection algorithm, fast convergence speed, most likely to fall into local minimum) % 6-bfla + perturbation operator (preferred algorithm, convergence speed, may fall into local minimum) type = 1; % initialization, 1 - random initialization (the default) % % 2 - heuristic initialization -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % function calls [X,fval,F] = SFLA(T,popsize,maxgen,method,type); Shuffled Frog-leaping (SFLA) % T - time matrix % POPSize - population size % MaxGen - Maximum evolution algebra % method - Method selection,1 - pseudoparallel niche adaptive genetic algorithm (PPNSA) % 2 - hybrid leapfrog algorithm + mutation operator (SFLA+MO) % 3 - Batch leapfrog algorithm (BFLA), is the improved SFLA algorithm % 4-PPNSA + disturbance operator (last selection algorithm, convergence speed, is easy to jump out of the local minimum) % 5-Sfla +MO+ disturbance operator (secondary selection algorithm, convergence speed is fast, is easy to fall into the local minimum) % 6 - BFLA+ perturbation operator (preferred algorithm, convergence rate medium, may fall into local minimum) % type - initialization mode,1 - random initialization (default setting) % 2 - heuristic initialization % Output parameters: The corresponding solution of % X - optimal fitness % fval - optimal fitness value % F - optimal, average, worst fitness % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % result drawing figure (1) FigSche (X, T); figure(2); plot(1:maxgen,F,'.-'); grid on; Legend (' optimal ',' average ',' worst ',3); Xlabel (' Evolution algebra '); Ylabel (' fitness '); set(gcf,'position',[700 200 500 400]) set(gca,'XLim',[1 maxgen]); Title ([' work packages: ', num2str (N), 'count: the machine', num2str (M), ', the optimal value: ', num2str (fval)]);Copy the code

Complete code or simulation consulting to add QQ1575304183