### [workshop scheduling] solving production scheduling problems based on MATLAB particle swarm optimization algorithm [including Matlab source code phase 412]

Matlab scientific research 2021-08-10 09:14:42 阅读数:946

workshop scheduling solving production scheduling

## One 、 Introduction to production scheduling

Job shop scheduling refers to a given machining task , According to the existing production conditions , Allocate limited system resources , Arrange the processing steps of the product , Make a performance index optimal . In the actual production process , The constraints involved mainly include ： The processing capacity of the machine , Number of machines , Number of products processed , Processing sequence of products , Delivery time of products , Quantity of raw materials for production , Cost limit , Machine fault , Production date, etc . The performance indexes considered mainly include ： Shortest product delivery time , Minimum processing time , The shortest production cycle , Least cost , The highest equipment utilization , The actual production process generally needs to balance multiple performance indexes [1].

## Two 、 Introduction to particle swarm optimization

Particle swarm optimization (PSO) It is a numerical optimization algorithm based on swarm intelligence , By social psychologists James Kennedy And Electrical Engineer Russell Eberhart On 1995 in . since PSO Since the birth of , It has been improved in many ways , This part will introduce the basic principle and process of particle swarm optimization .
1.1 Particle swarm optimization
Particle swarm optimization (PSO) It is a population intelligent algorithm , Its inspiration comes from the flock of birds or the school of fish , It is used to solve nonlinear problems in many fields of science and engineering 、 Nonconvex or combinatorial optimization problems .

1.1.1 Algorithmic thought
Many birds are social , And different bird groups are formed for various reasons . Birds may be of different sizes , Appear in different seasons , It may even consist of different species in the group that can cooperate well . More eyes and ears mean more opportunities to find food and predators in time . Birds are always good for the survival of their members in many ways ：
foraging ： Sociobiologists E.O.Wilson say , At least in theory , Individual members of the group can benefit from other members' discoveries and previous experience in looking for food [1]. If a flock of birds have the same food source , Then some species of birds will gather together in a non competitive way . such , More birds can take advantage of other birds' discovery of food locations .
Against predators ： Birds have many advantages in protecting themselves from predators .
More ears and eyes mean more opportunities to find predators or any other potential danger ;
A flock of birds may confuse or suppress predators through siege or agile flight ;
In groups , Mutual warning can reduce the danger of any bird .
aerodynamics ： When birds fly in groups , They often arrange themselves in a specific shape or formation . The number of birds in the flock is different , Each bird produces a different air flow when it stirs its wings , This will lead to changes in wind patterns , These formations will make full use of different typing , So that birds in flight can use the surrounding air in the most energy-saving way .
The development of particle swarm optimization needs to simulate some advantages of bird swarm , However , In order to understand an important property of swarm intelligence and particle swarm optimization , It is worth mentioning some shortcomings of birds . When birds flock , It also brings them some risks . More ears and eyes means more wings and mouth , This leads to more noise and movement . under these circumstances , More predators can locate birds , A continuing threat to birds . A larger group will also need more food , This leads to more food competition , It is possible to eliminate some weaker birds in the group . What needs to be pointed out here is ,PSO There is no disadvantage of simulating bird group behavior , therefore , It is not allowed to kill any individual during the search , In genetic algorithm , Some weaker individuals die . stay PSO in , All individuals will survive , And strive to become stronger throughout the search process . In particle swarm optimization , The improvement of potential solution is the result of cooperation , In evolutionary algorithms, it is because of competition . This concept makes swarm intelligence different from evolutionary algorithms . In short , In evolutionary algorithms , Each iteration has a new population evolution , In swarm intelligence algorithms , Each generation has individuals who make themselves better . The identity of an individual does not change with iterations .Mataric[2] The following flock rules are given ：

