李文超，杨宏兵

LI Wen-chao1, YANG Hong-bing2

(1.江苏大学 汽车与交通工程学院，镇江 212013；2.苏州大学 机电工程学院，苏州 215021)

0 引言

车间生产调度优化不仅是制造自动化领域一项重要研究课题，也是现代企业管理一项重要内容。对于很多属于NP难或属于NP完全的调度问题，至今仍未发现求解它们的有效算法。

作为作业调度领域内一个典型模型，Job-shop问题自1976年Job-shop调度问题被证明为NP完全后[1]，关于其解的研究以及相关的延伸问题一直是学术界关注的一个焦点。Job-shop问题早期研究多集中于寻找其最优解的精确算法如分枝定界、隐性枚举等方法[2,3]，这类方法对规模较小问题（如5×20，或10×10等）效果显著，但随着问题规模增加，该类算法难以实现。自上世纪80代后，随着计算机技术发展，研究多转向于以寻找其近优解为目的启发式算法。如文献[4,5]提出构建神经网络方法来求解Job-shop问题。文献[6]通过建立多代理结构体系求Job-shop的解。文献[7]提到利用多点构建思路搜索其解。文献[8]利用Lagrangian松弛神经网络求其解。文献[9]采用禁忌搜索算法和模拟退火方法取得较好效果。这些算法对于规模较大问题能够在规定时间内找到较满意近优解，但也存在一些问题，如有的对参数取值比较敏感，而有的算法要找到理想的解则耗费时间较长。

作为一种启发式随机搜索算法，禁忌（Tabu Search）算法被普遍用于组合优化问题求解。该算法在搜索过程中利用建立的Tabu表，对已经进行的搜索过程做选择和记录，为下一步的搜索方向提供参考。在Job-shop研究中，该方法被不同研究者所使用，取得良好效果。除上述文献[9]外，利用该方法取得显著效果还有文献[10,11]。在本文中，对于Job-shop搜索过程中操作对的选择采取了5种方式，每种方法均有其缺点和优点。这些方式在搜索过程中如找不到可行解，则被暂时置入Tabu表，以其他方式代之，继续搜索过程，直到得到满意解或达到规定时间。

本文组织结构如下：第1节为问题描述，第2节针对Job-shop问题介绍算法方案及总体实现步骤。第3节对所提算法进行数值仿真实验。第5节给出结论及评价。

1 问题描述

Job-shop问题主要是指要处理n个工件在在m台机器上调度问题，即确定各工件在各台机器上处理次序，使得某些性能指标达到最优，通常以任务最大完工周期(makespan)作为指标。各工件在各机器上处理时，须满足如下条件：1）每个工件最多经过m台机器处理，且各工件以不同次序通过各台机器；2）每台机器加工各工件次序不同；3）各个工件在每台机器上加工时间是确定的；4）每个工件通过各台机器的次序是确定不变的；5）每个工件在同一时间只能在一台机器上完成；6）每台机器对各工件只加工一次（即不考虑可重入情况）；7）每台机器在同一时间内只加工一个工件。

由于Job-shop问题复杂性，其求解方法多种多样。文献[12]介绍一种通过有向图逐步去除析取约束方法来获取其可行解。本文在其建立有向图基础上，通过添加约束（即有向弧）方法来求取其可行解。其过程可通过如下实例[12]加以说明。

表1 4×3Job-shop问题实例

表1给出了一个4×3Job-shop问题（记为E1）初始条件，基于该初始条件，可建立其初始有向图模型如图1所示：

图1 E1初始有向图模型

由图1可计算工件j在机器i上操作oij加工指标：

1）最早开工时间seij：图中源点B到该操作所在的节点(i, j)间最大路径的长度

2）最迟完工时间claij：图中源点B到终点T间最大路径长度与该操作所在的节点(i, j)到终点T间最大路径的长度之差加上该操作处理时间pij，即：

在同一台机器i上，工件j可先于工件k加工的先决条件是操作oij的最早完工时间ceij早于操作ojk的最迟开工时间seik，即：

图2 E1添加约束后有向图模型

在上述过程中，可互换操作对选取很重要，如果选取不当，则可能导致得不到可行方案或所获调度方案不理想。本文提出利用Tabu表，在搜索过程中对于不合适选取方法，暂时限定其选取，提高搜索效率。

2 算法实现

2.1 禁忌搜索

作为一种元启发式算法，禁忌搜索（TS）被广泛应用于组合优化问题求解。它基本组成要素主要有：初始解、邻域、动作、唤醒函数、搜索策略、Tabu表、终止条件等。其基本思路是从初始解开始，在初始解形成的领域内采取既定动作进行搜索，找到该邻域内最优解，并以此最优解为新的出发点，按既有搜索策略继续进行搜索。如果在搜索过程中陷入某个邻域内不能发现新的最优解，则改换搜索策略继续搜索，并将原策略放入Tabu表，暂时不用，以避免在搜索过程中陷入循环。在后续搜索过程中如果满足一定条件，则该策略可被唤醒函数唤醒，可继续使用。算法终止与具体条件。

作为一种普适性算法，禁忌算法在解决具体问题应用中若要取得好的效果，则需要结合具体问题进行具体分析，恰当确定算法在所求问题中基本元素和具体参数。

2.2 算法设置

