MILP Models and an Improved BSA for Hybrid Flow Shop Scheduling Problems with Blocking

Abstract

Abstract: The hybrid flow shop scheduling problems with blocking(HFSP-B) were studied with the minimization of makespans. Firstly, four MILP models were proposed based on different modeling ideas. Secondly, due to the inefficiency of the MILP model to medium-large problems, an improved backtracking search optimization algorithm(IBSA) was proposed. In this algorithm, roulette selection strategy and VNS were introduced to improve the convergence rate and local search ability. At last, numerical experiments were completed on real instances and the results show the effectiveness and superiority of the proposed MILP models and the IBSA.

Key words: hybrid flow shop scheduling, blocking, mixed integer linear programming(MILP);backtracking search optimization algorithm(BSA), roulette selection strategy, variable neighborhood search(VNS)

摘要： 针对带有阻塞限制的不相关并行机混合流水车间调度问题，以最小化最长完工时间为目标，依据不同的建模思想，建立了求解该问题的4个混合整数线性规划(MILP)模型；鉴于混合整数线性规划不适合求解中大规模问题，提出了一种改进的回溯搜索算法以求解中大规模问题，在该算法中，引入了轮盘赌选择策略以及变邻域搜索算法，以提高算法的收敛速度以及局部搜索能力。最后，对所提MILP模型以及算法进行了对比分析，通过对具体实例的求解验证了所提MILP模型以及算法的有效性及优越性。

关键词: 混合流水车间调度；阻塞；混合整数线性规划；回溯搜索算法；轮盘赌选择策略, 变邻域搜索

CLC Number:

TP18

MENG Leilei, ZHANG Chaoyong, REN Caile, LI Zhenguo, REN Yaping. MILP Models and an Improved BSA for Hybrid Flow Shop Scheduling Problems with Blocking[J]. China Mechanical Engineering.

孟磊磊, 张超勇, 任彩乐, 李振国, 任亚平. [车间调度]求解带有阻塞限制的HFSP的MILP模型与改进回溯搜索算法[J]. 中国机械工程.

References

