基于启发式规则的临时分段调度计划与优化

张志英,曾建智

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



基于启发式规则的临时分段调度计划与优化

张志英,曾建智

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

船舶堆场中临时分段调度方案的优劣影响着调度的效率和成本。本文以临时分段的调度过程为优化对象，以平板车的移动距离为优化目标建立数学模型。通过制定动态的临时分段调度规则和超长分段调度规则，充分利用堆场中的空存储单元，最终确定一个较优的临时分段调度方案。同时利用任务合并对堆场调度的任务序列进行优化，从而减少调度过程中临时分段的数量。最后，利用某船厂的实际数据对模型和调度规则进行实例验证和数值分析，结果表明，所制定的调度规则可以优化堆场调度方案，提高堆场空间资源利用率和调度效率。

堆场；调度规则；超长分段；任务合并；启发式规则

在大中型船舶的设计阶段，因为生产资源和工艺的约束，一艘船通常被分割为200个左右的分段，这些分段分别进行独立的生产建造，最后在船坞进行搭载。由于船舶企业生产和管理的原因，各个分段在不同加工工序之间无法即时周转，堆场便作为暂存或者预处理(预舾装、检验和修补等)分段的场所。作为中间产品的分段规格约为15 m×15 m×5 m，重量为100～300 t，有些特殊规格的分段甚至超过500 t。因此需要专门的搬运设备(平板车)对分段进行运输和调度。平板车只能进行平面方向上的运输，且一次只能搬运一个分段，它利用液压装置将分段提升，通过堆场中的可行路径，将分段移动至目标位置并放置支撑杆上。在船舶堆场调度过程中，根据作业流程可分为三种分段：进场分段、出场分段和临时分段。对于临时分段的处理是无增值的操作，且对其采用不同的调度规则会直接影响平板车的调度效率以及整个堆场的调度计划，因此对于临时分段如何制定一个科学、合理的调度规则尤为重要。

分段堆场一般为若干个大小相等的正方形场地组成的一个矩形区域，每一个场地为一个存储单元。一个存储单元一般存放一个分段(常规分段)，但是船舶分段的尺寸不尽相同，对于一些超长规格的分段，将占用一个以上的存储单元。这些分段成为临时分段时，其调度复杂程度将远远大于常规分段，堆场需要为其制定相应的调度方法。Changkyu等[1-2]以临时分段移动数量为优化目标建立模型，并运用遗传算法和改进动态启发式算法对模型进行求解。Tao等[3]在此基础上考虑分段进出堆场任务顺序对调度方案的影响，并运用启发式算法和禁忌搜索对结果进行优化。以上研究通过制定相应的规则对临时分段的位置进行重新选择，虽然提高堆场的空间利用率，但是临时分段可能阻碍其他分段的移动，增加了调度难度且效率不高。申钢等[4]以最小化临时分段移动量和平板车在堆场中的行驶距离为优化目标建立优化模型，并运用分支定界法和启发式规则来确定分段的移动路径和停放位置。平板车移动路径中的临时分段先移至堆场外暂存，待分段调度完成后再移回原来位置。徐建祥等[5]提出利用临时场地用于暂时存放临时分段并在任务结束后移回原来位置。以上研究对临时分段都采用了重回原位的调度策略，对堆场空存储单元并没有充分的利用，堆场调度过程是一个静态的过程，堆场的空间资源利用率不高。而且每一个调度任务结束后都需将暂存在堆场外的临时分段移回，可能再次影响后续的调度任务。对于特殊规格分段的研究，Tao[6]考虑了超重分段的调度，当分段重量大于平板车的额定载重时，采用两辆平板车协同调度的方法并制定了相应的平板车指派规则，但其研究的是船厂中车间与车间和车间与堆场之间的调度流程优化，并没有对堆场内部的调度进行细化的研究。

本文通过对临时分段的调度过程进行研究，提出动态的临时分段调度规则，并针对超长分段，研究相应的调度方法。同时还对调度时间差在规定可接受时间范围内的任务进行任务合并，最终得到一个科学、合理的堆场调度方案，并用某船厂的实际数据对以上调度规则的合理性进行验证。