Secure roaming ： When birds fly , There is no collision with each other or with obstacles ;
Dispersed ： Every bird keeps a minimum distance from other birds ;
polymerization ： Each bird will also keep a maximum distance from other birds ;
Go home ： It is possible for all birds to find food sources or nests .
When designing particle swarm optimization , These four rules are not used to simulate the group behavior of birds . stay Kennedy and Eberhart The basic particle swarm optimization model is developed , Yes agent The movement of does not follow the rules of safe roaming and dispersion . let me put it another way , In the motion process of basic particle swarm optimization algorithm , Allow the agents in the particle swarm optimization algorithm to be as close to each other as possible . Aggregation and homing are effective in particle swarm optimization model . In particle swarm optimization , The agent must fly in a specific area , To maintain maximum distance from any other agent . This is equivalent to the whole process , The search always stays within or at the boundary of the search space . The fourth rule , Homing means that any agent in the group can achieve global optimization .

stay PSO During the development of the model ,Kennedy and Eberhart Five basic principles are proposed to judge whether a group of agents is a group ：

Nearby principle ： The agent group should be able to perform simple spatial and temporal calculations ;
Quality principles ： Agent groups can respond to quality factors in the environment ;
Multi response principle ： The agent group should not engage in activities in too narrow channels ;
Stability principle ： Agent groups cannot change their behavior patterns every time the environment changes ;
The principle of adaptability ： When the cost of calculation is small , Agent groups can change their behavior patterns .

1.1.2 Particle swarm optimization process
Considering these five principles ,Kennedy and Eberhart A method for function optimization is developed PSO Model . In particle swarm optimization , Using the method of random search , Using swarm intelligence to solve . let me put it another way , Particle swarm optimization (PSO) is a population intelligent search algorithm . This search is done by a set of randomly generated possible solutions . This set of possible solutions is called a group , Every possible solution is called a particle .
In particle swarm optimization , Particle search is influenced by two learning methods . Every particle is learning from other particles , At the same time, I also learn my own experience in the process of sports . Learning from others can be called social learning , Learning from one's own experience can be called cognitive learning . As a result of social learning , The particle stores in its memory the best solution accessed by all particles in the group , We call it gbest. Through cognitive learning , The particle stores in its memory the best solution it has ever visited , be called pbest.

The change in the direction and size of any particle is determined by a factor called velocity , Speed is the rate of change of position relative to time . about PSO, Iterating over time . such , For particle swarm optimization , Velocity can be defined as the rate of change of position relative to iteration . As the iteration counter unit increases , Speed v Dimension and position of x identical .

about D Dimensional search space , In time step t The second in the next group ith A particle consists of D Dimension vector x i t = ( x i 1 t , ⋯ , x i D t ) T x_i^t = {(x_{i1}^t, \cdots ,x_{iD}t)T}xit​=(xi1t​,⋯,xiDt​)T To express , Its speed is determined by another D Dimension vector v i t = ( v i 1 t , ⋯ , v i D t ) T v_i^t = {(v_{i1}^t, \cdots ,v_{iD}t)T}vit​=(vi1t​,⋯,viDt​)T Express . The first ith The location of the optimal solution visited by particles is p i t = ( p i 1 t , ⋯ , p i D t ) T p_i^t = {\left( {p_{i1}^t, \cdots ,p_{iD}^t} \right)^T}pit​=(pi1t​,⋯,piDt​)T Express , The index of the optimal particle in the population is “g”. The first ith The velocity and position of particles are updated by the following formula respectively ：
v i d t + 1 = v i d t + c 1 r 1 ( p i d t − x i d t ) + c 2 r 2 ( p g d t − x i d t ) (1) v_{id}^{t + 1} = v_{id}^t + {c_1}{r_1}\left( {p_{id}^t - x_{id}^t} \right) + {c_2}{r_2}\left( {p_{gd}^t - x_{id}^t} \right)\tag 1vidt+1​=vidt​+c1​r1​(pidt​−xidt​)+c2​r2​(pgdt​−xidt​)(1)

x i d t + 1 = x i d t + v i d t + 1 (2) x_{id}^{t + 1} = x_{id}^t + v_{id}^{t + 1}\tag 2xidt+1​=xidt​+vidt+1​(2)

