Graph model and three-stage scheduling strategy for ship block storage yards
CHEN Junyu, TIAN Ling, DAI Jingzhou
Beijing Key Lab of Precision/Ultra-precision Manufacturing Equipment and Control, Department of Mechanical Engineering, Tsinghua University, Beijing 100084, China
Abstract：Effective ship block yard scheduling is important for managing logistics costs in block construction. However, previous storage yard models have not been able to accurately describe the turns of flat transporters in storage yards which limits the scheduling effectiveness. Such scheduling strategies are only applicable to improving the efficiencies of small storage yards. A storage yard graph model was developed in this study with a node that integrates the cell position and the pose of the flat transporter so that the turns are accurately described. A fast, three stage strategy was then used to solve the scheduling scheme. The inbound block cell assignment is improved by decoupling the inbound order from the assignment order and incorporating an obstructive block prediction algorithm. Simulation of multi-yard scheduling in a shipyard scale model reduced the unproductive yard transfer rate to 10%, which shows the effectiveness of this storage yard model and the three-stage scheduling strategy.
[1] PARK C, SEO J, KIM J, et al. Assembly block storage location assignment at a shipyard: A case of hyundai heavy industries[J]. Production Planning & Control, 2007, 18(3): 180-189. [2] PARK C, SEO J. Assembly block storage location assignment problem: Revisited[J]. Production Planning and Control, 2009, 20(3): 216-226. [3] PARK C, SEO J. Mathematical modeling and solving procedure of the planar storage location assignment problem[J]. Computers & Industrial Engineering, 2009, 57(3): 1062-1071. [4] PARK C, SEO J. Comparing heuristic algorithms of the planar storage location assignment problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2010, 46(1): 171-185. [5] ZENG J Z, ZHANG Z Y. Block stockyard scheduling and optimizing based on an intelligent algorithm[J]. Journal of Harbin Engineering University, 2016, 37(1): 41-47. (in Chinese) 曾建智, 张志英. 基于智能算法的船舶分段堆场调度计划与优化[J]. 哈尔滨工程大学学报, 2016, 37(1): 41-47. [6] ZENG J Z, ZHANG Z Y, XING Y, et al. Block stockyard scheduling and optimization with single time window based on dual-layer genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2016, 22(9): 2165-2174. (in Chinese) 曾建智, 张志英, 邢艳, 等. 基于双层遗传算法的单时间窗分段堆场调度计划与优化[J]. 计算机集成制造系统, 2016, 22(9): 2165-2174. [7] ZHANG Z Y, JI F, ZENG J Z. Block stockyard scheduling approach based on an improved genetic algorithm[J]. Journal of Harbin Engineering University, 2015, 36(8): 1103-1108. (in Chinese) 张志英, 计峰, 曾建智. 基于改进GA的分段堆场计划调度方法研究[J]. 哈尔滨工程大学学报, 2015, 36(8): 1103-1108. [8] ZHANG Z Y, SHEN G, LIU X R, et al. Block storage yard scheduling of shipbuilding based on shortest-path algorithm[J]. Computer Integrated Manufacturing Systems, 2012, 18(9): 1982-1990. (in Chinese) 张志英, 申钢, 刘祥瑞, 等. 基于最短路算法的船舶分段堆场调度[J]. 计算机集成制造系统, 2012, 18(9): 1982-1990. [9] ZHANG Z Y, XU J X, JI F. Shipbuilding yard scheduling approach based on genetic algorithm[J]. Journal of Shanghai Jiaotong University, 2013, 47(7): 1036-1042. (in Chinese) 张志英, 徐建祥, 计峰. 基于遗传算法的船舶分段堆场调度研究[J]. 上海交通大学学报, 2013, 47(7): 1036-1042. [10] ZHANG Z Y, ZENG J Z. Obstructive block stockyard scheduling and optimization based on heuristic rules[J]. Journal of Harbin Engineering University, 2016, 37(10): 1416-1423. (in Chinese) 张志英, 曾建智. 基于启发式规则的临时分段调度计划与优化[J]. 哈尔滨工程大学学报, 2016, 37(10): 1416-1423. [11] TAO N R. Research on resouce scheduling problems during ship block assembly process[D]. Shanghai: Shanghai Jiao Tong University, 2013. (in Chinese) 陶宁蓉. 船舶分段建造过程中的资源调度优化研究[D]. 上海: 上海交通大学, 2013. [12] CHEN K. Research and application of block storage yard scheduling[D]. Shanghai: Shanghai Jiao Tong University, 2016. (in Chinese) 陈凯. 船舶分段堆场调度研究与应用[D]. 上海: 上海交通大学, 2016. [13] CHEN K, JIANG Z H, LIU J F, et al. Shipbuilding yard scheduling with block inbound time window[J]. Journal of Shanghai Jiaotong University, 2016, 50(9): 1390-1398. (in Chinese) 陈凯, 蒋祖华, 刘建峰, 等. 带有进场时间窗的船舶分段堆场调度[J]. 上海交通大学学报, 2016, 50(9): 1390-1398. [14] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
2022, Vol. 62 