1 问题描述与解决方法

1.1 问题描述

船舶分段堆场的调度与集装箱堆场的调度[7]相似，但其属于平面调度[8]。分段堆场的调度操作包括分段的存放和取回，由于平板车运输的局限性[9]，在存放和取回分段的路径中会遇到阻挡其前进的分段(临时分段)，必须将这些分段移动至平板车调度路径之外，才能完成后续的调度工作。对于临时分段的处理一般有移至暂存场所待分段调度完成后移回原位和移至堆场的其他空存储单元进行存放。但这两种方法都需要将临时分段移出堆场，使得平板车的移动距离较远、调度时间较长，从而导致堆场的调度效率不高。因此需要对临时分段的调度方法进行优化。

船舶设计过程中由于建造工艺要求特殊[10]，船舶艏、艉部的分段其规格与大部分常规分段有所不同，其中有部分超长分段，这些分段需要占用的存储单元数较多且连续，更容易成为临时分段。因此需要根据分段的形状特性来进行相应的调度。

分段堆场调度中每一个分段都有其相应的调度时间，而由于堆场空间资源的有限性，一些调度时间较晚的分段不可避免的会存放于调度时间较早分段的移动路径上，成为了临时分段。这样在调度过程中会产生大量不必要的临时分段，从而增加了堆场的运作成本。

考虑到堆场运作的实际情况和研究问题的方便，作了以下假设：1)船舶分段堆场由若干个面积相等的正方形场地组成，每个正方形场地为一个存储单元；2)分段用最小包络矩形近似；3)一个存储单元只能存放一个分段；4)每个存储单元能容下各种常规分段；5)超长分段需要两个相邻的存储单元进行存放；6)调度时间差在可接受范围内的调度任务可以进行任务合并；7)所有分段按“笔直型”路径进出堆场。

根据以上假设，本文拟解决的问题有：1)确定堆场调度计划中所产生临时分段的具体调度过程；2)调度过程中超长分段的调度方案；3)对计划调度周期内分段的调度任务序列进行优化。

1.2 解决方法

本文针对以上问题，首先研究了临时分段动态的调度规则，对临时分段采取移动至相邻的空存储单元的调度方法；其次对于超长分段也提出了相应的调度规则，通过平板车的旋转、平移等操作对超长分段进行调度；最后以临时分段移动距离为优化目标，利用以上调度规则优化堆场一段调度时间内的调度过程。本文还根据堆场的实际情况，对调度时间相近的任务进行任务合并，优化堆场分段调度计划的任务序列。分段调度流程如图1所示。

图1 分段调度流程图Fig.1 Block scheduling flow chart

2 建立船舶分段堆场调度模型

2.1 分段堆场存储单元位置编码

船舶分段堆场由若干个大小相同的正方形场地组成，每一个场地为一个存储单元。存储单元的位置编码方式为临近道路的位置开始从左至右，从上至下依次编码，如图2所示，堆场被划分成M行N列，即堆场有M×N个存储单元，存储单元位置编码从1至M×N。

图2 存储单元位置编码Fig.2 Position coding of storage unit

2.2 堆场状态二进制矩阵

为了表示分段在堆场中的停放位置及堆场存储单元的状态，建立堆场状态二进制矩阵。矩阵Ht的每个元素bVi表示调度时刻t堆场中存储单元位置为Vi的状态，bVi=1表示存储单元内已有分段存放，bVi=0表示该时刻存储单元状态为空。

2.3 堆场状态的更新

2.4 堆场调度模型

模型中的符号如下：

M、N分别表示堆场在宽度和长度上被划分的存储单元数量，堆场中存储单元的总数为M×N；

D：堆场存储单元的规格D×D；

W：堆场至暂存堆场的距离；

(Lg，Wg)：分段g的几何投影参数，其中g∈R；

T：堆场的调度周期；

ts：调度周期T的开始时间；

te：调度周期T的结束时间；

Vi：分段i在堆场中的位置；

tRi：分段Ri的调度时间；

决策变量：

目标函数：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