among d=1,2,…,D Dimensionality ,i=1,2,…,S Index particles ,S It's the size of the group .c1 and c2 Constant , Cognitive and social scaling parameters, respectively , Or simply called acceleration coefficient .r1 and r2 Is to satisfy uniform distribution [0,1] Random number between . The above two formulas update each dimension of each particle separately , The only connection between different dimensions in the problem space is introduced through the objective function , That is, the best position found so far gbest and pbest[3].PSO The algorithm flow of is as follows ：
1.1.3 Interpret and update the equation
Speed update equation （1） The right side of the consists of three parts 3：
The speed of the previous time v, It can be considered as a momentum term , Used to store the previous direction of motion , The purpose is to prevent particles from changing direction violently .
The second is the cognitive or self part , Through this , The particle's current position moves to its own best position , So throughout the search , Particles will remember their best position , To avoid wandering around . What needs to be noted here is ,pidt-xidt It's a direction from xidt To pidt Vector , So as to attract the current position to the best position of the particle , The order of the two cannot be changed , Otherwise, the current position will be far away from the best position .
The third is the social part , Responsible for sharing information through groups . Through this item , The particle moves towards the best individual in the group , That is, each individual learns from other individuals in the group . Again, the two should be pgbt-xidt.
It can be seen that , Cognitive scale parameters c1 What is adjusted is the maximum step size of the particle in its best position direction , And the social scale parameter c2 It adjusts the maximum step size in the direction of the globally optimal particle . chart 2 The typical geometry of particle motion in two-dimensional space is given .

chart 2 Geometric description of particle movement in particle swarm optimization

As can be seen from the renewal equation ,Kennedy and Eberhart Of PSO The design follows PSO The five basic principles of . In the process of particle swarm optimization , stay d A series of time steps are calculated in dimensional space . At any time step , All species follow gbest and pbest The guiding direction of , That is, the population responds to quality factors , So as to follow the quality principle . Because there are uniformly distributed random numbers in the velocity renewal equation r1 and r2, stay pbest and gbest The current position between is randomly assigned , This proves the diversity of response principles . In the process of particle swarm optimization , Only if the particle swarm starts from gbest When better information is received in , Random motion will occur , The stability principle of particle swarm optimization process is proved . Population in gbest Change as you change , Therefore, follow the principle of adaptability .
1.2 Parameters in particle swarm optimization
The convergence speed and optimization ability of any population-based algorithm are affected by its parameter selection . Usually , Because the parameters of these algorithms are highly dependent on the problem parameters , Therefore, it is impossible to give general suggestions on the parameter setting of these algorithms . however , Existing theories and / Or experimental research , The general range of parameter values is given . Similar to other population-based search algorithms , Because there are random factors in the search process r1 and r2, So universal PSO Parameter adjustment has always been a challenging task .PSO The base version of requires only a few parameters . This chapter only discusses [4] Introduced in PSO Parameters of the basic version .

A basic parameter is population size , It is usually set empirically according to the number of decision variables in the problem and the complexity of the problem . General advice 20-50 A particle .

Another parameter is the scaling factor c1 and c2. As mentioned earlier , These parameters determine the particle step size in the next iteration . in other words ,c1 and c2 Determines the velocity of the particles . stay PSO In the base version of , choice c1=c2=2. under these circumstances , The particle s The increase in speed is uncontrolled , This is conducive to faster convergence , But it is not conducive to making better use of the search space . If we make c1=c2>0, Then the particles will attract pbest and gbest Average value .c1>c2 Setting is conducive to multimodal problems , and c2>c1 Conducive to single-mode problems . During search ,c1 and c2 The smaller the value of , The smoother the particle trajectory , and c1 and c2 The greater the value of , The motion of particles is becoming more and more intense , The more acceleration . Researchers have also proposed adaptive acceleration coefficients [5].
The stopping criterion is not only a parameter of particle swarm optimization , It is also a parameter of any population-based meta heuristic algorithm . Common stopping criteria are usually based on the maximum number of function evaluations or iterations , The number of times is proportional to the time spent by the algorithm . A more effective stopping criterion is the search ability based on the algorithm , If an algorithm does not significantly improve the solution within a certain number of iterations , Then you should stop searching .

## 3、 ... and 、 Partial source code

