基于订单总拖期的仓储作业调度建模与优化

仓储系统的作业分为备货作业和补货作业.备货作业是指根据订单, 将货物由存储位置运输至理货区, 它直接影响到仓储系统的服务水平, 因此, 本文只研究仓储系统的备货作业调度.备货作业分为2个操作阶段:① 由堆垛机将所需货物从存储位置运输至巷道口;② 由叉车将货物从巷道口运送至理货区.

一托盘货物在备货作业过程中的全部操作称为一个备货作业任务.一个备货订单包含若干个备货作业任务, 并包含一个订单下达时间和一个交货期.订单要求的货物全部运至理货区的时间为订单的完成时间.如果订单的完成时间晚于交货期, 则需承担相应的拖期费用, 拖期费用和订单的拖期量相关.

仓储系统作业流程固定, 且每个阶段都有多个平行设备.可以认为, 仓储系统的调度问题是混合流水车间 (Hybrid Flowshop, HFS) 调度问题.HFS调度和最小化总拖期调度都是NP问题[1,2,3], 一般采用启发式方法进行求解.Ruiz等[4]回顾了Flowshop问题常用的启发式方法, 并使用Taillard[5]提出的评价体系比较了各种启发式算法的有效性.Ronconi等[6]以作业任务总拖期最小化为目标使用了一种两阶段构造法求解带阻塞的Flowshop问题.Haouari等[7]分别使用禁忌搜索和模拟退火算法对两阶段HFS问题进行求解, 并与其他算法进行比较, 结果表明, 禁忌搜索有较好的表现.Negenman[8]针对HFS问题提出了几种简化的禁忌搜索算法.

目前调度方面的理论研究大多以最小化作业任务的完成时间或拖期为优化目标.然而在一些实际生产中, 系统同时处理多个订单, 每个订单包含多个作业任务.订单中单个作业任务的提前完成对订单的完成时间没有影响;而订单中一个作业任务的滞后则会造成整个订单的拖期.本文以各订单的总拖期时间为优化目标, 安排仓储系统的备货作业调度.这种调度目标更符合仓储系统的实际运作情况, 对实际作业具有指导意义.

本文模型中的仓储系统由堆垛机和叉车等设备, 以及货架和理货区等设施构成, 如图1所示.货架及其对应的堆垛机构成巷道, 是仓储系统的主体部分.

该问题为两阶段混合流水车间调度问题, 以各订单的总拖期最小化为目标.任务第1阶段的操作由货物所在巷道的堆垛机完成, 第2阶段的操作由叉车完成.堆垛机和叉车的运输容量均为一个托盘的货物.各阶段作业的准备时间为设备移动至货物位置的时间, 操作时间为设备装载货物并运输至指定地点的时间.

N为货物种类的集合, a∈N为其索引.k为操作阶段的索引, k∈{1, 2}.M为所有设备的集合, i∈M为设备的索引, Mk为第k阶段的设备的集合.出于货物的存储要求和方便管理方面的考虑, 规定同种货物存储在一个巷道内, 并在巷道内集中存储.ua为货物a的存储位置对应的堆垛机, ua∈M1.

O为订单的集合, l∈O为订单的索引.rl为订单l的下达时间, dl为订单l的交货时间.Cl为订单l的完成时间, 若Cl晚于dl, 则要承担相应的拖期成本.拖期量Tl=max{0, Cl-dl}.货物备货任务 (job) 的集合为J, j∈J为job的索引.Lj为j对应的订单编号, Lj∈O.Aj为j对应的货物种类, Aj∈N.cj, k为j第k阶段操作的完成时间.j第k阶段的操作时间为pj, k, 准备时间为qj, k.B为一个足够大的正数.

模型的决策变量如下:

xj, k, i为操作与机器的对应关系, 其值为1表示任务j第k阶段的操作在机器i上完成;其值为0表示其他;j∈J, k∈{1, 2}, i∈Mk.

yj, j′, k, i为两个操作之间的相互关系, 其值为1表示任务j和j′第k阶段的操作都在机器i上完成, 且j先于j′加工 (不一定连续) ;其值为0表示其他;j, j′∈J, k∈{1, 2}, i∈Mk.

zj, j′, k, i为两个操作之间的相互关系, 其值为1表示任务j和j′第k阶段的操作都在机器i上完成, 且j先于j′加工 (连续的) ;其值为0表示其他;j, j′∈J, k∈{1, 2}, i∈Mk.

