基于K-means聚类的超启发式跨单元调度方法.docx

第36

第36卷第4期2024年4月

Vol.36No.4Apr.2024

JournalofSystemSimulation

基于K-means聚类的超启发式跨单元调度方法

赵彦霖，田云娜

(延安大学数学与计算机科学学院，陕西延安716000)

摘要：结合我国制造业实际生产状况，针对柔性作业车间跨单元调度问题，提出一种基于K-means聚类的超启发式算法。应用K-means聚类算法将相近属性的实体划入相应“工件簇”决策块中，采用蚁群算法为每个决策块选择启发式规则；对每个决策块内的实体运用相应的启发式规则产生调度解。仿真结果表明：该算法以决策块的形式适度增大了计算粒度，有效降低了算法时间复杂度，以聚类的方式将具有相近属性的被加工实体进行聚集，有利于为不同属性的实体选择合适的规则。该算法提高了计算效率，具有较好的优化性能，是解决柔性跨单元调度的一种有效算法。

关键词：跨单元调度；超启发式算法；决策块；聚类；蚁群算法

中图分类号：TP18；TP301.6文献标志码：A文章编号：1004-731X(2024)04-0941-16

DOI:10.16182/j.issn1004731x.joss.22-1541

引用格式:赵彦霖,田云娜.基于K-means聚类的超启发式跨单元调度方法[J].系统仿真学报,2024,36(4):941-956.

Referenceformat:ZhaoYanlin,TianYunna.Hyper-heuristicApproachwithK-meansClusteringforInter-cellScheduling[J].JournalofSystemSimulation,2024,36(4):941-956.

Hyper-heuristicApproachwithK-meansClusteringforInter-cellScheduling

ZhaoYanlin,TianYunna

(SchoolofMathematicsandComputerScience,YananUniversity,Yanan716000,China)

Abstract:AccordingtotheactualproductionsituationofChinasmanufacturingindustry,ahyper-heuristicalgorithmbasedonK-meansclusteringisproposedforinter-cellschedulingproblemofflexiblejob-shop.K-meansclusteringisappliedtogroupentitieswithsimilarattributesintothecorrespondingworkclusterdecisionblocks,andtheantcolonyalgorithmisusedtoselectheuristicrulesforeachdecisionblock.Theoptimalschedulingsolutionsaregeneratedbyusingcorrespondingheuristicrulesforschedulingofentitiesineachdecisionblock.Computationalresultsshowthat,thecomputationalgranularityisproperlyincreasedbytheformofdecisionblocks,andthecomputationalefficiencyoftheoptimalalgorithmisimproved.Theclusteringalgorithmcouldgrouptheprocessedentitieswithsimilarattributesandthesuitablerulesforentitieswithdifferentattributesareeasytobechosen.Theproposedapproachnotonlyimprovescomputationalef