基于优先规则的船舶分段空间调度算法

doi:10.3969/j.issn.1007-7375.2020.02.010

摘要/Abstract

摘要： 为有效解决船舶分段的空间调度问题，提出了一种基于优先规则的求解算法。首先利用优先规则和禁忌搜索算法产生可行的分段调度序列，再采用一种启发式定位策略——最下最左填满策略对产生的调度序列进行解码，以评估调度序列的优劣。算法不断迭代，最终可得到近似最优解。对船厂的实际生产数据进行了实证分析，并与现有的算法进行了对比，验证了所提出的算法在空间调度问题上的有效性和优越性。

关键词: 空间调度, 禁忌搜索算法, 优先规则, 船舶分段

Abstract: To efficiently solve the spatial scheduling problem (SSP) for blocks in shipbuilding, a priority rule-based solution algorithm is proposed. Firstly, feasible scheduling sequences of blocks are generated by combining priority rules and the Taboo search algorithm. And then, these feasible scheduling sequences are decoded and evaluated using a heuristic location strategy, which is called the bottom-left-fill (BLF) strategy. The approximate optimal solution can be obtained in the process of algorithm iteration. Based on the actual data of a shipyard, an empirical analysis is carried out. The effectiveness and superiority of the proposed algorithm are verified by comparing with existing algorithms.

Key words: spatial scheduling, taboo search algorithm, priority rule, ship block

中图分类号:

TP391
U673

朱辉, 杨立乾, 赵金楼. 基于优先规则的船舶分段空间调度算法[J]. 工业工程, 2020, 23(2): 76-82.

ZHU Hui, YANG Liqian, ZHAO Jinlou. Priority Rule-based Spatial Scheduling Algorithm for Blocks in Shipbuilding[J]. Industrial Engineering Journal, 2020, 23(2): 76-82.

参考文献

