Double Archive Particle Swarm Optimization Solving Flexible Job-Shop Scheduling Problem

doi:10.3778/j.issn.1002-8331.2202-0298

Abstract

Abstract: This paper proposes a particle swarm optimization based on credibility of solution and double archive to minimize makespan of flexible job-shop scheduling problem（FJSP）. Firstly, the elite archive and the optimization archive are constructed to store the individual historical optimal position（Pbest） of the elite particle with better fitness value and the position of the particles that have made rapid progress, respectively. Secondly, it uses the particles in the elite archives to calculate the credibility of solution, and judge the evolutionary state of the current population according to the credibility of solution. The particles adjust the strength of learning from the two archives according to the evolutionary state to achieve a balance between convergence and diversity. Further, extensive experiments are carried out on 5 test problems of Kacem and 10 test problems of MK series, and the comparison with other algorithms according to the minimum completion time and average completion time proves the effectiveness of DAPSO in solving the FJSP problem.

Key words: particle swarm optimization, flexible job-shop scheduling, double archive, credibility of solution

摘要： 针对最小化完工时间的柔性作业车间调度问题（FJSP），提出了双档案粒子群算法（DAPSO）。构建精英档案和进步档案分别存储具有较好适应值的精英粒子的个体历史最优位置（Pbest）和进步较快粒子的位置。利用精英档案中的粒子计算解可信度,并根据解可信度来判断当前群体所处的进化状态，粒子根据进化状态调整向两个档案中学习的力度以达到收敛性与多样性的平衡。在Kacem的5个测试问题和MK系列10个测试问题开展了广泛实验，通过与其他算法按照最小完工时间、平均完工时间进行了比较，证明了DAPSO在求解FJSP问题时的有效性。

关键词: 粒子群优化算法, 柔性作业车间调度, 双档案机制, 解可信度

ZHANG Yujia, SONG Wei. Double Archive Particle Swarm Optimization Solving Flexible Job-Shop Scheduling Problem[J]. Computer Engineering and Applications, 2023, 59(11): 294-301.

张宇嘉, 宋威. 双档案粒子群算法求解柔性作业车间调度问题[J]. 计算机工程与应用, 2023, 59(11): 294-301.

References

