本文研究基于在制品水平的有限缓存区越库作业调度问题。在分析问题特点的基础上，提出越库作业在制品定义，对其性质进行分析。其次，提出适应于该类问题求解的禁忌搜索算法。进一步，通过数值实验，对禁忌搜索算法的参数进行优化。并将所得到的较优算法与启发式算法进行比较，从而说明所出禁忌搜索算法的有效性。最后，针对不同问题规模及不同订单规模确定最大在制品库存水平，对缓存区最优容量设置进行数值分析，从而为越库中心决策提供一定的理论依据。
关键词：有限缓存区，越库，死锁，在制品，禁忌搜索算法
0引言
越库作业（cross docking），也称为直接配送，指在物流的任何中间点(仓库或配送中心)只实现收发货功能而消除货物存储与订单获取功能[1]。越库作业被认为是配送系统中的准时制策略(Just-in-time)。其优势在于在不增加库存的同时充分利用运输规模经济降低运输费用和减少运输时间。因此，在物流配送领域得到非常成功的应用，被包括沃尔玛(Wal-Mart)、Home Depot, Costco, Canadian Tire 以及FedEx等著名企业所采用。
目前，针对越库作业的研究并不多，且主要集中在越库配送中心的布局及货物整合方面[2][3][4] 。越库作业调度模型是由F. Chen 与C.Y. Lee [5]提出，具体模型为：给定两台机器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︱Cmax。文中，作者在证明该问题为强NP－难特性的基础上，研究若干可行解的特性并给出求解该类问题的近似算法和分枝定界算法。目前，针对该模型进行的研究有：文[6]研究以最小加权完工时间和为目标的两机器越库流水作业调度问题，并采用模拟退火算法求解该问题。文[7]则研究了面向准时制物流的越库调度问题，提出求解该问题的分枝定界算法及启发式算法。本文作者在文献[8]中提出并研究了无阻塞两机器越库作业调度问题F2︱CD︱∑wjCj，其目标函数为最小化加权完工时间和，并提出计算复杂性为nm2m的动态规划算法。
考虑到实际作业时，受越库中心作业面积限制，暂存货物的存储空间容量不可能为无限大。同时，每种货物进入作业区时均以固定的存储单元包装。当同种货物进入缓存区后，要等到所有需要该货物的车辆全部装完后，装有该货物的存储单元才会被取走，这无形中加大了对缓存区容量的需求。当缓存区容量设置过小时，会导致所有的设备都处于等待状态，系统无法正常运行。缓存区容量过大又会造成严重的空间浪费，空间利用率降低。因此，确定合适的越库区域大小是越库作业能否顺利实施的重要前提条件。
文[9]中作者针对缓存区容量设置问题提出有限缓存区越库作业调度模型：有限缓存区越库作业调度模型F2︱CD，B︱∑wjCj。在证明该问题为强NP－hard问题后，给出求解该问题的启发式算法。
在制品原本是指制造企业生产线上从第一道工序开始到最后一道工序结束这期间所有准备加工、正在加工及已经加工的零部件的总和。本文所提的越库作业在制品库存则是指越库作业中进货、整合、出货等操作过程中所有货物的总和，采用表示当集合J2中任务按照排序在M2上加工时，缓存区内存放任务的最大数量。为了进一步提高越库作业效率，增加收益，必须采取措施降低在制品库存，加速货物流通速度，缩短其在越库中心的逗留时间。
本文将基于[9]提出的启发式算法，进一步研究求解该问题的禁忌搜索算法( Tabu Search)。并基于禁忌搜索算法研究不同问题规模及不同订单规模与最大在制品库存水平之间的关系，对缓存区最优容量设置进行数值分析等。
禁忌搜索算法是局部邻域搜索算法的推广。Glover等人(1986年)首次提出这个概念，进而形成一套完整的算法。该算法能够解决NP-hard问题，它通过禁止向某些邻域移动的策略来跳出局部最优。S.Q.Liu[10]采用禁忌搜索算法求解成组车间作业排序问题，通过实际问题的数值实验表明，该禁忌搜索算法比其它一些求解该问题的算法更加有效且快速。V.Ganapathy[11]研究两机器流水作业问题，其目标是最小化总完工时间，采用禁忌搜索算法和模拟退火算法求解，通过数值实验表明禁忌搜索算法在求解该类问题时比模拟退火算法的性能要好。M. Ben-Daya[12] 采用禁忌搜索算法求解流水作业排序问题，作者提出一种新的邻域生成方法，并通过数值实验表明该算法对于求解流水作业排序问题相比较其它一些已有的算法改进很多，可在更短时间内得到一个比较好的解。上述文献充分说明禁忌搜索算法是求解NP-难调度问题方面重要方法。
本文研究结构如下：第2节，研究基于该问题的禁忌搜索算法各参数的设置及整个算法的设计；第3节，通过数值实验，确定禁忌搜索算法某些参数的最优设置，验证算法有效性，对不同问题规模的在制品库存水平及缓存区容量设置展开研究，提出基于在制品库存水平的缓存区容量设置；第4节，总结与展望。
1 禁忌搜索算法
本文将从问题的固有特性出发，提出适合于所研究问题的有效禁忌搜索算法。并基于禁忌搜索算法的思想，结合所研究问题的特点，在平衡目标函数值（即最小化加权完工时间和）与缓存区在制品库存水平（WIP）的基础上，找到最佳任务加工顺序和最佳缓存区容量。
1.1算法描述
首先给定初始解向量，及初始值为空的禁忌表T，在每次迭代中，应用best-fit搜索策略对的邻域进行搜索，选择一个最好的非禁忌邻域解，同时刷新禁忌表T。在下一次迭代中以解向量作为初始解，搜索过程中，记录当前得到的最好目标函数值、缓存区在制品库存水平（WIP）及相应的解向量。算法如下：
步骤1：初始化。，＝，，；
步骤2：赋值。在的邻域中找到最好的非禁忌邻域解，并修改禁忌表T，赋值，计算最佳适配值与启发式算法最优值的偏离值Dev；对于某些会造成死锁的排列方式，将其开始死锁时的任务及其前面所有任务的组合放入死锁记忆禁忌表中，永久禁忌；
步骤3：如果＜,则赋值，＝，，返回步骤2；
步骤4:如果（）,（），Dev<<>NDev<<>，三个条件中任一个满足，则算法结束，否则返回步骤2。
其中， 为当前最优排序，为当前最优排序对应的最小加权完工时间和，T为禁忌表，为算法最大迭代步数，为最优解无改进最大迭代步数。需要说明的是在寻找最优算法时必须根据缓存区最大容量B及当前缓存区容量B'来判断该排列是否满足缓存区容量限制的条件，若不能满足条件，则将该排列直接剔除即永久禁忌，不再考虑。