提出并研究两台机器环境下的以带权总完工时间为目标函数的越库排序问题。将两阶段越库作业中的进货车辆与出货车辆看作两台流水作业的机器，所装载的货物为需加工的工件，整个作业过程看作具有前序限制关系的两台机流水作业。首先研究该问题的计算复杂性及其最优解的若干性质；其次提出求解该问题的逆向动态规划算法，该算法的计算复杂性为nm2m；最后，给出了动态规划算法的数值实验。结果表明，该算法至少可以求解25个工件规模的越库配送排序问题。
关键词：越库；物流；配送；排序；动态规划；
随着信息技术的发展及运输系统本身效率的提高，为减少安全库存和缩短提前期，许多企业正在或试图应用一项新的配送技术—cross docking。Cross docking 可译为越库，或直接配送，指在物流的任何中间点(仓库或配送中心)只实现收发货的功能而消除货物存储与订单获取功能[1]，可认为是配送系统中的准时制策略(Just-in-time)。越库配送是将货物在进货口卸下，经过简单分拣等操作后直接装到等候在出货口的车辆上运送给零售商，在不增加库存的同时降低了运输费用和运输时间。其优势在于：1 对较大、较稳定的需求，并不需要每次都采取订购模式来运作，越库配送可使供应链各环节减少库存；2 对稳定而小批量的需求，采用越库技术来代替零担运输（Less-than-truckload）可大大降低运输成本；3节省了昂贵的库存费用；4顺应了商品本身对时间上的要求，例如快递、保鲜食品等。越库技术已成功地应用于沃尔玛 (Wal-Mart)、Home Depot, Costco, Canadian Tire 以及FedEx等著名企业。
目前，国内外针对越库技术的研究尚不多见，且主要集中在越库配送中心的布局、货物整合方面。文献[2]运用数学建模及启发式算法，基于产品的仓库占用空间和停留时间，判断哪些产品更适合采用越库技术；文献[3]则研究随机需求下的直通配送系统，在各需求点的库存监控周期内，设定若干个等时间间隔检测点。从第1个检测点开始检查，测算监控周期剩余时间内越库和不越库的期望费用，比较两者，决定是否采用越库作业，逐次推进，使系统在一定服务水平下费用最低；文献[4]针对美国邮电局邮件优先投递传送系统的卡车运输网络进行了设计，利用整数规划松弛法解决大规模系统的物流配送网络，为解决类似模型提供了依据。
越库排序模型是由F. Chen and C.Y. Lee 在文[5]中提出的。文[6]研究了面向准时制物流的越库排序问题，提出求解该问题的分枝定界算法及启发式算法。本文基于文[5]中的模型继续研究两台机器越库排序问题，该问题的目标函数为带权总完工时间，即使J2中所有工件的带权总完工时间为最小。主要研究求解F2︱CD︱∑wjCj问题的动态规划算法，在研究问题最优解性质的基础上，提出求解F2︱CD︱∑wjCj的动态规划算法并对该算法的计算复杂性进行了分析。给出动态规划算法的数值实验与结果分析。
1. 问题及算法研究
本文所研究问题如下：将越库作业中的进货车辆与出货车辆看作两台机器M1、M2，相应运输的货物为两个任务集，J1={J11,J12,…,J1n}, J2={J21,J22,…,J2m}；其中J1与J2中的工件分别在机器M1、M2上加工。工件集J1中的工件J1i在机器M1上的加工时间记作p1i；工件集J2中的工件J2j在机器M2的加工时间为p2j。对工件集J2中的一个工件J2j，存在工件集J1的一个子集Sj使得J2j必须等待所对应的Sj中所有工件在M1上加工结束后，J2j才能在M2上开始加工。三参数表示法，该问题简记为：F2︱CD︱∑wjCj。易知F2︱CD︱∑wjCj是一个强NP－hard问题。这是因为对于F2︱︱∑wjCj已被证明为强NP－hard问题[7]，而该问题可以看作是F2︱CD︱∑wjCj问题的一种特殊情况，即当前序关系集合S为一单位矩阵时。因此F2︱CD︱∑wjCj为强NP－hard问题。
动态规划算法是运筹学的一个重要分支，它是解决多阶段决策最优化的一种有效方法。其一般求解步骤为：首先将问题的过程划分成恰当的阶段，正确选择状态变量、决策变量及每阶段的允许决策集合，然后正确写出状态转移方程和指标函数，由最初状态开始，由前向后顺推，逐步求得各段的最优决策和相应的最优值，最后得到整个问题的最优解。其最优性原理为[8]：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。动态规划算法在求解大规模排序问题中有非常成功的应用[9][10][11]，鉴于此，针对问题F2︱CD︱∑wjCj，作者采用向后动态规划算法，状态变量为每次加工的工件数量t，决策变量为尚未加工的工件J2q，允许决策集合为尚未安排加工的所有工件集合，指标函数即为带权总完工时间。同时为了提高该问题动态规划算法的效率，在每一步骤中，并不完全考虑所有当前可加工工件的所有前序工件，以此简化算法。为提高算法性能，先给出两个引理。
引理1假设最后完工的k个工件的集合H J2。若S(H)S(J2\H)成立且存在一个最优排序*，使得H最后完工，则存在一个满足上述条件的最优序使得H中的工件按照wj/P2j非增顺序排列（WSPT）。
证明若集合Ht中所有工件的前序集已在M1上加工完毕，则该集合中所有工件在排序时均不需考虑其前序，此种排序可看作为单机排序，而在单机排序中，依据WSPT规则得到的排序可获得最小的加权完工时间和。因此，在这种情况下可直接使用WSPT规则进行排序而无需迭代。证毕。
此引理可以减少整个算法的循环时间、简化运算步骤，尤其在集合J1中工件数量远远小于J2中工件数量的情况下。