在本文中，对于JS问题禁忌算法的初始解设置为其初始有向图模型。动作为按照既定搜索规则选取可互换操作。邻域为有向图模型存在的互换操作对集合。搜索策略功能是选取合适互换操作对，这是算法关键。本文给出5种选取方法，算法在搜索过程中可根据具体情况灵活采用其中一种方法。对于可互换操作oij与ojk，各方法选取标准如下。

1）最小值方法，选取函数fc1值由下式确定：

2）均值方法，选取函数fc2如下：

3）乘值方法，选取函数值fc3如下：

4）均方值方法，选取函数值fc4如下：

5）均方值方法，选取函数值fc5如下：

若算法在搜索过程中使用某种选取方法fci找不到更好的解，将该函数放入Tabu表，暂停使用。直到Tabu表满，用唤醒函数将其唤醒重新使用。

2.3 算法总体实现

算法总体思路是从初始解开始，计算初始有向图中各工序参数，将存在先后顺序操作间约束加在有向图上，如存在可互换操作，采用2.2中搜索策略选取其中一对，确定先后顺序并将其加在有向图上。对更新后有向图重复上述步骤，直到满足终止条件。具体步骤如下：

步骤1：建立JS问题初始有向图模型G0,并将该模型赋予临时模型GT,即GT=G0;

步骤2：根据有向图GT，若同一机器上任意两操作间均存在次序约束，转步骤7，否则转步骤3。

步骤3：计算图GT中各操作参数如最早（迟）开工和（完工）时间，两操作对间时间间隔。若存在均小于0，转步骤6。否则，转步骤4。

步骤4：对存在先后次序操作对，将其次序约束添加到有向图GT上，形成新有向图GT’。令GT=GT’，判断GT’中是否存在可互换操作对，若有转步骤5；否则，转步骤2。

步骤5：根据2.2中选取方法，选取函数值fci最小操做对，若，则按操作oij先于oik将约束添加到有向图GT上，形成新有向图GC，令GT=GC，转步骤2。

步骤6：判断Tabu表是否饱和，若饱和，弹出其第一个元素，并将步骤5中最近使用选取函数置入Tabu表，令GT=GC，转步骤5。

步骤7：得到可行调度，终止程序。

3 仿真计算

本文从两方面设计了数值仿真实验：首先从求解精度测试所提算法（记为TSCG）性能，然后从求解效率方面对所提算法进行测试。在测试过程中，与文献[10]所提算法i-TSAB进行对比。算法中Tabu表长度为3。算法程序用Matlab7.0编写实现，仿真在PC上进行，参数为CPUCeleron M(1.6GHz), 内存504M。

图3给出算法TSCG与i-TSAB（记为SEJS）在求解精度方面对比。横标Ti表示不同规模算例,分别为(m×n)15×30、15×50、20×30、20×50、20×100；图中横标为各算例标号，纵坐标为算法相对精度，表示如下：

式（8）中H可取TSCG或i-TSAB，LB所求问题下界，所用算例和LB值可参见文献[10]。

图3 算法TSCG与i-TSAB求解精度比较

图4为两种算法求解效率比较。虽然两种算法在求解过程中所耗费时间与问题规模基本上都成线性关系，但由图3可知算法TSCG的坡度明显低于算法i-TSAB的坡度。结合图3可以看出本文所提算法在求解精度方面在问题规模较小时不如i-TSAB，但在问题规模较大时两者相近。同时在求解时间存在明显优势。综合考虑精度和效率，算法TSCG优于算法i-TSAB。

图4 两种算法求解效率比较

4 结束语

本文针对Job-shop问题，在析取有向图模型基础上，提出一种通过逐步添加析取约束的禁忌搜索算法。算法在搜索过程中能够通过不同策略选取可互换操作对。数值仿真结果说明算法TSCG在求解精度面和效率方面存在综合优势，比较适合工程方面应用。

[1]Garey M R,Johnson D S,and Sethi R.The complexity of flow-shop and job-shop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.

[2]M.Florian,P.Trepant,G.McMahon.An implicit enumerationalgorithm for the machine sequencing problem[J].Management Science,1971,17(7):782-792.

[3]H.H.Greenberg.A branch and bound solution to the general scheduling problem[J].Operations Research,1968,16(3):353-361.

[4]张长水,阎平凡.解Job-shop问题的神经网络方法[J].自动化学报,1995,21(6):706-712.

[5]杨圣祥,汪定伟.神经网络和启发式算法混合策略解Jobshop调度问题[J].系统工程学报,1999,14(2):140-145.

[6]张宇,孙宪鹏.基于多代理结构的Job-shop动态优化调度策略研究[J].制造业自动化,2001,23(3):22-25.

[7]J.C.Beck.Solution-guided multi-point constructive search for job shop scheduling[J].Journal of Artificial Intelligence Research,2007,29(1):49-77.

[8]Luh P.B.,Zhao xing,Wang Yajun,etc.Lagrangian relaxation neural networks for Job shop scheduling[J].IEEETRANSA CTION Son Robotics and Automation,2000,16(1): 78-88.

[9]C.Y.Zhang,P.Li,Y.Rao,etc.A very fast TS/SA algorithm for the job-shop scheduling problem[J].Computers and Operations Research,2008,25(1):282-294.

[10]E.Nowicki,C.Smutnicki.An advanced tabu search algorithm for the job shop problem[J].Journal of Scheduling,2005,8:145-159.

[11]E.Nowicki,C.Smutnicki.A fast taboo search algorithm for the job shop problem[J].Management Science,1996,42:797-813.

[12]Pinedo M.Scheduling:Theory,algorithm,and system[M].Beijing:China Machine Press,2005.