| [车间调度]求解带有阻塞限制的HFSP的MILP模型与改进回溯搜索算法 |
| |
| 引用本文： | 孟磊磊,张超勇,任彩乐,李振国,任亚平. [车间调度]求解带有阻塞限制的HFSP的MILP模型与改进回溯搜索算法[J]. 中国机械工程, 2018, 29(22): 2647 |
| |
| 作者姓名： | 孟磊磊 张超勇 任彩乐 李振国 任亚平 |
| |
| 作者单位： | 华中科技大学数字制造装备与技术国家重点实验室，武汉，430074 |
| |
| 基金项目： | 国家自然科学基金资助项目(51575211,51705263)；国家自然科学基金国际(地区)合作与交流项目(51561125002);吉林省自然科学基金资助项目（20180101058JC）;浙江省自然科学基金资助项目(LQ16G010002)；高等学校智能制造创新引智计划资助项目(B16019) |
| |
| 摘 要： | 针对带有阻塞限制的不相关并行机混合流水车间调度问题，以最小化最长完工时间为目标，依据不同的建模思想，建立了求解该问题的4个混合整数线性规划(MILP)模型；鉴于混合整数线性规划不适合求解中大规模问题，提出了一种改进的回溯搜索算法以求解中大规模问题，在该算法中，引入了轮盘赌选择策略以及变邻域搜索算法，以提高算法的收敛速度以及局部搜索能力。最后，对所提MILP模型以及算法进行了对比分析，通过对具体实例的求解验证了所提MILP模型以及算法的有效性及优越性。
|
| 关 键 词： | 混合流水车间调度；阻塞；混合整数线性规划；回溯搜索算法；轮盘赌选择策略 变邻域搜索 |
MILP Models and an Improved BSA for Hybrid Flow Shop Scheduling Problems with Blocking |
| |
| 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, 2018, 29(22): 2647 |
| |
| Authors: | MENG Leilei ZHANG Chaoyong REN Caile LI Zhenguo REN Yaping |
| |
| Affiliation: | State Key Lab of Digital Manufacturing Equipment and Technology, Huazhong Universityof Science and Technology, Wuhan, 430074 |
| |
| 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. |
| |
| Keywords: | hybrid flow shop scheduling,blocking,mixed integer linear programming(MILP) backtracking search optimization algorithm(BSA),roulette selection strategy,variable neighborhood search(VNS), |
|
| 点击此处可从《中国机械工程》浏览原始摘要信息 |
|
点击此处可从《中国机械工程》下载免费的PDF全文 |