目标函数(1)根据不同规格的分段计算出堆场每次调度时临时分段的移动距离，并利用所对应的调度规则选择每个临时分段的最优调度方法，使整个调度周期内，对于临时分段平板车的移动距离最小。同时，根据任务合并的规则，对整个调度计划内的任务调度序列进行优化。

约束(2)限制堆场每次只能执行一个调度任务；约束(3)限定临时分段与调度分段之间的相互位置关系；约束(4)表示超长分段的尺寸与存储单元大小的关系；约束(5)、(6)规定了不同规格类型的分段所分配的存储单元个数，即常规分段分配一个确定的存储单元，超长分段需要两个相邻的存储单元才能满足其存放空间需求。约束(7)确保分段的调度时间在规定的调度周期内。

3 基于启发式规则的堆场调度模型求解

3.1 临时分段动态调度规则

现有堆场调度对于临时分段的处理一般将其移至堆场外的暂存堆场，等调度结束后再将分段移回原位。这样的调度方法不仅平板车移动距离远，而且占用堆场以外的其他资源。将临时分段重新选位能有效的提高对堆场资源的利用率，但是该调度方法较为繁杂。因此，本文对临时分段采取动态的调度规则，即利用临时分段相邻的空存储单元进行合理调度。

图3 临时分段调度规则Fig.3 Scheduling rule of the obstructive blocks

3.2 超长分段调度规则

对于超长分段的存放位置VSi作以下规定：若超长分段Si平行于道路存放(pSi=1)，那么该分段的存放位置用分段左端所占的存储单元位置表示；若超长分段Si垂直于道路存放(pSi=0)，则该分段的存放位置用分段上端所占的存储单元位置表示。

平板车在堆场中除了平移，还可以通过旋转操作将超长分段以OSi为中心进行旋转，从而完成后面存储单元上存放分段的调度任务。若分段调度路径中存在超长分段，即临时分段为超长分段的情况，为此提出以下调度规则：

5)超长分段垂直于道路存放，即pSi=0，则按照常规分段的调度规则对其进行调度。

图4 超长分段调度方法Fig.4 Scheduling method of the ultra-long blocks

3.3 任务合并规则

在堆场中两分段Ri与Rj，若在调度中存在以下关系：分段Rj在分段Ri的移动路径上，且分段Ri的调度时间早于分段Rj。这样分段Rj便成为了临时分段，需要利用平板车将其移动至其他位置来完成对分段Ri的调度。但若这两个调度分段的调度时间差在一个可以接受的时间范围δ内，便可以将这两个调度任务合并，即忽略两者的调度时间顺序，根据它们的存放位置关系依次进行调度。如图5所示。

图5 任务合并示例Fig.5 Task merging sample

(8)

(9)

(10)

(11)

式(8)表示两调度分段之间的时间约束关系；式(9)、(10)说明了两调度分段之间的位置关系；式(11)限定两个任务合并的分段的调度时间差必须在δ内，否则两个任务不能合并。满足以上条件的任务可以进行合并，即taski=taskj。

4 实例验证与结果分析

4.1 实验验证与结果

为了验证本文调度模型以及规则的可行性与正确性，以上海某大型船厂调度周期内一段时间的分段调度为例，利用MicrosoftVisualStudio2010软件，在处理器为2.40GHz，内存为4GB的计算机上进行求解。实验包括以下输入参数：1)堆场调度前的二进制状态矩阵；2)60h内所需调度的分段及其具体调度时间(表1)；3)堆场调度允许任务合并的最大时间差δ=3h。某堆场调度前的状态如图6所示，堆场的参数为M=6，N=10，即堆场由60个存储单元构成，初始负载率为65%，Bx是已存放在堆场存储单元上分段的编号。

按照调度时间顺序排列的调度计划如表1所示，调度分段的数量为30个，其中进场分段13个(常规分段用A1至A10依次编号，超长分段用S1至S3编号)，出场分段17个(用Bx表示)，为了便于区分，调度过程中遇到的临时分段用Bx表示。

通过算法程序确定调度分段进出堆场时所产生的临时分段，用本文研究的调度规则对临时分段、超长分段的具体调度过程进行优化，同时将任务合并的规则运用到调度中，得到一种较优的堆场临时分段调度方案，如表2所示，其中阴影部分表示任务进行了合并，任务合并减少的临时分段由△表示。若取D=15m、W=10m，该调度方案的临时分段移动距离为656.3m，其中平板车对超长临时分段进行了3次旋转调度操作，采用任务合并后临时分段数量减少了9个。

图6 堆场初始状态Fig.6 Stockyard initial state

表1 堆场调度计划

表2 堆场调度方案

4.2 数值分析

4.2.1 任务合并对减少临时分段的影响

任务合并可以有效的减少调度过程中临时分段的数量，而且任务允许任务合并的最大时间差δ和调度分段的数量都会影响最终的优化效果。为了比较不同参数下任务合并对减少临时分段的影响，在δ为2、3、4、5 h，调度规模分别为60、80、100个分段的参数下共进行了12组试验，其中各个分段的调度时间由[0,60 h]随机生成。为了保证更好的试验效果，对每组试验进行5次，并取平均值。

图7 任务合并试验结果Fig.7 Test results of task-merging

试验结果如图7所示，通过对堆场调度过程进行合理的任务合并，可以有效的减少调度过程中临时分段的调度数量。随着可接受任务合并时间差δ从2 h逐渐增加至5 h，临时分段的减少百分比也相应的增加，而且相同的调度周期内，任务数量越多，任务合并的效果也约为明显。但任务合并使一段时间内同时出场的分段数量增多，受后续工序的空间资源的制约，若δ值过大，例如δ=8 h时，一段时间内由于任务合并造成的同时出场分段的最大数量为5个，因此会引发场地堵塞等问题。

4.2.2 堆场存储单元空置率e

在一定的调度周期内，堆场中一些存储单元始终处于空置状态，使得堆场的空间资源利用率不高，因此通过堆场存储单元空置率可以反映出调度规则对堆场空间资源的利用情况，一个合理、高效的调度计划会对堆场的存储空间充分的利用。给出空置率的定义为

式中：Nume表示调度周期内堆场中始终没有被用于存储分段的存储单元个数，M、N分别表示堆场的行数和列数。

为了比较不同调度规则和不同规模(40、50、60个分段)对存储单元空置率影响，在堆场规格为6×10，初始负载率为65%的堆场中，分别运用不同的调度规则进行试验，得到结果如图8所示，可以看出制定的动态调度规则对于降低堆场空置率有一定的效果，且随着调度规模的增加，效果更佳。虽然采用该调度规则空置率高于重新选位调度规则(位置随机选择)时的空置率，但是临时分段采用重新选位的调度规则，会增加平板车的运输距离，增加了调度计划的复杂度。因此该调度规则对于降低堆场存储单元空置率，提高堆场空间资源利用率有一定的效果。

临时分段动态调度规则在不同堆场初始负载率时的调度效果也有所不同，因此试验比较了不同初始负载率下(60%、70%、80%、90%)采用动态调度规则相比于移出暂存规则堆场空置率e的优化幅度。试验的其他输入参数为：1)调度规模：50个分段；2)M=6，N=10。

图8 堆场空置率试验结果Fig.8 Test results of Nume

对比结果如图9所示，在堆场初始负载率较低时(60%、70%、80%)动态调度规则相比于将临时分段移出堆场暂存待分段调度完成后移回堆场的调度方式对堆场存储单元空置率的优化效果较为明显。但堆场负载率较高时(90%)，本文的调度规则优化效果则不明显，原因是该调度规则需要利用堆场中闲置的存储单元，一旦堆场的负载率过高，堆场中空存储单元数量也相应减少，这样也就无法发挥动态调度的优势。

图9 空置率优化幅度Fig.9 Optimization effect of Nume

4.2.3 调度规则对比

临时分段的移动量是评价堆场调度方案优劣的标准，对于临时分段的处理一般有：1)移出堆场暂存；2)重新选位。本文采用动态的调度规则，将临时分段移动至相邻的存储单元进行存储。如图10所示，临时分段的移动距离相比于其他调度规则有所下降，而且随着调度分段数量的增加，该调度规则的优势也更加的明显。