式 (1) 为各订单的总拖期最小.式 (2) 规定了每个任务的每个阶段在且仅在一台机器上操作.式 (3) 以及 (4) 规定了当xj′, k, i=xj, k, i=1时, 有yj, j′, k, i+yj′, j, k, i=1, 其他情况下yj, j′, k, i+yj′, j, k, i=0.式 (5) 规定了当yj, j′, k, i=yj′, j″, k, i=1时, 有yj, j″, k, i=1.式 (6) 规定了2个任务j和j′在同一台设备上连续操作时满足yj, j′k, i=1.式 (7) 和 (8) 规定了xj, k, i和zj, j′, k, i的关系, 其中:式 (7) 表示若任务j在某台机器上操作, 则j在此机器上可能有一个相邻的后续任务;式 (8) 表示若某台机器上共有n个任务, 则该机器上有n-1组相邻任务.式 (9) 规定任务的开始时间不得早于该任务对应订单的下达时间.式 (10) 规定任务第2阶段的开始时间不早于第1阶段的结束时间.式 (11) 规定若1台设备连续加工2个任务, 则前一任务相应操作结束之后, 后续任务才能开始.式 (12) 表示堆垛机的阻塞情况.式 (13) 规定任务第1阶段的操作只能由存储此货物的巷道对应的堆垛机完成.式 (14) 规定订单中所有货物都运送至理货区的时间为该订单的完成时间.

本问题是两阶段HFS调度问题, HFS调度问题包含机器的选择和job的排序2个子问题.由于规定job第1阶段的操作只能由货物所在巷道对应的堆垛机完成, 故本问题有3个决策点:堆垛机上job的排序, 各job第2阶段操作的执行顺序以及叉车的选择.如图2所示, 在这3个决策点分别使用相应的规则进行调度, 即可得到调度问题的初始解.

本问题中, 订单内单个job的滞后完成会推迟整个订单的完成时间, 而订单中其他job的提前完成对订单的拖期量没有影响.因此, 在时间上集中安排同一个订单内的job, 有利于减小订单的拖期量.在此引入子订单的概念:订单l中在堆垛机i上操作的任务构成子订单sl, i={j∈J|Lj=l, uAj=i}, l∈O, i∈M1.根据上面的分析, 同一子订单内的任务需要集中执行, 同样, 同一订单内的不同子订单也需要集中执行.

下面根据问题的这一特性, 针对3个决策点分别设计了不同的启发式规则.根据数字实验, 选出最优秀的规则组合, 并用此生成调度问题的初始解.

(1) job在堆垛机上的排序规则.首先确定订单的执行顺序, 然后使堆垛机上各子订单的执行顺序Di (i∈M1) 与其保持一致, 而子订单中的job根据sj, 1+pj, 1按升序排列, 这样就得到了job在堆垛机上的执行顺序.其中确定订单执行顺序的规则有:

① ERD, 即把订单根据其下达时间按升序排列.

② EDD, 即把订单根据其交货期按升序排列.

③ 最晚开始时间规则, 即把各订单根据其估计最晚开始时间ts按升序排列.其中ts=dl-max Pl, i, 1, i∈M1, Pl, i, 1=∑pj, 1, j∈sl, i.Pl, i, 1为子订单sl, i在i上第1阶段加工时间的和.

(2) 确定各job第2阶段操作执行顺序的规则.

④ 最早可开始时间规则.任务j在巷道内的最早开始时间tj, 1=max{rLj, tj′, 2}, 其中rLj为任务j对应的订单下达时间, tj′, 2为堆垛机i上前一个任务j′第2阶段操作开始的时间.选择tj, 1最早的任务.

⑤ 最短子订单宽放时间规则.子订单sl, i的宽放时间gl, i=dl-tj, 1-P′l, i, 1.其中P′l, i, 1=∑pj, 1, j∈s′l, i, 为子订单sl, i中待安排部分s′l, i的第1阶段加工时间和.选择gl, i最短的子订单对应的任务.

⑥ 子订单最晚开始时间规则.子订单sl, i的估计最晚开始时间tsl, i=dl-P′l, i, 1.选择tsl, i最早的任务.

(3) 选择叉车的规则.

⑦ 最早空闲规则.叉车i的最早空闲时间为fi=cj′, 2, 其中j′为i上已安排的最后一个任务.选择fi最早的叉车.

