Heuristic algorithm for flowshop scheduling with limited buffer constraint

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (32): 18-22.

Previous Articles Next Articles

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

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

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

1.北京科技大学东凌经济管理学院，北京 100083
2.东北大学秦皇岛分校数学与统计学院，河北秦皇岛 066004

Abstract

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

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

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

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

[1]	ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89.
[2]	MENG Xin, YANG Qin, HAO Tingting, ZHANG Jie, CAO Cejun. Optimized Combination of Picking Path in Different Distributions and Algorithms [J]. Computer Engineering and Applications, 2020, 56(23): 229-236.
[3]	LI Yali, WANG Shuqin, CHEN Qianru, WANG Xiaogang. Comparative Study of Several New Swarm Intelligence Optimization Algorithms [J]. Computer Engineering and Applications, 2020, 56(22): 1-12.
[4]	YI Chengqi, GUO Xin, TONG Nannan, DOU Yue, CHEN Dong, WANG Jiandong. Innovation Situation Analysis Algorithm Based on Heuristic Model of Community Detection [J]. Computer Engineering and Applications, 2020, 56(15): 74-79.
[5]	HU Xiaomin, LIANG Tianyi, WANG Mingfeng, LI Min. Novel Tree Heuristic Search Algorithm for Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(11): 164-171.
[6]	CHI Zongzheng, DONG Shaozheng, GUO Tong, REN Zhilei, ZHOU Kuanjiu, GUO He. Research on Wind Farm Layout Based on Hyper-Heuristic [J]. Computer Engineering and Applications, 2019, 55(7): 220-225.
[7]	SHANG Zhengyang1, GU Jinan2, TANG Shixi2, SUN Xiaohong2. Efficient Residual-Space-Optimization Algorithm for Three Dimensional Container Loading Problem [J]. Computer Engineering and Applications, 2019, 55(5): 44-50.
[8]	ZHANG Jun, HE Ketai. Study on Hybrid Genetic and Simulated Annealing Algorithm for Three-Dimensional Packing Problems [J]. Computer Engineering and Applications, 2019, 55(14): 32-39.
[9]	WANG Changbao1, YANG Xibei1，2, DOU Huili1, CHEN Xiangjian1, WANG Pingxin3. Research on local attribute reduction approach via neighborhood decision error rate [J]. Computer Engineering and Applications, 2018, 54(6): 95-99.
[10]	WANG Zhuan, PEI Zeping. Order batching algorithm based on heuristic picking route for saving mileage [J]. Computer Engineering and Applications, 2018, 54(23): 203-209.
[11]	XU Xuesong1, XU Xinyao2. Simultaneous regression algorithm for multi-structure model fitting [J]. Computer Engineering and Applications, 2017, 53(6): 73-79.
[12]	SUN Liangxu1, QU Dianli2, LIU Guoli3. Two-stage estimation distribution algorithm for permutation flowshop scheduling problem [J]. Computer Engineering and Applications, 2017, 53(2): 64-71.
[13]	WANG Yinglong1, HUA Jiajia1, QIAN Wenbin2, YANG Jun2. Dynamic algorithm of attribute reduction in set-valued decision information system [J]. Computer Engineering and Applications, 2017, 53(17): 60-64.
[14]	SONG Lijun, ZHAO Hu. Integrated order acceptance and scheduling for multi-node flow-line production [J]. Computer Engineering and Applications, 2015, 51(4): 249-253.
[15]	LI Lijuan, WU Xiao, WANG Zhilong. Research of no-idle flow shop scheduling based on improved bacteria foraging optimization algorithm [J]. Computer Engineering and Applications, 2015, 51(17): 255-258.

Heuristic algorithm for flowshop scheduling with limited buffer constraint

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics