针对船舶分段堆场调度中的堆场空间利用率低和作业调度效率低的现状，建立以最小阻挡分段移动数量为优化目标的组合分段堆场调度模型;提出一种基于位置权重的进场及阻挡分段堆位的分配策略；采用深度优先搜索与分段移动方向相结合的方式获取路径，并用遗传算法与禁忌搜索相结合的混合启发式算法优化任务分段的执行顺序；分析验证调度周期、场地规格及通行能力对调度结果的影响.实验结果表明：考虑组合分段的堆场可以处理的分段数量更多；优化堆位分配策略与混合启发式算法可以明显地提高堆场空间的利用率和调度效率，并能够有效地减少堆场调度中的阻挡分段数量.
In order to improve the low utilization ratio and processing efficiency of block scheduling in storage yard, a combined assembly block scheduling model was established. The optimal objective was to minimize the total number of obstructive blocks. This paper proposed a location selecting strategy for the incoming blocks and relocating blocks based on the location weight. Depth-first search algorithm and moving direction were combined to obtain the transportation route. Hybrid heuristic algorithm based on genetic algorithm and tabu search was used to improve the sequencing solution. Finally, the effects of scheduling period, size and traffic capacity of storage yard on the experimental results were analyzed. The experimental results show that the storage yard with combined block can handle more tasks. Moreover, the optimization of allocation strategy and hybrid heuristic algorithm can significantly improve the utilization ratio and scheduling efficiency of storage yard, while effectively reducing the number of obstructive blocks.
［1］陶宁蓉. 船舶分段建造过程中的资源调度优化研究［D］. 上海: 上海交通大学, 2013.
TAO Ningrong. Research on resource scheduling problems during ship block assembly process［D］. Shanghai: Shanghai Jiao Tong University, 2013.
［2］陈凯, 蒋祖华, 刘建峰等.带有进场时间窗的船舶分段堆场调度［J］.上海交通大学学报, 2016, 50(9): 1390-1398.
CHEN Kai, JIANG Zuhua, LIU Jianfeng, et al. Shipbuilding yard scheduling with block inbound time window［J］. Journal of Shanghai Jiao Tong University, 2016, 50(9): 1390-1398.
［3］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 and Control, 2007, 18(3): 180-189.
［4］PARK C, SEO J. Mathematical modeling and solving procedure of the planar storage location assignment problem［J］. Computers and Industrial Engineering, 2009, 57(3): 1062-1071.
［5］TAO N R, JIANG Z H, QU S P. Assembly block location and sequencing for flat transporters in a planar storage yard of shipyards［J］. International Journal of Production Research, 2013, 51(14): 4289-4301.
［6］张志英, 徐建祥, 计峰.基于遗传算法的船舶分段堆场调度研究［J］.上海交通大学学报, 2013, 47(7): 1036-1042.
ZHANG Zhiying, XU Jianxiang, JI Feng. Shipbuilding yard scheduling approach based on genetic algorithm［J］. Journal of Shanghai Jiao Tong University, 2013, 47(7): 1036-1042.
［7］王冲, 茅云生, 辛锺桂. 基于遗传算法的船舶分段运输调度方法［J］.上海交通大学学报, 2017, 51(3): 338-343.
WANG Chong, MAO Yunsheng, SHIN Jonggye. Ship block transportation scheduling approach based on genetic algorithm［J］. Journal of Shanghai Jiao Tong University, 2017, 51(3): 338-343.
［8］张志英, 计峰, 曾建智.基于改进GA的分段堆场计划调度方法研究［J］.哈尔滨工程大学学报, 2015, 36(8): 1103-1108.
ZHANG Zhiying, JI Feng, ZENG Jianzhi. Block stockyard scheduling approach based on an improved genetic algorithm［J］. Journal of Harbin Engineering University, 2015, 36(8): 1103-1108.
［9］周健, 曹瑞霞, 汪雄.分段堆场预测调度研究［J］.计算机工程与应用, 2013, 49(23): 221-227.
ZHOU Jian, CAO Ruixia, WANG Xiong. Shipbuilding yards predictable scheduling approach［J］. Computer Engineering and Applications, 2013, 49(23): 221-227.
［10］JOO C M, KIM B S. Block transportation scheduling under delivery restriction in shipyard using meta-heuristic algorithms［J］. Expert Systems with Applications, 2014, 41(6): 2851-2858.
［11］ZHENG J L, JIANG Z B, CHEN Q, et al. Spatial scheduling algorithm minimising make-span at block assembly shop in shipbuilding［J］. International Journal of Production Research, 2011, 49(8): 2351-2371.
［12］陆春霞. 船体不规则分段的动态空间调度及场地堆放问题研究［D］.江苏镇江: 江苏科技大学, 2013.
LU Chunxia. Research on irregular block dynamic spatial scheduling and stacking problem in shipbuilding industry［D］. Zhenjiang, Jiangsu: Jiangsu University of Science and Technology, 2013.