⑧ 不延迟规则.按待安排的任务j第1阶段的完成时间cj, 1, 将叉车分为2个集合M21={i∈M2|fi≤cj, 1}, M22={i∈M2|fi>cj, 1}.若M21不为空, 则选择M21中fi最大的叉车;否则, 选择M22中fi最小的叉车.

根据选用的规则组合, 确定调度的初始解步骤如下:

(1) 使用相应规则确定job在堆垛机上的排序.

(2) Di中的首个未执行任务为堆垛机i的待安排任务.各堆垛机的待安排任务组成集合W.

(3) 选用第2阶段job的排序规则, 从W中选出1个job, 令其为j, 其对应子订单为sl, i.

(4) 使用选择叉车的规则确定服务j的叉车.

(5) 安排j的备货作业计划, 并从sl, i中删去j.若sl, i变为空, 则从堆垛机i的子订单执行序列Di中删去sl, i.

(6) 若各Di均为空, 则结束;否则, 返回 (2) .

3个决策点的不同规则一共有18种组合, 下面通过数字实验, 根据调度结果选出最适合的规则组合.

假设此仓储系统共存储60种货物并随机确定一种存储方案, 根据货物存储位置和设定的堆垛机速度确定第1阶段作业的准备时间和操作时间;根据设定的距离和叉车的速度确定第2阶段作业的准备时间和操作时间.每个算例包含10个订单;订单的下达时间rl服从[0, 4] h的平均分布;订单的交货时间dl服从rl+0.5∑Lj=l∑Lj=lpj, 1, rl+∑Lj=lpj,1∑Lj=lpj,1的平均分布;每个订单包含6种货物, 每种货物的需求数量服从[1]的平均分布;巷道的数量取10, 15, 20;叉车的数量取10, 15, 20.所有参数和规则组合生成162种问题, 针对每种问题分别采用10个算例进行计算, 其平均总拖期如表1所示.表中:规则组合栏的①～⑧分别对应2.1节中的8个规则;表中数值为在此资源状况下, 使用该规则组合进行调度的10次数字实验的订单总拖期的平均值, 单位为s;平均总拖期为该规则组合在9种资源状况下不同算例的平均总拖期;与最小值之比为该规则组合对应的平均总拖期与各规则组合的平均总拖期中的最小值之比.

由表可见, 所有的规则组合中, 规则组合③④⑦、③④⑧和③⑥⑧对应调度结果的平均总拖期最小.本文采用这3种规则组合生成调度问题的初始解.

在本问题中第1阶段的操作只能由货物所在巷道的堆垛机完成, 而且仓储系统一旦建成, 堆垛机资源不能再扩充.各子订单和job在第1阶段的排序对调度结果影响最大[9].因此, 本文提出一种禁忌搜索算法, 仅对子订单和任务在堆垛机上的排序进行调整, 对第2阶段的排序和机器的选择采用前文选定的规则组合进行调度.

此禁忌搜索分为2个阶段, 搜索的第1阶段在保证同一子订单内的job集中执行的基础上, 调整堆垛机上的子订单的执行顺序, 根据各订单总拖期选择最优的子订单执行顺序.第1阶段优化完成后进入第2阶段的禁忌搜索, 突破同一子订单的job集中执行的限制, 调整堆垛机上各job的排序.第1阶段的搜索能够快速地确定堆垛机上各子订单的执行顺序, 第2阶段则在前面优化结果的基础上进行进一步的搜索.算法的详细设计如下.

(1) 解的向量表示.对于HFS调度问题, 一个完整的计划Π由多个序列组成, Π=∪Πk, i, k∈{1, 2}, i∈Mk.Πk, i为第k阶段设备i上job的排序,

Πk,i=[πk,i(1)πk,i(2)⋯πk,i(nk,i)]Πk,i=[πk,i(1)πk,i(2)⋯πk,i(nk,i)]

其中, πk, i (n) 表示Πk, i中的一个job, nk, i=|Πk, i|表示Πk, i中job的数量.

本算法的搜索分为2个阶段, 在第1阶段的搜索中, 同一个子订单中的job在Π1, i中安排在一起, 因此堆垛机上的计划Π1, i又可表示为Γ1, i, i∈M1.其中Γ1, i=[γ1, i (1) γ1, i (2) … γ1, i (n1, i) ], γ1, i (n) 表示Γ1, i中的一个子订单, n1, i表示Γ1, i中子订单的数量, γ1, i (n) 中的job根据备货操作第1阶段的准备和操作时间之和按照升序排列.