clear;
w=3;% The number of times the program runs
genn=50; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Max algebra
PS=50; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Population size
e=0.4; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PSO Algorithm inertia factor
ICPSOm=zeros(1,w);
ICPSOOptimy=cell(w,1);
CPSOm=zeros(1,w);
CPSOOptimy=cell(w,1);
T=[ 54 79 16 66 58
83 3 89 58 56
15 11 49 31 20
71 99 15 68 85
77 56 89 78 53
36 70 45 91 35
53 99 60 13 53
38 60 23 59 41
27 5 57 49 69
87 56 64 85 13
76 3 7 85 86
91 61 1 9 72
14 73 63 39 8
29 75 41 41 49
12 47 63 56 47
77 14 47 40 87
32 21 26 54 58
87 86 75 77 18
68 5 77 51 68
94 77 40 31 28];
pt=T';
global v
for v=1:w
[opy,optimya]=ICPSOflowshop(pt,genn,PS,e);
ICPSOm(v)=opy;
%CPSOSE{v,1}=opx;
%CPSOAvgen{v,1}=avgena;
ICPSOOptimy{v,1}=optimya;
[opy,optimyb]=copsoflowshop(pt,genn,PS,e);
CPSOm(v)=opy;
%PSOSE{v,1}=opx;
%PSOAvgen{v,1}=avgen;
CPSOOptimy{v,1}=optimyb;
CPSOm =
1294 1297 1297 1297 1297 1296 1278 1297 1297 1297
CPSOminm =
1278
CPSOmaxm =
1297
CPSOaverage =
1.2947e+003
CPSOstd =
5.9451
??? Undefined variable 'CPSOSE' or class 'CPSOSE'.
Error in ==> C:\MATLAB6p5p1\work\CPSO flow-shop of subswarm\copsomain.m
On line 61 ==> see=CPSOSE{CPSOh(1),1};
fschange('C:\MATLAB6p5p1\work\CPSO flow-shop of subswarm\copsomain.m');
clear copsomain
fschange('C:\MATLAB6p5p1\work\CPSO flow-shop of subswarm\copsomain.m');
clear copsomain
copsomain
CPSOm =
1297 1297 1297 1297 1297 1297 1295 1279 1297 1297
CPSOminm =
1279
CPSOmaxm =
1297
CPSOaverage =
1295
CPSOstd =
5.6569
CPSOm =
1297 1289 1278 1297 1278 1297 1278 1297 1297 1283
CPSOminm =
1278
CPSOmaxm =
1297
CPSOaverage =
1.2891e+003
CPSOstd =
8.9374
CPSOm =
1278 1297 1297 1297 1297 1296 1297 1297 1278 1297
CPSOminm =
1278
CPSOmaxm =
1297
CPSOaverage =
1.2931e+003
CPSOstd =
7.9645
CPSOm =
1294 1297 1296 1297 1297 1297 1278 1297 1294 1297
CPSOminm =
1278
CPSOmaxm =
1297
CPSOaverage =
1.2944e+003
CPSOstd =
5.8916
PSOm =
1297 1297 1297 1297 1278 1297 1278 1297 1297 1297
CPSOm =
1294 1288 1288 1297 1287 1297 1289 1297 1297 1291
PSOminm =
1278
PSOmaxm =
1297
PSOaverage =
1.2932e+003
PSOst =
8.0111
CPSOminm =
1287
CPSOmaxm =
1297
CPSOaverage =
1.2925e+003
CPSOstd =
4.3269
PSOm =
1278 1297 1297 1297 1278 1297 1297 1281 1297 1278
CPSOm =
1297 1293 1278 1297 1297 1297 1297 1297 1297 1297
PSOminm =
1278
PSOmaxm =
1297
PSOaverage =
1.2897e+003
PSOst =
9.4640
CPSOminm =
1278
CPSOmaxm =
1297
CPSOaverage =
1.2947e+003
CPSOstd =
6.0009
PSOm =
1298 1306 1297 1297 1297 1297 1297 1297 1297 1297
CPSOm =
1297 1297 1297 1297 1297 1297 1297 1297 1297 1297
PSOminm =
1297
PSOmaxm =
1306
PSOaverage =
1298
PSOst =
2.8284
CPSOminm =
1297
CPSOmaxm =
1297
CPSOaverage =
1297
CPSOstd =
0
PSOm =
Columns 1 through 9
1618 1596 1607 1618 1607 1604 1605 1613 1604
Column 10
1618
CPSOm =
Columns 1 through 9
1605 1615 1598 1607 1618 1610 1619 1586 1616
Column 10
1609
PSOminm =
1596
PSOmaxm =
1618
PSOaverage =
1609
PSOst =
7.4685
CPSOminm =
1586
CPSOmaxm =
1619
CPSOaverage =
1.6083e+003
CPSOstd =
10.1768
PSOm =
Columns 1 through 9
1617 1623 1625 1616 1633 1597 1622 1618 1600
Column 10
1617
CPSOm =
Columns 1 through 9
1607 1615 1615 1618 1607 1583 1584 1602 1618
Column 10
1617
PSOminm =
1597
PSOmaxm =
1633
PSOaverage =
1.6168e+003
PSOst =
10.9118
CPSOminm =
1583
CPSOmaxm =
1618
CPSOaverage =
1.6066e+003
CPSOstd =
13.3267
PSOm =
4030 3984 4059 4069 4007 4006 3984 4019 4035 3994
CPSOm =
4002 4001 4012 4008 4015 3991 4009 3981 4001 3987
PSOminm =
3984
PSOmaxm =
4069
PSOaverage =
4.0187e+003
PSOst =
29.5599
CPSOminm =
3981
CPSOmaxm =
4015
CPSOaverage =
4.0007e+003
CPSOstd =
11.1858
PSOm =
4044 4019 3980 4027 4046 4047 4035 4076 4050 3989
CPSOm =
4012 4025 4008 3970 3987 3996 4007 4026 4035 3979
PSOminm =
3980
PSOmaxm =
4076
PSOaverage =
4.0313e+003
PSOst =
29.0136
CPSOminm =
3970
CPSOmaxm =
4035
CPSOaverage =
4.0045e+003
CPSOstd =
21.3607
PSOm =
4039 4138 4077 4128 4123 4052 4093 4162 4148 4142
CPSOm =
4105 4171 4111 4105 4147 4141 4168 4044 4066 4098
PSOminm =
4039


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.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
341.
342.
343.
344.
345.
346.
347.
348.
349.
350.
351.
352.
353.
354.
355.
356.
357.
358.
359.
360.
361.
362.
363.
364.
365.
366.
367.
368.
369.
370.
371.
372.
373.
374.
375.
376.
377.
378.
379.
380.
381.
382.
383.
384.
385.
386.
387.
388.
389.
390.
391.
392.
393.
394.
395.
396.
397.
398.
399.
400.
401.
402.
403.
404.
405.
406.
407.
408.
409.
410.
411.
412.
413.
414.
415.
416.
417.
418.
419.
420.
421.
422.
423.
424.
425.
426.
427.
428.
429.
430.
431.
432.
433.
434.
435.
436.
437.
438.
439.
440.
441.
442.
443.
444.
445.
446.
447.
448.
449.
450.
451.
452.
453.
454.
455.
456.
457.
458.
459.
460.
461.
462.
463.
464.
465.
466.
467.
468.
469.
470.
471.
472.
473.
474.
475.
476.
477.
478.
479.
480.
481.
482.
483.
484.
485.
486.
487.
488.
489.
490.
491.
492.
493.
494.
495.
496.
497.
498.
499.
500.
501.
502.
503.
504.
505.
506.
507.
508.
509.
510.
511.
512.
513.
514.
515.
516.
517.
518.
519.
520.
521.
522.
523.
524.
525.
526.
527.
528.
529.
530.
531.
532.
533.
534.
535.
536.
537.
538.
539.
540.
541.
542.
543.
544.
545.
546.
547.
548.
549.
550.
551.
552.
553.
554.
555.
556.
557.
558.
559.
560.
561.
562.
563.
564.
565.
566.
567.
568.
569.
570.
571.
572.
573.
574.
575.
576.
577.
578.
579.
580.


## 5、 ... and 、matlab Edition and references

1 matlab edition
2014a

2 reference
[1] Baoziyang , Yu Jizhou , Poplar . Intelligent optimization algorithm and its application MATLAB example （ The first 2 edition ）[M]. Electronic industry press ,2016.
[2] Zhang Yan , Wu Shuigen .MATLAB Optimization algorithm source code [M]. tsinghua university press ,2017.