基于TSP方法求解等待时间受限的置换流水车间调度-控制与决策.PDFVIP

第27 卷 第5 期 控 制 与 决 策 2012 年 5 月 Vol. 27 No. 5 Control and Decision May 2012 文章编号: 1001-0920 (2012) 05-0768-05 基于TSP 方法求解等待时间受限的置换流水车间调度 王柏琳, 李铁克, 孙 彬 (1. 北京科技大学东凌经济管理学院，北京100083；2. 钢铁生产 制造执行系统技术教育部工程研究中心，北京100083) 摘 要: 等待时间受限的置换流水车间调度问题要求工件在连续两个机器间的等待时间满足上限值约束. 对 此, 分析了工件序列中相邻工件的加工持续时间及其上下界关系, 并且提出一种启发式方法. 首先, 建立旅行商问 题(TSP) 以生成初始调度; 然后, 采用扩展插入方法优化调度解. 为了衡量算法性能, 给出问题下界的计算方法和相 关评价指标, 并通过数据实验验证了该启发式和下界计算方法的可行性和有效性. 关键词: 生产调度；置换流水车间；等待时间受限；启发式 中图分类号: TP301 文献标识码: A TSP-based heuristic algorithm for permutation flowshop scheduling with limited waiting time constraints WANG Bai-lin, LI Tie-ke, SUN Bin (1. Dongling School of Economics and Management，University of Science and Technology Beijing ，Beijing 100083，China ；2. Engineering Research Center of MES Technology for Iron Steel Production，Ministry of Education ，Beijing 100083 ，China ．Correspondent ：WANG Bai-lin ，E-mail ：wangbailin 83@) Abstract: In the permutation flowshop scheduling problem with limited waiting time constraints, the waiting time of each job between two consecutive machines is restricted by some upper bound. Based on the deep discussion of the duration time between two adjacent jobs in one job permutation and the relations of its upper and lower bound, a heuristic algorithm is proposed. In the algorithm, a travelling salesman problem(TSP) concerning the duration times is built to obtain an initial schedule, and then an extended inserting method is presented for the further optimization. To measure algorithm performance, an approach to calculate a lower bound of the problem is proposed. Numerical results show effectiveness and feasibility of this heuristic algorithm.