(2) 邻域结构定义.本算法中邻域是通过在Γ1, i或Π1, i上移动子订单或job的位置来实现的.得到各job在堆垛机上的排序后, 可以根据前文选定的规则组合确定各阶段的计划.将Γ1, i中位于x的子订单移动到Γ1, i中的另一个位置y即可获得第1阶段搜索的邻域;将Π1, i中位于x的job移动到Π1, i中的另一个位置y即可获得第2阶段搜索中的邻域, i∈M1.

(3) 邻域操作方法.首先随机选中一个拖期的订单, 找到该订单中最晚完成的job及其对应的子订单sl, i, 则堆垛机i造成了订单l的拖期.将子订单sl, i在堆垛机i上的执行顺序提前, 则可以减少订单l的拖期量.第1阶段搜索的邻域操作方法:将Γ1, i中sl, i之前的一个子订单γ1, i (n) 移动到sl, i之后, 得到Γ′1, i, 如图3 (a) 所示.第2阶段搜索的邻域操作方法:将Π1, i中子订单sl, i之前紧邻的一个job移动到sl, i后面, 得到Π′1, i, 如图3 (b) 所示.在第2阶段的搜索中, 加入局部搜索的机制, 若进行该操作后订单总拖期有所降低, 则继续进行此类操作.

(4) 初始解的产生方法.使用前文选定的规则组合确定初始解.

(5) 解的评价方法.获得堆垛机上各job的排序后, 结合选定的规则组合可以得到完整的调度解和各订单的拖期量, 以各订单的总拖期作为解的评价指标.

(6) 禁忌列表.由于相同的排序会得到相同的调度计划, 因此在执行邻域操作之后, 将该邻域操作涉及的2个子订单放入禁忌列表中, 防止解的循环, 并跳出局部最优.

(7) 特赦准则.当目前的所有邻域操作均被禁忌时, 释放能够获得最优目标值的操作, 并将该调度解作为当前解, 以进行进一步的搜索.

(8) 终止准则.算法采用指定迭代步数的终止准则, 搜索结束时, 目标值最优的调度解即为禁忌搜索的最终结果.

表2所示为结合规则组合③⑥⑧, 在M1和M2分别为20和15台的情况下, 以2.3节的数据进行计算的结果.表中, 初始解列、第1和第2阶段禁忌搜索结果列分别为算例经过相应阶段计算后的结果.订单总拖期列为调度结果中全部订单的总拖期;拖期比为订单总拖期与订单总跨度的比值, 其中订单总跨度S=∑ (dl-rl) , l∈O;拖期订单比例为调度结果中拖期订单的数量占订单数量的比例;改进比例α= (T1-T2) /T1, 其中T1为前一阶段调度的总拖期, T2为本阶段调度的总拖期.

表3所示为结合选定的3种规则组合, 以2.3节的数据进行禁忌搜索的统计结果.表中平均总拖期为各算例中订单总拖期的平均值.

表2和3中数据显示:第1阶段的禁忌搜索能够较大幅度地减少订单的总拖期, 降低拖期比, 并减少拖期订单的数量;而第2阶段禁忌搜索的改进幅度较小.这也与本问题中同一订单中的任务需要在时间上集中执行这一分析相吻合.在对调度解的质量要求不高, 或者计算时间有限的情况下, 可以仅进行第1阶段的禁忌搜索.表3中数据显示选定的3种规则组合对该问题的优化效果比较接近, 在实际应用中可从中选择一种规则组合与禁忌搜索配合使用.

本文针对仓储系统的备货作业调度, 以订单总拖期最小化为目标建立了两阶段混合流水调度模型.在问题的各决策点采用了不同的启发式规则, 并通过计算实例选出适用于该问题的规则组合.在此基础上, 设计了两阶段的禁忌搜索算法.该方法充分利用了问题的特性, 有效地缩小了搜索空间, 加快了搜索速度, 可快速计算出优化调度方案.

目前以订单的完成时间为优化指标的调度研究还比较少, 今后可以以此为优化指标, 在仓储系统动态在线调度和备货补货并行作业调度方面展开进一步的研究.