本文主要研究两台机器环境下的以加权完工时间和为目标函数的越库调度问题。首先针对两机器越库调度问题进行研究与分析，给出该问题最优解的若干性质；其次，基于最优解的性质，提出求解该问题的启发式算法，并在此基础上对所给算法进行改进；最后，通过数值实验与动态规划算法比较，证明所给算法及其改进算法的有效性。

关键词：物流调度启发式算法越库配送

1 引言

越库（Cross docking），也可译为直接配送，指在物流的任何中间点(仓库或配送中心)只实现收发货的功能而消除货物存储与订单获取功能^[1] 。越库作业由来已久，已在一些产业领域开展了几十年，主要是针对易变质或时间敏感性货物，如海产品以及新鲜食品类。然而真正运用在其他行业，还只是近几年发生的。通过越库策略大幅降低库存水平，可以降低库存管理成本、减少货物损失率、丢失率及加快资金周转等。越库作业可认为是配送系统中的准时制策略(Just-in-time)。

目前，针对越库技术的研究主要集中在越库配送中心的布局及货物整合方面：文献[2]运用启发式算法对基于产品在仓库中的占用空间和停留时间，判断哪些产品更适合采用越库技术。文献[3]则通过对一个随机需求的直通配送系统的运行过程中进行研究后，提出将各需求点的库存在监控周期内设定若干个等时间间隔的检测时点，从第一个检测时点开始检查，并测算监控周期剩余时间内转载和不转载的期望总费用；比较二者，决定是否使用越库作业，逐次推进，使系统在一定服务水平下费用最低。文献[4]针对美国邮电局邮件优先投递系统的卡车运输网络进行设计，文中利用整数规划的松弛法来解决大规模系统的物流配送网络，为解决类似模型提供了依据。

越库调度模型是由F. Chen and C.Y. Lee 在文[5]中提出的。该文详细研究了如下问题：给定两台机器M₁、M₂及两个任务集，J₁={J₁₁,J₁₂,…,J_1n},J₂={J₂₁,J₂₂,…,J_2m}；其中J₁与J₂中的任务分别在机器M₁、M₂上加工。任务集J₁中的任务J_1i在机器M₁上的加工时间记作p_1i；任务集J₂中的任务J_2j在机器M₂的加工时间为p_2j。对任务J_2j，存在任务集J₁的一个子集S_j使得J_2j必须等待所对应的S_j中所有任务在M₁上加工结束后，J_2j才能在M₂上开始加工。问题的目标函数为最小化最大完工时间。采用著名的三参数表示法^[6]，该问题被记作F2︱CD︱C_max。在该文中，作者在证明该问题为强NP－难特性的基础上，研究了若干可解特例并给出求解该类问题的近似算法和分支定界算法，具体见文[5]所述。

本文作者在文[7]中基于F. Chen and C.Y. Lee的模型，提出一个新的模型，依据三参数表示法可记为：F2︱CD︱∑w_jC_j，其中，w_j为任务J_2j的权重，C_j为任务J_2j在M₂上的完工时间。其目标函数为最小化加权完工时间和，即极小化J₂中所有任务的加权完工时间和。文中作者在研究了上述问题的特性后，证明该问题为强NP－hard问题，并给出求解该问题的动态规划算法。考虑到动态规划算法只能求解规模为m=30的问题，而多数研究NP－hard问题的学者均采用启发式算法进行求解^{[8][9][10][11]}，因此本文亦试图找到有效求解该问题的启发式算法,以获得大规模问题的求解方法。全文结构如下：

第二节研究该问题解的性质，并在此基础上提出求解F2︱CD︱∑w_jC_j的启发式算法，并基于所提出的算法给出改进算法。第三节通过数值实验验证所给改进算法的有效性，同时，将改进算法与动态规划算法进行数值实验比较，以验证算法的正确性。第四节总结本文的研究结果并对未来的研究方向做了进一步展望。

2 算法

在介绍具体算法之前，首先分析关于该问题解的某些性质。本文所用符号如下：

V₁：已分配在M₁上加工的任务J_1i的集合；

V₂：已分配在M₂上加工的任务J_2j的集合；

：M₂上已安排加工的任务J_2j的集合，为部分任务集合；

S_j'：对应S_j中除去H₁中已加工任务的集合，即：S_j^'＝S_j－S_jÇH₁；