计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (32): 18-22.

• 博士论坛 • 上一篇    下一篇

缓冲区有限的流水车间调度问题的启发式算法

于艳辉1,2,李铁克1,王柏琳1   

  1. 1.北京科技大学 东凌经济管理学院,北京 100083
    2.东北大学秦皇岛分校 数学与统计学院,河北 秦皇岛 066004
  • 出版日期:2012-11-11 发布日期:2012-11-20

Heuristic algorithm for flowshop scheduling with limited buffer constraint

YU Yanhui1,2, LI Tieke1, WANG Bailin1   

  1. 1.Dongling School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China
    2.School of Mathematics and Statistics, University of Northeastern University at Qinhuangdao, Qinhuangdao, Hebei 066004, China
  • Online:2012-11-11 Published:2012-11-20

摘要: 针对缓冲区有限的流水车间调度问题,分析了目标函数的特征,及目标函数与工件空闲时间之间的关系,设计开发了启发式算法。算法将以Makespan为目标函数转化成以最小化机器空闲时间为目标函数,并以此为基础构造初始加工序列,再通过贪婪排序与插入寻优消除缓冲区受限约束并寻找问题的近优解。仿真实验结果表明,算法在求解质量和计算时间方面明显优于其他几种排序规则,并体现了目标函数表达式结构的特性及对解的适应性。

关键词: 流水车间调度问题, 缓冲区有限, 启发式算法

Abstract: For the flowshop scheduling with limited buffers, the special nature of the objective function and the relationship between the objective function and idle time are analyzed. On this basis, a target heuristic algorithm is proposed. Based on the transformation of the objective function, and in order to minimize the idle time, the algorithm forms the initial processing sequence and then solves the violated buffer constraints and searches for the optimal solution with greed and insertion. Emulating experimental results demonstrate the new algorithm obtains satisfactory results both on solutions quality and computation time, and show the characteristics of the problem and adaptability.

Key words: flowshop scheduling, limited buffers, heuristic algorithm