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

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

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

于艳辉1，2，李铁克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.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

摘要/Abstract

摘要： 针对缓冲区有限的流水车间调度问题，分析了目标函数的特征，及目标函数与工件空闲时间之间的关系，设计开发了启发式算法。算法将以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

于艳辉1，2，李铁克1，王柏琳1. 缓冲区有限的流水车间调度问题的启发式算法[J]. 计算机工程与应用, 2012, 48(32): 18-22.

YU Yanhui1，2, LI Tieke1, WANG Bailin1. Heuristic algorithm for flowshop scheduling with limited buffer constraint[J]. Computer Engineering and Applications, 2012, 48(32): 18-22.

[1]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[2]	孟鑫，杨琴，郝婷婷，张洁，曹策俊. 不同订单分配和算法下的拣货路径优化组合[J]. 计算机工程与应用, 2020, 56(23): 229-236.
[3]	李雅丽，王淑琴，陈倩茹，王小钢. 若干新型群智能优化算法的对比研究[J]. 计算机工程与应用, 2020, 56(22): 1-12.
[4]	易成岐，郭鑫，童楠楠，窦悦，陈东，王建冬. 基于启发式社团发现模型的创新态势研判算法[J]. 计算机工程与应用, 2020, 56(15): 74-79.
[5]	胡晓敏，梁天毅，王明丰，李敏. 新型树启发式搜索算法的机器人路径规划[J]. 计算机工程与应用, 2020, 56(11): 164-171.
[6]	迟宗正，董绍正，郭童，任志磊，周宽久，郭禾. 求解风力发电机布局问题的超启发式算法研究[J]. 计算机工程与应用, 2019, 55(7): 220-225.
[7]	尚正阳1，顾寄南2，唐仕喜2，孙晓红2. 高效求解三维装箱问题的剩余空间最优化算法[J]. 计算机工程与应用, 2019, 55(5): 44-50.
[8]	侯屿1，2，秦小林2，彭皓月1，2，张力戈1，2. 全局调距和声特征选择算法[J]. 计算机工程与应用, 2019, 55(2): 21-27.
[9]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[10]	刘竹松，李生. 正余混沌双弦鲸鱼优化算法[J]. 计算机工程与应用, 2018, 54(7): 159-163.
[11]	王长宝1，杨习贝1，2，窦慧莉1，陈向坚1，王平心3. 邻域决策错误率的局部约简方法研究[J]. 计算机工程与应用, 2018, 54(6): 95-99.
[12]	吴伟民，李泽熊，林志毅，吴汪洋，方典禹. 飞蛾纵横交叉混沌捕焰优化算法[J]. 计算机工程与应用, 2018, 54(3): 136-141.
[13]	王转，裴泽平. 启发式路径下节约里程的订单分批算法[J]. 计算机工程与应用, 2018, 54(23): 203-209.
[14]	徐雪松1，徐歆尧2. 一种多结构数据的同步拟合方法[J]. 计算机工程与应用, 2017, 53(6): 73-79.
[15]	王严欣，崔耀东，李华. 应用精确两阶段排样图的板材下料算法[J]. 计算机工程与应用, 2017, 53(5): 236-240.