Improved COOT Algorithm to Solve Multi-Objective Flexible Jobshop Scheduling Problem

doi:10.3778/j.issn.1002-8331.2207-0227

Abstract

Abstract: Aiming at the multi-objective flexible jobshop scheduling problem（FJSP）, a model with the completion time, total machine load and energy consumption as the optimization objectives is established, and the multi-objective COOT algorithm combined with simulated annealing（MOCOOT-SA） is proposed to solve it. The algorithm optimizes the original single-objective COOT algorithm into a multi-objective algorithm by introducing the concept of archive set and Pareto solution, and selects a new neighborhood structure and update method for specific individuals, and then integrates the simulated annealing algorithm（SA） to optimize local search ability and convergence speed. Finally, the appropriate codec method is selected, the MOCOOT-SA algorithm is used to test the improved benchmark example, and compared with the results of the NSGA-II algorithm and the MOPSO algorithm, the average optimization ratio of each target is 0.013~0.047, the optimal value optimization ratio is 0.016~0.045. The results show the advantage of this algorithm that it can better solve the multi-objective FJSP.

Key words: flexible jobshop, production scheduling, multi-objective optimization, MOCOOT-SA algorithm

摘要： 针对柔性车间调度的多目标优化问题，建立了以完工时间、机器总负荷、能耗为优化目标的模型，并提出了一种结合模拟退火的多目标COOT算法（multi-objective COOT algorithm combined with simulated annealing，MOCOOT-SA）进行求解。该算法通过引入存档集和Pareto解的理念，将原有的单目标COOT算法优化成多目标算法，并为其中特定个体选择新的邻域结构和更新方式，再融合模拟退火算法（simulated annealing，SA）优化局部搜索能力和收敛速度。最后选用合适的编解码方式，用MOCOOT-SA算法测试改进的基准算例，并与NSGA-Ⅱ算法、MOPSO算法的结果进行对比，得到各目标上的平均值优化比为0.013~0.047，最优值优化比为0.016~0.045。结果表明，该算法的优点是能更好地解决多目标柔性车间调度问题。

关键词: 柔性车间, 生产调度, 多目标优化, MOCOOT-SA算法

LING Fangping, JI Weixi. Improved COOT Algorithm to Solve Multi-Objective Flexible Jobshop Scheduling Problem[J]. Computer Engineering and Applications, 2023, 59(22): 307-314.

凌方平, 吉卫喜. 改进COOT算法求解多目标柔性车间调度问题[J]. 计算机工程与应用, 2023, 59(22): 307-314.

References

[1] BRUKER P，SCHLIE R.Job-shop scheduling with multi-purpose machines[J].Computing，1990，45（4）：369-375.
[2] 连裕翔，张超勇，孟磊磊，等.基于改进Jaya算法的柔性作业车间调度问题[J].计算机集成制造系统，2021，27（11）：3172-3184.
LIAN Y X，ZHANG C Y，MENG L L，et al.Improved Jaya algorithm and tabu search for flexible job shop scheduling problem[J].Computer Integrated Manufacturing Systems，2021，27（11）：3172-3184.
[3] 陈浩杰，丁国富，张剑，等.求解资源受限多项目调度的改进遗传规划算法[J].中国机械工程，2021，32（10）：1213-1221.
CHEN H J，DING G F，ZHANG J，et al.Improved genetic programming algorithm for RCMPSP[J].China Mechanical Engineering，2021，32（10）：1213-1221.
[4] ZHANG G，SHAO X，LI P，et al.An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem[J].Computers & Industrial Engineering，2009，56（4）：1309-1318.
[5] KNOWLES J，CORNE D.The Pareto archived evolution strategy：a new baseline algorithm for multiobjective optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation.Piscataway：IEEE，1999：98-105.
[6] DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-11[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.
[7] 肖世昌，吴自高，孙树栋，等.双资源约束的鲁棒Job Shop调度问题研究[J].机械工程学报，2021，57（4）：227-239.
XIAO S C，WU Z G，SUN S D，et al.Research on the dual-resource constrained robust job shop scheduling problems[J].Journal of Mechanical Engineering，2021，57（4）：227-239.
[8] 鞠录岩，杨建军，张建兵，等.改进NSGA算法求解多目标柔性车间作业调度问题[J].计算机工程与应用，2019，55（13）：260-265.
JU L Y，YANG J J，ZHANG J B，et al.Improved NSGA for multi-objective flexible job-shop scheduling problem[J].Computer Engineering and Applications，2019，55（13）：260-265.
[9] NARUEI I，KEYNIA F.A new optimization method based on coot bird natural life model[J].Expert Systems with Applications，2021，183（2）：115352.
[10] HUSSIEN A M，TURKY R A，ALKUHAYLI A，et al.Coot bird algorithms-based tuning PI controller for optimal microgrid autonomous operation[J].IEEE Access，2022，10：6442-6458.
[11] ALQAHTANI A S，SARAVANAN P，MAHESWARI M，et al.An automatic query expansion based on hybrid CMO-COOT algorithm for optimized information retrieval[J].The Journal of Supercomputing，2022，78（6）：8625-8643.
[12] 李夏苗，陈新江，伍国华，等.考虑断点续传的中继卫星调度模型及启发式算法[J].航空学报，2019，40（11）：274-289.
LI X M，CHEN X J，WU G H，et al.Scheduling model and heuristic algorithm for tracking and data relay satellite considering breakpoint transmission[J].Acta Aeronautica et Astronautica Sinica，2019，40（11）：274-289.
[13] 孔芝，杨青峰，赵杰，等.基于自适应调整权重和搜索策略的鲸鱼优化算法[J].东北大学学报（自然科学版），2020，41（1）：35-43.
KONG Z，YANG Q F，ZHAO J，et al.Adaptive adjustment of weights and search strategies-based whale optimization algorithm[J].Journal of Northeastern University（Natural Science），2020，41（1）：35-43.
[14] 蔡敏，王艳，纪志成.混合粒子群优化算法求解模糊柔性作业车间调度问题[J].南京理工大学学报，2021，45（3）：352-360.
CAI M，WANG Y，JI Z C.Hybrid particle swarm optimization for solving fuzzy flexible job-shop scheduling problem[J].Journal of Nanjing University of Science and Technology，2021，45（3）：352-360.
[15] 张钧，贺可太.求解三维装箱问题的混合遗传模拟退火算法[J].计算机工程与应用，2019，55（14）：32-39.
ZHANG J，HE K T.Study on hybrid genetic and simulated annealing algorithm for three-dimensional packing problems[J].Computer Engineering and Applications，2019，55（14）：32-39.
[16] 李金忠，夏洁武，曾小荟，等.多目标模拟退火算法及其应用研究进展[J].计算机工程与科学，2013，35（8）：77-88.
LI J Z，XIA J W，ZENG X H，et al.Survey of multi-objective simulated annealing algorithm and its applications[J].Computer Engineering & Science，2013，35（8）：77-88.
[17] SUMAN B.Simulated annealing-based multiobjective algorithms and their application for system reliability[J].Engineering Optimization，2003，35（4）：391-416.