具有后成组约束的两阶段柔性流水作业计划制订的启发式算法.pdfVIP

学兔兔 第49卷第 12期 机 械 工 程 学 报 V01．49 NO．12 2013 年 6 月 JOURNAL0FMECHANICALENGINEERING Jun． 2013 DoI：10．3901，JM E．2013．12．183 具有后成组约束的两阶段柔性流水作业计划 制订的启发式算法木 黎展滔 陈庆新 毛 宁 (广东工业大学广东省计算机集成制造系统重点实验室 广州 510006) 摘要：提出一类考虑后成组约束的、工件批量到达的两阶段柔性流水车间调度问题，并且在每阶段都是由非同等并行机构成， 在对后成组约束进行定义和数学描述的基础上，进一步建立两阶段柔性流水车间调度问题的优化模型。通过对该类调度问题 的分析，得到一条调度优势准则(定理 1)，并且根据定理 1，设计一种基于组合调度规则的启发式算法以及该类调度问题的算 例生成方法。为验证算法和比较评估调度规则的性能，对算例采用基于文献所提出的 12种组合调度规则和启发式算法进行 仿真调度，对调度结果的分析表明，算法的有效性和启发式算法调度规则在求解所提出的两阶段柔性流水调度问题的优越 性能。 关键词：启发式算法 柔性流水车间 后成组约束 中图分类号：F406 HeuristicAlgorithm forTwo—stageFlexibleFlow ShopScheduling withTailGroupConstraint LIZhantao CHENQingxin MAONing (KeyLaboratoryofComputerIntegratedManufacturingSystemofGuangdongProvince， GuangdongUniversityofTechnology,Gunagzhou510006) Abstract：Two—stageflexibleflow shopschedulingproblemwithtasktailgroupconstraintandreleasinginbatchisproposed，where thetwosatgesaremadeupofunrelatedmachines．Basedondefiningwto-stageflexibleflow shopwithtailgroupconsrtanitand givingitsmahtematicaldescriptionsystematically,hteoptimiz~ionmodelofhtewto-stageflexibleflow shop scheduling isput forwrad．Throughanalyzingofhtiskindofproblem，aruleofadvanatgescheduling(hteorem1)isproved．Accordnigtohteorem1，a newheuristicmehtodbasedoncombinatorialdispatchingrule，isdesigned．Inordertovalidatehtemethodandcompareandevaluate htenew heuristic，asimulationmehtodispresented，nadthenwt elvedispatchingurlesbasedonhteliteraturesandheuristicrae adoptedinhteschedulingsimulation．SimulationresultsindicatehtathteheuristicmehtodiSeffectiveandheuristicoutperformsthe ohterwt elvedispatchingurleswihtrespecttothewto—satgeflexibleflow shopschedulingpro