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

doi:10.12068/j.issn.1005-3026.2018.09.020

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

CLC Number:

TP391

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.

References

[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]	JING Yuan-wei， BAI Yun. Sliding Mode Control of TCP Network Based on Event-Triggered [J]. Journal of Northeastern University(Natural Science), 2021, 42(4): 457-462.
[2]	PAN Wei-ping， FAN Zhi-ping， HUANG Min. Four-Block Layout Algorithm for Two-Dimensional Plate Shearring and Punching of Circular Parts [J]. Journal of Northeastern University(Natural Science), 2021, 42(11): 1650-1655.
[3]	LIU Jun， LI Guo-jia， WANG Jing， LI Zi-nan. Channel Assignment Strategy for Low Earth Orbit Satellite Communication [J]. Journal of Northeastern University Natural Science, 2019, 40(6): 807-812.
[4]	WANG Qing， TIAN Wei-xi， GU Xiao-wei， QIN Zong-chen. Dynamic Optimization of the Staging Scheme of Open-Pit Metal Mines in Different Market Conditions [J]. Journal of Northeastern University Natural Science, 2018, 39(7): 1044-1048.
[5]	ZHANG Rui-you， PAN Wei-ping， LIU Shi-xin. Non-guillotine Cutting Algorithm of Rectangular Items Based on Five-Homogeneous-Block Mode [J]. Journal of Northeastern University Natural Science, 2018, 39(6): 771-775.
[6]	YANG Ming， LUO Yan-hong， WANG Yi-he. Policy Iteration Algorithm for Nonzero-Sum Games with Unknown Models [J]. Journal of Northeastern University Natural Science, 2015, 36(3): 318-322.
[7]	WANG Hai-ying， DING Hua， ZHANG Cui-hua， WANG Lin. Combined Model in Supply Chain with Capacity Constraint [J]. Journal of Northeastern University Natural Science, 2015, 36(2): 288-291.
[8]	YE Chengyin， JING Yuanwei， ZHENG Yan， CHU Junxia. FiniteTime Congestion Control Based on Terminal Sliding Mode Control [J]. Journal of Northeastern University Natural Science, 2014, 35(6): 761-765.
[9]	WANG Tao， LUO Yanhong. Optimal Control for Nonlinear DiscreteTime Time Delay Systems with Saturating Actuators [J]. Journal of Northeastern University Natural Science, 2014, 35(4): 461-464.
[10]	ZHAO Hai， YAO Chengcheng， AI Jun， JIA Siyuan. Research on the Bottleneck Delay of Internet IPLevel Topology [J]. Journal of Northeastern University Natural Science, 2014, 35(1): 38-41.
[11]	ZHOU Binghai， SHI Xiaoming. Scheduling Algorithm for DoubleCluster Tools of Wafer Fabrication System with Reentrant Constraints [J]. Journal of Northeastern University, 2013, 34(9): 1305-1309.
[12]	LIN Yongjie， YANG Xianfeng， ZOU Nan， JIA Lei. New Passive Transit Signal Priority Control Strategy for the Bus Vehicles at Urban Arteries [J]. Journal of Northeastern University, 2013, 34(9): 1227-1231.
[13]	GU Xiaowei， XU Xiaochuan， WANG Qing， ZHENG Youyi. Production Schedule Optimization in OpenPit Coal Mine [J]. Journal of Northeastern University, 2013, 34(8): 1184-1187.
[14]	CHEN Xiaolin， YUAN Guo， WANG Zhaodong， WANG Guodong. Application of Queue Storage Technology in ADCOSPM [J]. Journal of Northeastern University, 2013, 34(2): 227-230.