图10 不同调度规则对比Fig.10 Comparison of different scheduling rule

4 结论

本文通过对船舶分段堆场的调度过程进行研究，得出以下结论：

1)通过对堆场调度过程进行合理的任务合并，可以有效地减少调度过程中临时分段的调度数量；

2)在较低的堆场初始负载率时本文的调度规则对堆场存储单元空置率的优化效果较为明显；

3)本文将临时分段移动至相邻的存储单元进行存储，在调度规模较大时，优势更为明显。

[1]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.

[2]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.

[3]TAO Ningrong, JIANG Zuhua, QU Shipeng. Assembly block location and sequencing for flat transporters in a planar sto-rage yard of shipyards[J]. International journal of production research, 2013, 51(14): 4289-4301.

[4]张志英, 申钢, 刘祥瑞. 基于最短路算法的船舶分段堆场调度[J]. 计算机集成制造系统, 2012, 18(9): 1982-1990.

ZHANG Zhiying, SHEN Gang, LIU Xiangrui. Block storage yard scheduling of shipbuilding based on shortest-path algorithm[J]. Computer integrated manufacturing systems, 2012, 18(9): 1982-1990.

[5]张志英, 徐建祥, 计峰. 基于遗传算法的船舶分段堆场调度研究[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.

[6]陶宁蓉. 船舶分段建造过程中的资源调度优化研究[D]. 上海: 上海交通大学, 2013.

TAO Ningrong. Research on resouce scheduling problems during ship block assembly process[D]. Shanghai: Shanghai Jiaotong University, 2013.

[7]BAZZAZI M, SAFAEI N, JAVADIAN N. A genetic algorithm to solve the storage space allocation problem in a container terminal[J]. Computers & industrial engineering, 2009, 56(1): 44-52.

[8]PARK C, SEO J. Genetic algorithm of the planar storage location assignment problem[J]. Journal of the Korean institute of industrial engineers, 2009, 35(2): 129-140.

[9]ROH M I, CHA J H. A block transportation scheduling system considering a minimisation of travel distance without loading of and interference between multiple transporters[J]. International journal of production research, 2011, 49(11): 3231-3250.

[10]BANERJEE S K. Shipyard production systems design: a statistical approach[J]. International journal of production research, 1979, 17(6): 541-555.

Obstructive block stockyard scheduling and optimization based on heuristic rules

ZHANG Zhiying，ZENG Jianzhi

(School of Mechanical Engineering, Tongji University, Shanghai 201804, China)

The scheduling scheme of the obstructive blocks in the shipyard determined the efficiency and the cost of the stockyard scheduling operations. This paper took the scheduling process of the obstructive blocks as an optimization object. A mathematical model was established with the aim of minimizing the moving distance of the flat transporter. A dynamic scheduling rule for the obstructive blocks and the ultra-long blocks were proposed to make full use of the empty storage units, and which can ultimately obtain an optimal scheduling of the obstructive blocks. Meanwhile task-merging was used to optimize the sequence of the stockyard scheduling, thereby reducing the number of obstructive blocks during the scheduling process. Application data were acquired from a shipyard to validate the model and the scheduling rules, and the results showed that the proposed rules were effective to obtain a better stockyard scheduling scheme, and also improved the utilization of the space resource and scheduling efficiency.

stockyard; scheduling rules; ultra-long blocks; task-merging; heuristic rules

2015-08-06.

日期：2016-08-29.

国家自然科学基金项目(70872076)；上海市科技创新行动计划项目(11dz1121803).

张志英(1971- )，男，副教授.

张志英，E-mail：zyzhang08@tongji.edu.cn.

10.11990/jheu.201508010

网络出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160829.1421.032.html

O224；U673

A

1006-7043(2016)10-1416-08

张志英,曾建智. 基于启发式规则的临时分段调度计划与优化[J]. 哈尔滨工程大学学报， 2016, 37(10): 1416-1423.

ZHANG Zhiying，ZENG Jianzhi. Obstructive block stockyard scheduling and optimization based on heuristic rules[J]. Journal of Harbin Engineering University, 2016, 37(10): 1416-1423.