启发式算法求解等待时间受限的两阶段流水车间调度问题声忌理工手呈学才反bVol.28,No.2JournalofIndustrialEngineering/EngineeringManagement2014年第2期启发式算法求解等待时间受限的两阶段流水车间调度问题王柏琳l气李铁克1，2(1.北京科技大学东凌经济管理学院，北京100083;2.钢铁生产制造执行系统技术教育部工程研究中心，北京100083)摘要:等待时间受限的两阶段流水车间调度问题具有强NP难的复杂性，有必要探索问题特征来开发近似求解算法。本文分析了此问题与一般两阶段流水车间调度和无等待两阶段流水车间调度的关系，给出了两类特殊问题的多项式求解方法，探讨了最优调度的工件序列特征。在此基础上，设计了基于排列排序的启发式算法，算法应用Gilmore-Gomory启发式生成初始序列，构造调度解的可替换集合实现迭代寻优，并利用工件序列特征调整工件顺序以优化当前调度。通过对算法的求解性能进行理论分析和实验验证，进一步表明了该算法的有效性。关键词:调度;两阶段流水车间;等待时间受fll;启发式F406.2文献标识码A1004-6062(2014)02斗)182-09指数增长，因此无法求解大规模问题;或仅是对经典启发式o51言算法进行简单的扩展[7J虽然能够在短时间内获得可行解，在玻璃加工、钢铁生产[1.2J等流程性工业，由于生产过程但由于未能利用问题的特性，求解质量有待提高。对于具有的高温连续性或中间产品的不稳定性，往往要求工件在相邻强NP难复杂性的等待时间受限的两阶段流水车间调度问阶段的等待时间不能超过一定的时间上限，从而产生等待时题，近似算法的研究是有必要的问，而结合问题特征的求解间受限的流水车间调度问题。目前相关理论研究主要集中策略能够有效的提高算法的求解质量。因此，本文从问题特于无等待(即等待时间上限为零)调度方面[3叫，而针对一般征着手，分析其与不考虑等待时间限制的一般调度和无等待性等待时间受限调度的研究成果较少。其中，对于两阶段的调度的关系，探讨两类特殊问题的最优解和最优值特征，讨情况，在问题性质方面，文献[5J初步研究了等待时间受限的论最优调度的工件优先关系(DominanceRelation,DR)，进而两阶段流水车间调度问题，证明了问题是NP难的;文献[6J利用上述特征设计基于排列排序的启发式算法，并从理论分进一步证明了等待时间上限相同时两阶段流水车间调度问析和实验验证两方面检验算法的求解性能。题的强NP难特性，研究了排列排序问题与原问题之间的关系，为设计求解算法提供了理论依据;在算法求解方面，文献1问题描述及分析[5J应用分支定界法求解;文献[7J扩展了已有的启发式算1.1问题描述法并进行了比较分析;文献[8J对第一台机器为批处理机的等待时间受限的两阶段流水车间调度问题要求任-工特殊问题建立了混合整数规划模型，并提出了两阶段启发式件在相邻阶段的等待时间不能超过一定的时间上限，应用方法O对于多阶段的情况，文献[9J对不同车间环境下，等待Graham(1979)[13J提出的三元组表示法，此问题可表示为:时间受限的调度问题的建模机制进行了研究;文献[10J分析F21叭~αIC..。其中，F2表示调度问题的生产环境，即由2m了等待时间上限与可行调度的解析关系以及目标函数的特台机器|矶，M2f构成的两阶段流水车间(Flowshop)，n个待殊性质，设计了一种近似求解算法;文献[11J提出了一种结加工工件If，激均要求先经过矶，再经过M罢王川α;儿，…n2ι合交换邻域、变邻域和禁忌搜索的动态变邻域搜索方法;文表示调度问题的特殊工艺约束，即ViE11，2，…，圳，要求献[12J应用嵌入约束满足和变邻域搜索技术的混合遗传算工件J‘在机器间的等待时间矶=C-Pa-C不能超过给ail法实现问题求解。定上限值α，其中Pij为工件J在机器晚上的加工时间，Cii1，在流水车间调度中，仅有两阶段的情况是最基本的一类Ci2分别表示工件J在机器矶，M2上的完工时间;C表示调imu问题。从已有研究可以看出，对于等待时间受限的两阶段流度问题的优化目标，即确定各台机器上的工件加工顺序和工水车间调度问题，虽然对其问题性质已有了充分研究[5.6J但件完工时间飞，使得最大完工时间(Makespan)C..m在求解算法方面，或采用分支定界这种精确算法[5J虽然能maxlCijl:最小化o够...