带队列约束的RHFS列生成调度算法

doi:10.12068/j.issn.1005-3026.2018.09.020

东北大学学报:自然科学版 ›› 2018, Vol. 39 ›› Issue (9): 1315-1320.DOI: 10.12068/j.issn.1005-3026.2018.09.020

带队列约束的RHFS列生成调度算法

周炳海，王科

(同济大学机械与能源工程学院，上海201804)

收稿日期:2017-05-18 修回日期:2017-05-18 出版日期:2018-09-15 发布日期:2018-09-12
通讯作者: 周炳海
作者简介:周炳海(1965-)，男，浙江浦江人，同济大学教授，博士生导师.冯明杰(1971-)，男，河南禹州人，东北大学副教授; 王恩刚(1962-)，男，辽宁沈阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(71471135).国家自然科学基金资助项目(51171041).

Column Generation Scheduling Algorithm of Reentrant Hybrid Flow Shops(RHFS) with Queue Constraints

ZHOU Bing-hai， WANG Ke

School of Mechanical Engineering， Tongji University， Shanghai 201804， China.

Received:2017-05-18 Revised:2017-05-18 Online:2018-09-15 Published:2018-09-12
Contact: ZHOU Bing-hai
About author:-
Supported by:
-

摘要/Abstract

摘要： 为有效提升多重入车间的生产效率，考虑实际生产中队列约束，提出了基于列生成算法的可重入混合流水车间的调度方法.首先对两阶段生产调度问题进行描述，以最小化工件总完成时间为优化目标，建立数学规划模型.针对该调度模型提出列生成算法，设计带多重决策的动态规划方法来求解工件级子问题，为更快收敛，主问题求解中采用自适应加速策略.在使用分支定界将得到的解整数化的过程中，构造列池并设计局部变异.最后，对各种不同问题规模进行了数值实验，结果表明所提出的调度算法是有效可行的.

关键词: 队列, 可重入, 列生成, 动态规划, 分支定界

Abstract: To effectively enhance the production efficiency of multi-reentrant workshop， the queue constraint was considered where products were processed layer by layer， and then a scheduling method of reentrant hybrid flow shops(RHFS)was proposed based on column generation algorithm. Firstly， a two-stage scheduling model of RHFS was described and a mathematical programming model was built with an objective of minimizing the total completion time. A column generation algorithm was developed and dynamic programming with multiple decision-making was designed to solve each sub-problem. Further， the adaptive accelerating strategy was applied to effectively improve the algorithm convergence. In the process of generating integral solutions by using branch-and-bound method， column pool was built and neighborhood mutation method was emploied. Finally， numerical experiments in different problem scales were carried out to analyze the proposed algorithm. Results verify the validness and feasibility of the proposed algorithm.

Key words: queue, reentrant, column generation, dynamic programming, branch-and-bound

中图分类号:

TP391

周炳海，王科. 带队列约束的RHFS列生成调度算法[J]. 东北大学学报:自然科学版, 2018, 39(9): 1315-1320.

ZHOU Bing-hai， WANG Ke. Column Generation Scheduling Algorithm of Reentrant Hybrid Flow Shops(RHFS) with Queue Constraints[J]. Journal of Northeastern University Natural Science, 2018, 39(9): 1315-1320.

参考文献