[1] LEE K J, LEE J K, CHOI S Y. A spatial scheduling system and its application to shipbuilding: DAS-CURVE[J]. Expert Systems with Applications, 1996, 10(3-4): 311-324
[2] LEE J K, LEE K J, PARK H K, et al. Developing scheduling systems for Daewoo shipbuilding: DAS project[J]. European Journal of Operational Research, 1997, 97(2): 380-395
[3] PARK K, LEE K, PARK S, et al. Modeling and solving the spatial block scheduling problem in a shipbuilding company[J]. Computers & Industrial Engineering, 1996, 30(3): 357-364
[4] CHO K K, CHUNG K H, PARK C, et al. A spatial scheduling system for block painting process in shipbuilding[J]. CIRP Annals-Manufacturing Technology, 2001, 50(1): 339-342
[5] PARK C, CHUNG K H, PARK J C, et al. A spatial scheduling application at the block paint shop in shipbuilding: the HYPOS project[J]. Production Planning & Control, 2002, 13(4): 342-354
[6] SHIN J G, KWON O H, RYU C. Heuristic and metaheuristic spatial planning of assembly blocks with process schedules in an assembly shop using differential evolution[J]. Production Planning & Control, 2008, 19(6): 605-615
[7] 郭美娜, 李波. 基于树搜索的一种动态空间调度方法[J]. 计算机工程与应用, 2007, 43(14): 180-184
GUO Meina, LI Bo. Dynamic spatial scheduling approach based on tree-search[J]. Computer Engineering and Applications, 2007, 43(14): 180-184
[8] 张志英, 马姗静. 基于综合分解策略的船体分段空间调度方法[J]. 机械工程学报, 2010, 46(22): 189-194
ZHANG Zhiying, MA Shanjing. Approach on block spatial scheduling in shipbuilding based on integrated decomposition method[J]. Journal of Mechanical Engineering, 2010, 46(22): 189-194
[9] 聂兰顺, 靳金涛, 战德臣, 等. 基于配置空间理论的启发式空间调度算法[J]. 计算机集成制造系统, 2013, 19(10): 2590-2598
NIE Lanshun, JIN Jintao, ZHAN Dechen, et al. Heuristic spatial scheduling algorithm based on configuration space theory[J]. Computer Integrated Manufacturing Systems, 2013, 19(10): 2590-2598
[10] RAJ P, SRIVASTAVA R K. Solving spatial scheduling problem: an analytical approach[C]. Proceedings of the 37th International Conference on Computers and Industrial Engineering. Washington DC：Institute of Electrical and Electrics Engineers Inc., 2007: 2002-2011.
[11] RAJ P, SRIVASTAVA R K. Analytical and heuristic approaches for solving the spatial scheduling problem[C]. 2007 IEEE International Conference on Industrial Engineering and Electrical and Engineering Management. Singpore: Institute of Electrical and Electrics Engineers Inc., 2007: 1093-1097.
[12] GARCIA C, RABADI G. Exact and approximate methods for parallel multiple-area spatial scheduling with release times[J]. OR Spectrum, 2013, 35(3): 639-657
[13] KWON B, LEE G M. Spatial scheduling for large assembly blocks in shipbuilding[J]. Computers & Industrial Engineering, 2015, 89: 203-212
[14] 张志英, 陈洁. 空间调度问题的非线性规划分析求解方法[J]. 计算机集成制造系统, 2010, 16(6): 1272-1278
ZHANG Zhiying, CHEN Jie. Nonlinear programming approach for spatial scheduling problem[J]. Computer Integrated Manufacturing Systems, 2010, 16(6): 1272-1278
[15] VARGHESE R, YOON D Y. Dynamic spatial block arrangement scheduling in shipbuilding industry using genetic algorithm[C]. INDIN'05. 2005 3rd IEEE International Conference on Industrial Informatics. Perth, WA, Austrilia: Institute of Electrical and Electrics Engineers Inc., 2005: 444-449.
[16] KOH S, JANG J, KIM C, et al. GA-based spatial scheduling algorithm for mega-block assembly yard in shipbuilding company[C]. Proceedings of the 9th Asia Pacific Industrial Engineering & Management Systems Conference. Hanover, MD, USA: Informs, 2008.
[17] HU S, LIU T J, WANG S, et al. A hybrid heuristic algorithm for ship block construction space scheduling problem[J]. Discrete Dynamics in Nature and Society, 2015, 7: 1-6
[18] 张志英, 杨克开, 于瑾维, 等. 改进粒子群算法的动态空间调度方法[J]. 哈尔滨工程大学学报, 2009, 30(12): 1344-1350
ZHANG Zhiying, YANG Kekai, YU Jinwei, et al. Dynamic spatial scheduling approach based on improved particle swarm optimization algorithm[J]. Journal of Harbin Engineering University, 2009, 30(12): 1344-1350
[19] 马少辉, 王景秋, 陆春霞, 等. 动态空间调度的混合遗传算法[J]. 运筹与管理, 2013, 22(2): 99-104
MA Shaohui, WANG Jingqiu, LU Chunxia, et al. A dynamic spatial scheduling approach based on hybrid genetic algorithm[J]. Operation Research and Management Science, 2013, 22(2): 99-104
[20] 马少辉, 陆春霞. 船体不规则分段的动态空间调度算法[J]. 运筹与管理, 2014, 23(6): 281-287
MA Shaohui, LU Chunxia. A dynamic spatial scheduling algorithm for irregular blocks in shipbuilding[J]. Operation Research and Management Science, 2014, 23(6): 281-287
[21] 王东军, 刘翱, 刘克, 等. 基于优先规则的复杂并行机调度问题研究[J]. 系统工程理论与实践, 2016, 36(3): 779-786
WANG Dongjun, LIU Ao, LIU Ke, et al. Priority rule-based complex identical parallel machines scheduling[J]. Systems Engineering—Theory & Practice, 2016, 36(3): 779-786
[22] 刘振元, 王红卫. 基于优先规则的活动成本目标资源受限工程调度[J]. 系统工程理论与实践, 2006, 26(9): 99-106
LIU Zhenyuan, WANG Hongwei. Priority-rule-based resource constrained project scheduling with the objective of minimizing activities’ cost[J]. Systems Engineering—Theory & Practice, 2006, 26(9): 99-106
[23] 张松, 陈华平, 刘建. 复杂时间约束的水利工程项目调度问题研究[J]. 系统工程学报, 2016, 31(1): 135-144
ZHANG Song, CHEN Huaping, LIU Jian. Research on the complicated time-constrained project scheduling in water conservancy[J]. Journal of Systems Engineering, 2016, 31(1): 135-144
[24] 马英, 左春荣, 杨善林. 带不可用时间段和恶化加工时间的单机调度[J]. 系统工程学报, 2010, 25(3): 371-378
MA Ying, ZUO Chunrong, YANG Shanlin. Single machine scheduling with an availability constraint and deteriorating jobs[J]. Journal of Systems Engineering, 2010, 25(3): 371-378
[25] 王津剑, 杜吉旺, 范秀敏, 等. 复杂形状船舶分段建造空间调度优化算法[J]. 计算机集成制造系统, 2015, 21(11): 2945-2954
WANG Jinjian, DU Jiwang, FAN Xiumin, et al. Complex shape shipbuilding block spatial scheduling algorithm[J]. Computer Integrated Manufacturing Systems, 2015, 21(11): 2945-2954
[26] 张志英, 王蕾, 江志斌, 等. 面向船体曲面分段建造的空间调度方法[J]. 上海交通大学学报, 2008, 42(4): 569-573
ZHANG Zhiying, WANG Lei, JIANG Zhibin, et al. Spatial scheduling oriented to curved block in shipbuilding[J]. Journal of Shanghai Jiaotong University, 2008, 42(4): 569-573
[27] CHAZELLE B. The bottom-left bin-packing heuristic: an efficient implementation[J]. IEEE Transactions on Computers, 1983, C-32(8): 697-707
[28] HOPPER E, TURTON B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1): 34-57