启发式算法求解等待时间受限的两阶段流水车间调度问题  

Heuristic Algorithm for Two-Stage Flowshop Scheduling Problem with Limited Waiting Times

作　　者：王柏琳[1,2] 李铁克[1,2] 

机构地区：[1]北京科技大学东凌经济管理学院,北京100083 [2]钢铁生产制造执行系统技术教育部工程研究中心,北京100083

出　　处：《管理工程学报》2014年第2期182-190,共9页Journal of Industrial Engineering and Engineering Management

基　　金：国家自然科学基金资助项目(70771008);中央高校基本科研业务费专项资金资助项目(FRF-TP-12-116A);中国博士后科学基金资助项目(2012M510324)

摘　　要：等待时间受限的两阶段流水车间调度问题具有强NP难的复杂性,有必要探索问题特征来开发近似求解算法。本文分析了此问题与一般两阶段流水车间调度和无等待两阶段流水车间调度的关系,给出了两类特殊问题的多项式求解方法,探讨了最优调度的工件序列特征。在此基础上,设计了基于排列排序的启发式算法,算法应用Gilmore-Gomory启发式生成初始序列,构造调度解的可替换集合实现迭代寻优,并利用工件序列特征调整工件顺序以优化当前调度。通过对算法的求解性能进行理论分析和实验验证,进一步表明了该算法的有效性。The flowshop scheduling problem with limited waiting time constraints exists in the production environment （e. g. steelmaking and glass factories） where high temperature and requirement continuity are essential. In such production environment, it is imperative to restrict the maximum waiting time of any jobs between two consecutive machines. The objective of minimizing the makespan is one of the most important topics in this field. Two-stage flowshop scheduling problem with limited waiting time constraints to minimize the makespan is strongly NP-hard. Therefore, it is necessary to research on the approximation algorithms, and heuristic approaches concerning permutation schedules. This paper adopts the permutation flowshop scheduling as a method for solving two-stage flowshop scheduling problems. There are two extreme cases of the considered problem ： （ 1 ） the general two-stage flowshop scheduling in which the maximum waiting time is infinite, and （2） the no-wait two-stage flowshop scheduling in which the maximum waiting time is restricted to zero. These two problems can be solved by polynomial algorithms using permutation schedules, Johnson＇s rule and Gilmore-Gomory＇s heuristic respectively. There are two polynomial solvable cases with special characters of processing times. The first case is the proportionate flowshop scheduling in which the processing time of one job on all machines is equivalent. The second case is the machine-dependent flowshop scheduling in which the processing time of all jobs on one machine is equivalent. Based on the analysis of the characteristics of optimal schedules and minimum makespan of these two cases with two stages and limited waiting time constraints, some of these optimal solutions can be found in permutation schedules. Furthermore, a heuristic algorithm using permutation schedule is proposed. We first used Gilmore-Gomory＇s heuristic, which is the polynomial algorithm for the no-wait two-stage flowshop scheduling, to generate schedule because the optimal j

关 键 词：调度 两阶段流水车间 等待时间受限 启发式 

分 类 号：F406.2[经济管理—产业经济]