[1]王圣尧，王凌，许烨，等.求解混合流水车间调度问题的分布估计算法[J].自动化学报, 2012,38(3)：437-443.
WANG Shengyao, WANG Ling, XU Ye, et al.An Estimation of Distribution Algorithm for Solving Hybrid Flow-shop Scheduling Problem[J].Acta Automatica Sinica,2012,38(3)：437-443.
[2]LI J, PAN Q.Solving the Large-scale Hybrid Flow Shop Scheduling Problem with Limited Buffers by a Hybrid Artificial Bee Colony Algorithm[J].Information Sciences,2015, 316(C)：487-502.
[3]郭鹏.基于蜂群繁殖算法的流水车间调度问题研究[D].武汉：华中科技大学, 2012.
GUO Peng.Studies on Flow Shop Scheduling Using Honey Bees Mating Optimization[D].Wuhan：Huazhong University of Science and Technology,2012.
[4]WARDONO B, FATHI Y.A.Tabu Search Algorithm for The Multi-stage Parallel Machine Problem with Limited Buffer Capacities[J].European Journal of Operational Research,2004, 155(2)：380-401.
[5]TAVAKKOLI-MOGHADDAM R, SAFAEI N, TORABI S A.Scheduling of Flexible Flow Lines with Blocking by Memetic Algorithms[J].IFAC Proceedings Volumes,2006, 39(3)：21-26.
[6]TAVAKKOLI-MOGHADDAM R, SAFAEI N, SASSANI F.A Memetic Algorithm for the Flexible Flow Line Scheduling Problem with Processor Blocking[J].Computers & Operations Research,2009, 36(2)：402-414.
[7]张其亮，陈永生.列车调度问题模型与基于混合粒子群优化的求解算法[J].中国机械工程,2013,24(14)：1916-1922.
ZHANG Qiliang, CHEN Yongsheng.Train Scheduling Problem Model and Its Solution Based on Hybrid Particle Swarm Optimization Algorithm[J].China Mechanical Engineering, 2013,24(14)：1916-1922.
[8]张其亮，陈永生.带有阻塞限制的混合流水车间调度问题的混合粒子群求解算法[J].信息与控制，2013, 42(2):252-257.
ZHANG Qiliang, CHEN Yongsheng.Hybrid Particle Swarm Optimization Algorithm for Hybrid Flow Shop Scheduling Problem with Blocking[J].Information & Control, 2013, 42(2):252-257.
[9]张其亮，陈永生.解决具有混合约束柔性流水车间调度问题的粒子群优化算法[J].计算机应用研究,2013,30(11)：3253-3256.
ZHANG Qiliang, CHEN Yongsheng.Particle Swarm Optimization Algorithm for Flexible Flow Shop Scheduling Problem with Mixed Constraints[J].Application Research of Computers, 2013,30(11)：3253-3256.
[10]ZHANG Y, WANG S.The Research of Trailer Scheduling Based on the Hybrid Flow Shop Problem with Blocking[C]// Intelligent Control and Automation.Piscataway, 2008：3936-3940.
[11]茜彦辉.应用两阶段作用力微粒群算法求解混合流水车间调度问题[D].秦皇岛：燕山大学, 2015.
YAN Qianhui.Solving Hybrid Flow-shop Scheduling Problem by Two-phase Force Particle Swarm Optimization Algorithm[D].Qinhuangdao：Yanshan University,2015.
[12]陈璐，奚立峰，蔡建国，等.一种求解带有阻塞限制的混合流水车间的禁忌搜索算法[J].上海交通大学学报，2006，40(5)：856-859.
CHEN Lu, XI Lifeng, CAI Jianguo, et al.A Tabu Search Algorithm for Hybrid Flow Shop Problem with Blocking Constraint[J].Journal of Shanghai Jiaotong University, 2006，40(5)：856-859.
[13]陈超，鲁建厦.重型机械加工车间物流协调调度问题研究[J].浙江工业大学学报，2011，39(4)：452-457.
CHEN Chao, LU Jiansha.Study on logistics Facilities Coordination Scheduling Problem of Heavy-duty Mechanical Workshop[J].Journal of Zhejiang University of Technology, 2011,39(4)：452-457.
[14]陈飞跃，徐震浩，顾幸生.基于离散布谷鸟搜索算法的带阻塞有差速混合流水车间调度[J].华东理工大学学报(自然科学版)，2017，43(3)：425-435.
CHEN Feiyue, XU Zhenhao, GU Xingsheng.Discrete Cuckoo Search Algorithm for Blocking and Unrelated Hybrid Flow Shop Scheduling Problem[J].Journal of East China University of Science and Technology(Natural Science Edition) ，2017，43(3)：425-435.
[15]YUAN K, SAUER N, SAUVEY C.Application of EM Algorithm to Hybrid Flow Shop Scheduling Problems with a Special Blocking[C]//IEEE International Conference on Emerging Technologies & Factory Automation.Piscataway,2009：1-7.
[16]RASHIDI E, JAHANDAR M, ZANDIEH M.An Improved Hybrid Multi-objective Parallel Genetic Algorithm for Hybrid Flow Shop Scheduling with Unrelated Parallel Machines[J].International Journal of Advanced Manufacturing Technology, 2010, 49(9/12)：1129-1139.
[17]THORNTON H W, HUNSUCKER J L.A New Heuristic for Minimal Makespan in Flow Shops with Multiple Processors and No Intermediate Storage[J].European Journal of Operational Research,2004, 152(1)：96-114.
[18]NADERI B, GOHARI S, YAZDANI M.Hybrid Flexible Flowshop Problems：Models and Solution Methods[J].Applied Mathematical Modelling,2014, 38(24)：5767-5780.
[19]CIVICIOGLU P.Backtracking Search Optimization Algorithm for Numerical Optimization Problems[J].Applied Mathematics & Computation,2013, 219(15)：8121-8144.
[20]董彩云，张超勇，孟磊磊，等.基于谐波小波包和BSA优化LS-SVM的铣刀磨损状态识别研究[J].中国机械工程,2017, 28(17)：2080-2089.
DONG Caiyun, ZHANG Chaoyong, MENG Leilei,et al.State Recognition of Milling Tool Wears Based on Harmonic Wavelet Packet and BSA Optimization LS-SVM[J].China Mechanical Engineering,2017, 28(17)：2080-2089.
[21]林群.回溯搜索算法的改进及其工程应用[D].武汉：华中科技大学, 2015.
LIN Qun.Research on Backtracking Search Algorithm with Its Engineering Applications[D].Wuhan：Huazhong University of Science and Technology,2015.
[22]LU C, GAO L, LI X, et al.Energy-efficient Multi-pass Turning Operation Using Multi-objective Backtracking Search Algorithm[J].Journal of Cleaner Production, 2016, 137：1516-1531.
[23]LIN Q, GAO L, LI X, et al.A Hybrid Backtracking Search Algorithm for Permutation Flow-shop Scheduling Problem[J].Computers & Industrial Engineering,2015, 85(C)：437-446.
[24]LU C, GAO L, LI X, et al.Energy-efficient Permutation Flow Shop Scheduling Problem Using a Hybrid Multi-objective Backtracking Search Algorithm[J].Journal of Cleaner Production，2017, 144：228-238.
[25]侯彦红.基于回溯搜索算法的三峡—葛洲坝联合通航调度[D].武汉:华中科技大学, 2015.
HOU Yanhong.Backtracking Search Optimization Algorithm for Navigation Co-scheduling of the Three Gorges Dam and Gezhouba Dam[D].Wuhan：Huazhong University of Science and Technology,2015.
[26]王炳刚，饶运清，邵新宇，等.带有限中间缓冲区的多级并行机问题的求解[J].华中科技大学学报(自然科学版),2009,37(5)：86-89.
WANG Binggang, RAO Yunqing, SHAO Xinyu, et al.Solving Multi-stage Parallel Machine Problem with Limited Intermediate Buffers[J].Journal of Huazhong University of Science and Technology(Natural Science Edition), 2009,37(5)：86-89.
[27]王凌.智能优化算法及其应用[M].北京:清华大学出版社，2001.
WANG Ling.IntelligentOptimization Algorithms with Application [M].Beijing：Tsinghua University Press, 2001.
[28]崔琪，吴秀丽，余建军.变邻域改进遗传算法求解混合流水车间调度问题[J].计算机集成制造系统,2017,23(9)：1917-1927.
CUI Qi,Wu Xiuli,YU Jianjun.Improved Genetic Algorithm Variable Neighborhood Search for Solving Hybrid Flow Shop Scheduling Problem[J].Computer Integrated Manufacturing Systems, 2017,23(9)：1917-1927.
[29]谢展鹏，张超勇，邵新宇，等.基于Memetic算法的有限缓冲区流水车间调度问题[J].计算机集成制造系统, 2015, 21(5):1253-1261.
XIE Zhanpeng, ZHANG Chaoyong, SHAO Xinyu, et al.Flow Shop Scheduling with Limited Buffers Based on Memetic Algorithm[J].Computer Integrated Manufacturing Systems, 2015, 21(5):1253-1261.
[30]王万良，姚明海，吴云高，等.基于遗传算法的混合Flow-shop调度方法[J].系统仿真学报,2002, 14(7)：863-865.
WANG Wanling , YAO Minghai, WU Yungao, et al.Hybrid Flow-shop Scheduling Approach Based on Genetic Algorithm[J].Acta Simulata Systematica Sinica, 2002, 14(7)：863-865.
[31]MENG L, ZHANG C, SHAO X, et al.Mathematical Modelling and Optimisation of Energy-conscious Hybrid Flow Shop Scheduling Problem with Unrelated Parallel Machines[J].International Journal of Production Research,2018, 1：1-27.