具有交货期和工装数量约束的平行机调度.pdfVIP

业信 DOI：10．3969／j．issn．1009-9492．2012．09,016 具有交货期和工装数量约束的平行机调度 徐武来，黎展滔，毛 宁，陈庆新 (广东工业大学广东省计算机集成制造系统重点实验室，广东广州 510006) 摘要：提 _r一类具有 件交货期和工装数量约束的平行机调度问题。以降低部件拖期惩罚总费用为 目标，建立了该问题的数 学模型．．提fn一种遗传 与模拟退火相混合的算法来求解该类问题，即GASA算法。算法在初始种群的生成上，采取了随机生成 和按启发式规则生成相结合的方法；并引入模拟退火算法作为变异算子，以提高种群的多样性。最后，通过实例仿真，验汪 GASA算法的有效性，并与GA算法进行了对比，对比结果表明GASA更优越。 关键词：调度；交货期；T装数量；遗传模拟退火 中图分类号 ：0223 文献标识码 ：A 文章编号 ：l009—9492(2012)09—0053—05 SchedulingAlgorithm forParallelMachinesunderConstraintsof DeliveryDeadlineandQuantitiesofTooling XUWu—lai，LIZhan-tao，MAONing，CHENQing-xin (KeyLaboratoryofComputerIntegratedManufacturingSystemofGuangdongProvince，GuangdongUniversityof Technology，Guangzhou510006，China) Abstract：Anintegratedproblem wasstudiedforparallelmachinesscheduling． inwhichtheconstraintsofpartdeliverydeadlineand quantitiesof|oolingwereconsidered．Toreducetardinesspenaltycosts．asinglemodelwasbuilduptodescribethewholeproblem．A genetic—simulatedannealingalgorithm wasproposedtosolvetheproblem．A new initialization methodisproposed．which conllfines generation tinoughheuristicruleswith random generation．Finally， simulationsrevealthatthealgorithm iseffective．And simulated annealingalgorithm isadoptedtobemutationoperator．Comparinggenetic—simu1atedannealingalgorithm withgeneticalgorithm，results showoutthattheschedulingmodelandthealgorithmaremoreeffectivearidsuperior． Keywords：scheduling；deliverydeadline；quantitiesoftoo]ing；GASA O引言 的最小拖期和调度问题 ，这里的模具约束可以看 在具有多品种小批量生产特征的订货型企业 成是工装约束 ，采用了一种启发式算法对问题进 中，生产拖期会影响公司信誉甚至产生惩罚费 行了有效求解 ，其中每个任务都是由单独的工件 用 ，同时T装也常常成为了一种瓶颈资源。因 组成 ，而本文所研究问题的对象为部件 内的工 此，在调度过程中，交货期和工装数量约束是需