[1]Zhou B，Gao Z，Chen J.Scheduling algorithm of dual-armed cluster tools with residency time and reentrant constraints［J］.Journal of Central South University，2014，21(1):160-166.
[2]周炳海，石潇铭.带重入约束的双集束型晶圆制造设备调度算法［J］.东北大学学报(自然科学版)，2013，34(9):1305-1309.(Zhou Bing-hai，Shi Xiao-ming.Scheduling algorithm for double-cluster of wafer fabrication system with reentrant constraints［J］.Journal of Northeastern University(Natural Science)，2013，34(9):1305-1309.)
[3]Graves S C，Meal H C，Stefek D，et al.Scheduling of re-entrant flow shops［J］.Journal of Operations Management，1983，3(4):197-207.
[4]Hekmatfar M，Ghomi S M T F，Karimi B.Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan［J］.Applied Soft Computing，2011，11(8):4530-4539.
[5]Dugardin F，Yalaoui F，Amodeo L.New multi-objective method to solve reentrant hybrid flow shop scheduling problem［J］.European Journal of Operational Research，2010，203(1):22-31.
[6]Cho H M，Bae S J，Kim J，et al.Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm［J］.Computers & Industrial Engineering，2011，61(3):529-541.
[7]Jeong B，Kim Y D.Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times［J］.Computers & Operations Research，2014，47(47):72-80.
[8]Choi H S，Kim H W，Lee D H，et al.Scheduling algorithms for two-stage reentrant hybrid flow shops:minimizing makespan under the maximum allowable due dates［J］.International Journal of Advanced Manufacturing Technology，2009，42(9/10):963-973.
[9]Wu K，Zhao N，Gao L，et al.Production control policy for tandem workstations with constant service times and queue time constraints［J］.International Journal of Production Research，2016，54(21):6302-6316.
[10]Wu K.Classification of queueing models for a workstation with interruptions:a review［J］.International Journal of Production Research，2014，52(3):902-917.
[11]An Y J，Kim Y D，Choi S W.Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times［J］.Computers & Operations Research，2016，71(1):127-136.
[12]Nishi T，Izuno T.Column generation heuristics for ship routing and scheduling problems in crude oil transportation with split deliveries［J］.Computers & Chemical Engineering，2014，60(2):329-338.
[13]Tas D，Gendreau M，Dellaert N，et al.Vehicle routing with soft time windows and stochastic travel times:a column generation and branch-and-price solution approach［J］.European Journal of Operational Research，2014，236(3):789-799.(上接第1265页)
[7]Baker A R，Greenaway A M，Ingram C W.A microwave digestion-based determination of low molecular weight organic acids in Bayer process liquor ［J］.Talanta，1995，42(10):1355-1360.
[8]Power G，Loh J S C，Vernon C.Organic compounds in the processing of lateritic bauxites to alumina:part 2:effects of organics in the Bayer process ［J］.Hydrometallurgy，2012，127/128:125-149.
[9]Pan X L，Yu H Y，Tu G F，et al.Effects of precipitation activity of desilication products (DSPs) on stability of sodium aluminate solution ［J］.Hydrometallurgy，2016，165:261-269.
[10]潘晓林，蒋涛，侯宪林，等.拜耳法过程水合铝硅酸钠析出活性研究［J］.中国有色金属学报，2017，27(8):1748-1755.(Pan Xiao-lin，Jiang Tao，Hou Xian-lin，et al.Precipitation activity of sodium aluminosilicate hydrate during the Bayer process ［J］.The Chinese Journal of Nonferrous Metals，2017，27(8):1748-1755.)

[1]	井元伟，白云. 基于事件触发的TCP网络滑模控制[J]. 东北大学学报（自然科学版）, 2021, 42(4): 457-462.
[2]	潘卫平，樊治平，黄敏. 二维板材圆形件剪冲的四块排样算法[J]. 东北大学学报（自然科学版）, 2021, 42(11): 1650-1655.
[3]	姜旭艳，严锦立，全巍，孙志刚. SSA:一种面向CQF模型的TSN资源调度算法[J]. 东北大学学报:自然科学版, 2020, 41(6): 784-791.
[4]	王青，田维西，顾晓薇，秦宗琛. 不同市场条件下金属露天矿分期方案动态优化[J]. 东北大学学报:自然科学版, 2018, 39(7): 1044-1048.
[5]	张瑞友，潘卫平，刘士新. 基于匀质块五块模式的矩形件非剪切排样算法[J]. 东北大学学报:自然科学版, 2018, 39(6): 771-775.
[6]	赵海，郭红叶，司帅宗，朱剑. Platoon车辆自动控制方法及性能分析[J]. 东北大学学报:自然科学版, 2018, 39(6): 781-786.
[7]	杨明，罗艳红，王义贺. 模型未知非零和博弈问题的策略迭代算法[J]. 东北大学学报:自然科学版, 2015, 36(3): 318-322.
[8]	王海英，丁华，张翠华，王琳. 具有能力约束的供应链系统模型[J]. 东北大学学报:自然科学版, 2015, 36(2): 288-291.
[9]	靳绍珍，毛志忠，李鸿儒. 基于情景方法的微型智能电网经济运行的优化[J]. 东北大学学报:自然科学版, 2015, 36(11): 1521-1525.
[10]	叶成荫，井元伟，郑艳，褚俊霞. 基于终端滑模控制的有限时间拥塞控制[J]. 东北大学学报:自然科学版, 2014, 35(6): 761-765.
[11]	王涛，罗艳红. 带饱和执行器的非线性离散时滞系统的最优控制[J]. 东北大学学报:自然科学版, 2014, 35(4): 461-464.
[12]	顾晓薇，胥孝川，王青，刘剑平. 金属露天矿生产计划优化算法的改进[J]. 东北大学学报:自然科学版, 2014, 35(10): 1492-1495.
[13]	顾晓薇，胥孝川，王青，郑友毅. 露天煤矿生产计划优化[J]. 东北大学学报(自然科学版), 2013, 34(8): 1184-1187.
[14]	陈小林，袁国，王昭东，王国栋. 新一代中厚板轧后冷却系统中队列存储技术的应用[J]. 东北大学学报(自然科学版), 2013, 34(2): 227-230.
[15]	张欣;会国涛;罗艳红;. 基于ADP方法求解未知非线性零和微分对策问题[J]. 东北大学学报(自然科学版), 2012, 33(12): 1673-1676+1689.

带队列约束的RHFS列生成调度算法

Column Generation Scheduling Algorithm of Reentrant Hybrid Flow Shops(RHFS) with Queue Constraints

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价