[1] OZTURK G，BAHADIR O，TEYMOURIFAR A.Extracting priority rules for dynamic multi-objective flexible job shop scheduling problems using gene expression programming[J].International Journal of Production Research，2019，57：3121-3137.
[2] 邹泽桦，曾九孙，蔡晋辉.改进遗传算法求解柔性作业车间调度问题[J].计算机测量与控制，2017，25（4）：167-171.
ZOU Z H，ZENG J S，CAI J H，et al.Improved genetic algorithm for flexible job-shop scheduling problem[J].Computer Measurement & Control，2017，25（4）：167-171.
[3] DORIGO M，MANIEZZO V，COLORNI A.Ant system：optimization by a colony of cooperating agents[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，1996，26（1）：29-41.
[4] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Erciyes University.Engineering Faculty.Computer Engineering Department，2005.
[5] MIRJALILI S，MIRJALILI S M，LEWIS A.Grey wolf optimizer[J].Advances in Engineering Software，2014，69（3）：46-61.
[6] KENNEDY J，EBERHART R.Particle swarm optimization[C]//Proceedings of ICNN’95-International Conference on Neural Networks，1995：1942-1948.
[7] 林炜星，王宇嘉，陈万芬，等.基于多因子粒子群的高维数据特征选择算法[J].计算机工程与应用，2021，57（22）：199-207.
LIN W X，WANG Y J，CHEN W F，et al.High-dimensional data feature selection algorithm based on multifactor particle swarm optimization[J].Computer Engineering and Applications，2021，57（22）：199-207.
[8] LEE J H，SONG J，KIM D，et al.Particle swarm optimization algorithm with intelligent particle number control for optimal design of electric machines[J].IEEE Transactions on Industrial Electronics，2018，65（2）：1791-1798.
[9] 霍林，陆寅丽.改进粒子群算法应用于Android恶意应用检测[J].计算机工程与应用，2020，56（7）：96-101.
HUO L，LU Y L.Improved particle swarm optimization for Android malware detection[J].Computer Engineering and Applications，2020，56（7）：96-101.
[10] BEHESHTI Z.A time-varying mirrored S-shaped transfer function for binary particle swarm optimization[J].Information Sciences，2020，512：1503-1542.
[11] 梁田，曹德欣.基于莱维飞行的改进简化粒子群算法[J].计算机工程与应用，2021，57（20）：188-196.
LIANG T，CAO D X.Improved and simplified particle swarm optimization algorithm based on Levy flight[J].Computer Engineering and Applications，2021，57（20）：188-196.
[12] WEI B，XIA X，YU F，et al.Multiple adaptive strategies based particle swarm optimization algorithm[J].Swarm and Evolutionary Computation，2020，57：100731.
[13] XIA X，XING Y，WEI B，et al.A fitness-based multi-role particle swarm optimization[J].Swarm and Evolutionary Computation，2018：349-364.
[14] DING H，GU X.Hybrid of human learning optimization algorithm and particle swarm optimization algorithm with scheduling strategies for the flexible job-shop scheduling problem-ScienceDirect[J].Neurocomputing，2020，414：313-332.
[15] 顾幸生，丁豪杰.面向柔性作业车间调度问题的改进博弈粒子群算法[J].同济大学学报（自然科学版），2020，48（12）：1782-1789.
GU X S，DING H J.An improved gaming particle swarm optimization algorithm for flexible job?shop scheduling problems[J].Journal of Tongji University（Natural Science），2020，48（12）：1782-1789.
[16] SHI Y，EBERHART R.A modified particle swarm optimizer[C]//1998 IEEE International Conference on Evolutionary Computation Proceedings，IEEE World Congress on Computational Intelligence，1998：69-73.
[17] XU X，SHI Z，PAN B.?0-based sparse hyperspectral unmixing using spectral information and a multi-objectives formulation[J].ISPRS Journal of Photogrammetry and Remote Sensing，2018，141：46-58.
[18] TWOMEY K E，RANSON S L，HORST J S.That’s more like it：multiple exemplars facilitate word learning[J].Infant and Child Development，2014，23（2）：105-122.
[19] BAECK A，MAES K，MEEL C V，et al.The transfer of object learning after training with multiple exemplars[J].Frontiers in Psychology，2016，7（110）：1386.
[20] ROSALES R，REHFELDT R.Effects of multiple exemplar training on the emergence of derived relations in preschool children learning a second language[J].The Analysis of Verbal Behavior，2011，27（1）：61-74.
[21] GONG Y，LI J，ZHOU Y，et al.Genetic learning particle swarm optimization[J].IEEE Transactions on Cybernetics，2016，46（10）：2277-2290.
[22] LIANG J J，QIN A K，SUGANTHAN P N，et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation，2006，10（3）：281-295.
[23] XUE J，SHEN B.A novel swarm intelligence optimization approach：sparrow search algorithm[J].Systems Science & Control Engineering，2020，8（1）：22-34.
[24] KACEM I，HAMMADI S，BORNE P，et al.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J].IEEE Transactions on Systems，Man & Cybernetics，Part C：Applications & Reviews，2002，32（1）：1-13.
[25] BRANDIMARTE P.Routing and scheduling in a flexible job shop by Tabu search[J].Annals of Operations Research，1993，41（3）：157-183.
[26] NOUIRI M，BEKRAR A，JEMAI A，et al.An effective particle swarm optimization algorithm for flexible job-shop scheduling problem[C]//5th IEEE International Conference on Industrial Engineering and Systems Management（IESM），2013.
[27] HENCHIRI A，ENNIGROU M.Particle swarm optimization combined with Tabu search in a multi-agent model for flexible job shop problem[C]//International Conference in Swarm Intelligence.Berlin，Heidelberg：Springer，2013.
[28] ZIAEE M.A heuristic algorithm for solving flexible job shop scheduling problem[J].International Journal of Advanced Manufacturing Technology，2014，71：519-528.