求解作业车间JIT 调度问题的VNS／MP混合算法

杨宏安，齐亮亮，李锦远，王宏浩

（西北工业大学 现代设计与集成制造教育部重点实验室，陕西 西安 710072）

0 引言

在以适时、适量、零库存为特征的准时制（Just in Time，JIT）生产模式下，作业调度通过控制零部件的末道工序，以Pull方式实现上游工序的按需生产［1］。因此，JIT 生产环境下车间调度的实质就是传统的提前／拖期（Earliness／Tardiness，E／T）问题，而且这类E／T 调度模型［1］比较适合于大批量、生产稳定、组织扁平的流水线生产企业。

航空、航天、装备等行业的冷加工车间属于典型的Job shop类型，其零部件生产具有多品种小批量、加工工艺复杂、制造周期长和生产准备工作量大等特征。而基于末道工序准时完工的E／T 调度模型不能保证零部件中间加工过程的均衡性和合理性，还会导致零部件最后两道工序之间产生大量的中间存储成本［1］。因此，对于Job shop这类复杂的作业车间而言，对零部件的关键工序甚至所有中间工序的加工过程和进度进行精细化管控非常必要；另外，对于加工周期较长的大型复杂零部件，只有对其内部中间工序集进行严格的过程管控，才能保证零部件成品最终按期交付。

因此，将零部件的交货期分解至所有中间工序（或关键工序），并对这些工序的E／T 完工施加相应的E／T 惩罚成本，以通过中间工序的按期完工来保证最终零部件的准时交付，从而形成一类作业车间JIT调度问题（Just in Time Job shop Scheduling Problem，JIT-JSP）。传统的E／T 调度模型只要求零部件的末道工序准时完工，而JIT 调度则要求所有工序（或关键工序集）尽可能都在各自的交货期准时完工，因此JIT 调度问题可以视为一类精细化至工序准时交付的E／T 调度问题。

目前，针对非正规指标的Job shop调度问题，E／T调度方面的研究文献相对较多［1-3］，而有关JIT-JSP的研究甚少。Baptiste等［1］于2008年在国际上首次提出了JIT-JSP 模型，采用拉格朗日松弛方法获得了调度解的下界，并通过局域搜索方法得到调度解的上界，72个Benchmark算例的仿真结果表明，大部分算例上、下届之间的偏差仍然较大；Monette 等［4］在约束规划（Constraint Programming，CP）方法框架内，通过嵌入过滤算法和局域搜索方法来改进JIT-JSP调度解；Santos等［5］采用进化算法、局域搜索和数学规划（Evolutionary Alorithms，Local Search，Mathematical Programming，EA／LS／MP）混合方法求解JIT-JSP，即运用EA 和LS方法优化各机器上的工序加工序列，然后通过MP方法确定序列中各工序的开工时间，实验结果表明该混合方法在求解较大规模的JIT-JSP算例方面具有一定的优势；Yang等［6］采用与文献［5］类似的求解思路，运用遗传算法和MP 混合方法求解JIT-JSP；李海宁［7］采用禁忌搜索（Tabu Search，TS）和MP混合策略求解JIT-JSP，但该方法在调度规模较大时其优化性能将出现劣化现象。

文献［5-6］均采用两阶段的求解策略，首先采用近似算法得到机器上的工序加工序列，然后通过MP方法进行工序开工时间优化设置。在文献［5-6］的基础上，本文提出采用变邻域搜索（Variable Neighborhood Search，VNS）和MP 的混合方法（VNS／MP）来求解JIT-JSP，在VNS的每次迭代过程中，通过调用嵌入VNS内的MP 方法对VNS得到的机器加工序列进行工序开工时间优化计算。VNS／MP方法与文献［5-6］的本质区别是：前者需要多次调用MP方法，后者只需调用一次MP 方法来进行工序开工时间的优化计算。

1 JIT-JSP模型

JIT-JSP可以描述为：n个零件J=｛J1，J2，…，Jn｝在m 台机器M=｛M1，M2，…，Mm｝上加工，每个零件Ji包括ni道工序，调度任务是在满足基本工艺路线和机器能力约束的条件下，使所有工序的E／T 惩罚的总成本最小。

对于零件Ji的任一工序，其相关JIT 调度参数为：工序加工时间、工序交货期、开工时间、完工时间、承制机器、工序提前完工的单位时间惩罚系数、工序拖期完工的单位时间惩罚系数。则JIT-JSP调度模型为：

其中：式（1）为JIT 调度目标函数，即要求所有工序的E／T惩罚的总成本最小；式（2）为工序的提前完工量；式（3）为工序的拖期完工量；式（4）为工艺路线约束，即同一零件Ji内相邻工序之间的时序关系约束；式（5）为机器析取（能力）约束，即同一机器上工序队列的时序关系约束。

2 VNS／MP混合调度算法

针对JIT-JSP 这类复杂的非正规指标调度问题，其调度最优解必然需要合理地插入机器空闲时间，而插入机器空闲时间的前提则是需要已知各机器上的工序加工序列。因此，采用两阶段的JITJSP求解策略：首先优化机器加工序列，然后合理插入机器空闲时间（即工序开工时间优化）。

VNS是Hansen 等［8］提出的一种元启发近似算法，它通过在不同的邻域结构内跳转搜索来避免传统局域搜索方法易陷入局部最优的缺陷，因此VNS在邻域搜索方面的优势非常适合求解机器上的工序加工序列；而当机器加工序列确定后，即松弛了JIT-JSP模型中最难满足的机器析取约束，可以为MP这类数学方法精确计算工序开工时间提供可能。为此，设计了如图1 所示的VNS／MP 混合算法框架。

VNS／MP混合算法是在VNS的搜索框架内嵌入了MP方法，在每次迭代过程中，通过VNS的扰动（shaking）和局域搜索获得新邻居（机器加工序列），然后调用MP方法优化当前序列内各工序的开工时间取值。为了减少计算时间，邻域结构数量设置为。两类邻域结构Swap（交换）和Insertion（插入）的详细设计参见3.2节。

3 机器加工序列优化方法VNS

对于非正规指标的调度问题，单一邻域结构难以适应JIT 调度中提前和拖期的不同需求，因此需要寻找一种适用于E／T 特征的多邻域结构。VNS在迭代搜索过程中通过改变邻域结构来拓展搜索范围，因此选择VNS方法求解JIT 调度中的机器加工序列是合理的。

将MP方法嵌入VNS迭代搜索框架内有助于提高JIT 调度解的质量，但由此带来了计算时间成本较大的弊端。优良的初始解和邻域结构可以提高VNS的搜索效率，减少频繁调用MP方法导致混合算法计算成本较高的问题；另外，局域搜索是VNS算法中的另一关键操作。因此，以下从VNS 的初始解、邻域结构和局域搜索三方面进行重点说明。

3.1 基于EDD 和ALL-JIT 排序规则的初始解产生方法

初始解的质量直接影响VNS这类邻域搜索算法的搜索效率，因此本文采用文献［5］提出的初始解产生方法，即分别采用最早交货期（Earliest Due Date，EDD）规则和ALL-JIT 排序规则［10］产生两类机器加工序列，再通过调用MP 方法获得对应的两类JIT 调度解，最后依据调度目标值进行择优，以获得初始JIT 调度解。

3.2 Swap和Insertion邻域结构设计

采用Swap 和Insertion 两类移动方式来定义VNS的邻域结构。根据JIT 调度问题的特点，将Swap和Insertion的移动原则设定为：使各工序的完工时间尽可能向各自的交货期靠拢，以减少提前或拖期惩罚成本。

（1）相关定义和移动条件设定

定义1 紧邻工序对。指同一台机器上两道紧邻加工的工序，且两道工序之间不存在机器空闲时间。这两道工序称为紧邻机器前续工序和紧邻机器后续工序。

定义2 块。指同一台机器上依次紧邻加工的工序集，且各工序之间不存在机器空闲时间。其中：块内的首道工序称为块首，末道工序称为块尾。

Swap和Insertion 两类操作的移动条件设定如下：

1）提前工序移动条件 若工序u 提前完工，且u存在紧邻机器的后续工序，则选择u 作为移动对象。

2）拖期工序移动条件 若工序u 拖期完工，且u存在紧邻机器的前续工序，则选择u 作为移动对象。

（2）变量说明

对于任一工序u，根据u 所属零件的工艺路线，用JP［u］表示工序u 的零件前续工序，JS［u］表示工序u的零件后续工序；依据u所需的加工机器，用MP［u］表示工序u的机器前续工序，MS［u］表示工序u的机器后续工序。这里的机器前续或后续工序表示了某台机器上的相邻加工工序，而相邻加工工序之间则容许存在机器空闲时间，这与上述紧邻工序对不同。

相关符号说明：设工序u的完工时间为cu、交货期为du，则u对应的零件后续工序JS［u］的开工时间为stJS［u］、完工时间为cJS［u］、交货期为dJS［u］；而u对应的零件前续工序JP［u］的开工时间为stJP［u］、完工时间为cJP［u］、交货期为dJP［u］。

（3）Swap邻域结构设计

Swap移动操作方法为在紧邻工序对内随机选取满足上述移动条件的某一工序u，若u 提前完工，则将u与其紧邻机器的后续工序进行位置交换；若u为拖期完工，则将u 与其紧邻机器的前续工序进行位置交换。

文献［11］指出，交换机器上两道相邻工序（工序之间可以存在空闲时间）可能导致死锁，而将交换操作限定在紧邻工序对上，产生的新邻居一定是可行的。另外，将交换操作限定在紧邻工序对，有助于大大减小邻域搜索空间，而且这种交换方式可以避免交换（拖期完工工序，提前完工工序）这样的紧邻工序对，因为交换这类工序对将导致两道工序的完工时间更加背离各自的交货期。

在VNS的每次迭代过程中，通过MP 这类精确数学方法得到的调度解是当前机器加工序列条件下的最优解，因此各工序的完工时间已经尽可能靠近各自的交货期。在此条件下，提前（或拖期）工序和其对应的零件后续（或前续）工序之间满足以下两个性质：

性质1 若工序u 提前完工，且不存在紧邻机器后续工序，则u 对应的零件后续工序JS［u］必然提前完工。

证明 若工序u 提前完工，且没有紧邻机器后续工序，则cu＜du，且cu=stJS［u］，cJS［u］=stJS［u］+pJS［u］=cu+pJS［u］＜du+pJS［u］。因为u 和JS［u］的交货期 满 足du+pJS［u］≤dJS［u］，所 以cJS［u］≤dJS［u］，即工序JS［u］提前完工，证毕。

性质2 如果工序u 拖期完工，且不存在紧邻机器前续工序，则u对应的零件前续工序JP［u］必然拖期完工。

证明 若工序u 拖期完工，且不存在紧邻机器前续工序，则（stu+pu=cu）＞du，且stu=cJP［u］，由此得到stu＞du-pu；因为u 和JP［u］的交货期满足dJP［u］+pu≤du，所以stu＞du-pu≥dJP［u］，又因为stu=cJP［u］，故cJP［u］≥dJP［u］，即工序JP［u］拖期 完工，证毕。

根据上述两个性质有助于快速定位满足上述移动条件的提前或拖期工序。即当选择的工序u提前完工且没有紧邻机器后续工序时，依据性质1可知u 的零件后续工序也是提前完工，因此依次追溯u的零件后续工序，直到某一工序满足提前工序移动条件，则将该工序作为移动对象，通过Swap移动操作来获得新邻居；如果u 拖期完工且没有紧邻机器的前续工序，依据性质2可知u 的零件前续工序也是拖期完工，则依次追溯u的零件前续工序，直至某道工序满足拖期工序的移动条件后，方可进行Swap移动操作。

以图2为例，工序u提前完工，且不存在紧邻机器后续工序（因机器M1上的工序v 和u 之间存在空闲时间）。依据性质1追溯到JS［u］，而JS［u］满足上述提前工序的移动条件，则对紧邻工序对（JS［u］，JP［v］）执行Swap 移动操作。在交换之后获得的新机器加工序列中，各工序都在靠近各自交货时间点完工，因此新序列优于交换之前的机器加工序列。

（4）Insertion邻域结构设计

Insertion移动操作借鉴了Balas等［12］提出的邻域结构，并且满足他们给出的邻域中仅包含可行解的条件。具体的移动操作方法如下：

1）提前工序的Insertion移动方法 设选中的工序为u，且u 提前完工，w 为块尾工序：当w 的开工时间stw≤stJS［u］时，将u移到w 右侧，产生一个新邻居；否则在块内u的右侧随机选择某一工序x，当x 的开工时间stx≤stJS［u］时，将u 移到x 的右侧，产生一个新邻居（如图3）。

2）拖期工序的Insertion移动方法 设选中的工序为u，且u拖期完工，v为块首工序：若v的完工时间大于u 的零件前续工序的完工时间，即cv≥cJP［u］，则将u 移至v 左侧以产生新邻居；否则，在块内u的左侧随机选择某一工序x，当x 的完工时间cx≥cJP［u］时，将u 移至x 左侧，产生新邻居（如图4）。

块是工序集竞争同一机器资源的结果，也是工序向交货期靠拢的障碍，因此优先将满足上述移动条件的工序移至块首或块尾，有助于解除块对工序集的束缚；另外，利用块与块之间的间隙来容纳待移动工序，有助于减少Insertion移动操作对其他工序开工时间的影响，有可能改善调度解的质量。

3.3 局域搜索

作为VNS 算法的关键操作之一，局域搜索是在当前解的邻域内搜索局域最优解。为了增加搜索空间的多样性（diversification），设计了一种基于阈值接受的LS算法；为了避免Swap移动操作严重劣化调度解，提出一种基于工序重叠度的Swap邻域过滤机制。

（1）基于阈值接受的局域搜索方法

与基于爬山法的传统LS 方法不同，基于阈值接受的LS算法首先设定一个调度目标值的容许偏差（即阈值dr），如果局域搜索得到的调度解x″和当前解x′的调度目标偏差小于阈值，即f（x″）-f（x′）≤dr，则接受x″。在文献［13］提出的LS方法的基础上，引入MP方法来精确计算机器加工序列上各工序的开工时间，即利用MP 方法计算新邻居Nu（x′）对应的JIT 调度解x″。LS方法如图5所示。

（2）基于工序重叠度的Swap 邻域结构过滤机制

Swap邻域结构是交换同一台机器上的紧邻工序对，而这种交换操作有可能导致调度解产生劣化现象。因此，在LS方法的Swap移动操作中添加了一种基于工序重叠度的过滤机制。

假设紧邻工序对（u，v）满足移动条件。在图6a中，工序v 的零件前续工序JP［v］的加工时间和工序u的加工时间有部分重叠，且u 的零件后续工序JS［u］的加工时段与v 的加工时段也有重叠。如果交换（u，v），则u 和JS［u］的完工时间更加延迟，因此在Swap移动操作时，这类情况应该事先避免。在图6b中，虽然紧邻工序对（u，v）进行Swap操作前也有部分的加工时段重叠，但可以利用块间的空隙减小Swap操作的影响，因此这种条件下的Swap操作有助于改进调度解。

因此，工序对（u，v）重叠度的近似计算方法为

若将工序重叠度的阈值设定为Overlapmax，则对于某一紧邻工序对（u，v），只有当Overlap（u，v）≤Overlapmax时，才容许（u，v）进行Swap 移动操作。

4 工序开工时间优化方法——数学规划方法

在VNS算法中，共有以下3类操作产生各机器上的加工序列：

（1）VNS的初始化阶段 通过EDD 或ALLJIT 排序规则获得初始的机器加工序列。

（2）VNS 的shaking阶段通过Swap 或Insertion移动操作获得新的机器加工序列。

（3）VNS的局域搜索内部迭代过程 通过Insertion或Swap移动操作获得新邻居。

当VNS通过上述任一操作获得机器加工序列确定后，即松弛了JIT-JSP 模型中最难满足的机器能力约束，将原模型中的式（5）松弛为如下形式：

因此，在VNS／MP混合算法中，首先通过VNS方法确定出机器加工序列，然后调用MP 方法来优化各工序的开工时间取值。用式（6）替换JIT-JSP模型中的式（5），其他约束条件和目标函数保持不变，由此得到已松弛机器能力约束的MP 的JIT 调度模型；进而利用成熟的数学规划软件工具对MP调度模型进行精确求解，以获得当前机器加工序列内各工序的开工时间优化取值。

5 仿真实验及分析

5.1 JIT调度算例及实验环境

采用文献［1］设计的72 个JIT 调度的Benchmark 算例，每个算例用I-n-m-DD-W-ID 表示，其中：

n∈｛10，15，20｝为零件数量；m∈｛2，5，10｝为机器数量。

DD∈｛tight，loose｝表示同一零件内两道相邻工序交货期之间的松弛度。当时为tight时为loose（r为0～10之间的随机整数）。

W ∈｛equal，tard｝表示提前和拖期惩罚系数之间的关系，当二者均在［0.1，1］区间随机产生时，W=equal；当提前惩罚系数在［0.1，0.3］区间随机产生、拖期惩罚系数在［0.1，1］内随机产生时，W=tard。

ID∈｛1，2｝作为一个标识符。根据上述参数设定，共有36种参数组合，每种参数组合产生两个算例，分别标记为“1”和“2”，因此共有72个测试算例。

VNS／MP混合算法的参数设定为：VNS 的最大迭代次数N=100；LS算法中的qmax=50、阈值dr、工序重叠度阈值Overlapmax=0.5；VNS算法采用C++编程实现，MP 调度模型采用FICOTMXpress Optimizer数学规划软件进行求解。

5.2 实验结果及分析

选择文献［1，4-5，7］提出的JIT 调度算法与本文的VNS／MP算法进行比较，实验结果如表1～表4所示。在4个实验结果表中：

（1）LB（lower bounds）和UB（upper bounds）分别是文献［1］给出的JIT 调度解的下界值和上界值。其中，选择文献［1］给出的拉格朗日机器约束松弛下界值（LBR）和拉格朗日工艺顺序约束松弛下界值（LBP）的最大值作为JIT 调度解的下界值LB。

（2）文献［4］提出4种CP求解方法，本文选择4种方法中的最优JIT 调度结果参与比较。

（3）EA／LS／MP算法是文献［5］提出的一种JIT混合调度算法。

（4）TS／MP算法是文献［7］提出的一种JIT 混合调度算法。

（5）VNS／MP算法是对每一算例进行5次实验，并取其中的最好结果参与比较。

表1 零件数量为10的JIT调度算例实验结果

续表1

表2 零件数量为15的JIT调度算例实验结果

表3 零件数量为20的JIT调度算例实验结果

续表3

表4 72个JIT调度算例仿真结果统计表

表中每一行加粗数字表示五种方法（UB，CP，EA／LS／MP，TS／MP 和VNS／MP）相比较得到的JIT 调度目标值的最好值；另外，文献［7］仅给出了零件数量为10和15的实验结果，因此表3中TS／MP对应的列表示为“-”。

从获得的72个标准JIT 调度算例的已知最好解的数量分析如下：VNS／MP 算法远优于UB、CP方法，也优于EA／LS／MP 方法；与文献［7］给出的前48 个算例实验结果比较，VNS／MP 算法优于TS／MP方法。VNS／MP 算法在调度规模（n=10）较小时优势较为明显，在中规模（n=15）时与EA／LS／MP性能相当，在较大规模（n=20）时稍劣于EA／LS／MP方法。以下对EA／LS／MP和VNS／MP两类方法进行深入分析。

文献［5］提出的EA／LS／MP 算法采用两阶段调度策略，即在确定出机器加工序列后再优化工序开工时间。首先通过EA 这类群优化方法获得一个近优解，然后利用LS方法搜索得到更优的机器加工序列，最后调用MP 方法确定机器加工序列内各工序的开工时间，从而最终获得JIT 调度解。因此，三者方法的优势互补所形成的EA／LS／MP算法在JIT 调度解的优化性能方面具有一定优势；随着调度规模的增加，工序间的析取约束更为复杂，增加了各工序交货期的紧迫程度，工序交货期越紧迫，越有可能导致大部分工序出现拖期，而EA／LS／MP 在交货期紧迫的工况下的优化效果相对较好［5］。因此，EA／LS／MP算法在较大规模（n=20）时的优化性能较好。

VNS／MP算法在所有72 个算例中取得了35个算例的已知最好解，并且更新了其中25个算例的已知最好解。VNS／MP算法的优化性能主要源于：VNS中的两类Swap和Insertion邻域结构引导各工序向各自的交货期移动，由此获得了一个较好的机器加工序列；再通过MP 方法对机器加工序列上的各工序开工时间进行精确计算，从而获得了较好的JIT 调度结果。另外，VNS中的两类邻域结构都是通过移动紧邻工序对定义的，当调度算例的工序交货期较为紧迫时，同一台机器上的工序大都紧邻加工，使得满足移动条件的紧邻工序对较多，由此导致邻域搜索空间过大，影响了VNS的搜索效率，这也是VNS／MP 算法在较大规模（n=20）时表现稍差的原因之一；而当调度问题规模较小或交货期较为宽松时，机器加工序列中的紧邻工序对数量相对较少，邻域搜索空间相对较小，使得VNS的搜索效率较高。

6 结束语

本文针对JIT-JSP这类复杂的非正规指标调度问题，提出一种VNS／MP 混合调度算法，在VNS的迭代过程中，通过在Swap和Insertion两类邻域结构内进行跳转搜索，获得较优的机器加工序列，从而松弛了JIT-JSP调度模型中最难满足的机器析取约束；针对既定的机器加工序列，利用MP这类数学方法进行工序开工时间、机器空闲时间等的精确计算，从而获得一个较优的JIT 调度解。

邻域结构和局域搜索是VNS算法的两个关键环节。本文针对JIT 调度问题的特点，以引导工序向各自交货期移动为邻域设计原则，提出以紧邻工序对为移动对象的Swap 和Insertion 两类邻域结构，利用工序块之间的间隙优化机器上的工序加工序列；LS方法采用基于调度目标值容许偏差的阈值接受机制，增加了搜索空间的多样性。

本文采用72个JIT 调度的benchmark算例进行了测试验证，实验结果表明，VNS／MP 混合算法在JIT 调度解的优化性能方面具有一定的优势。本文研究方法对于项目JIT 调度、物料JIT 供应和离散车间精细化过程管控等具有一定的应用价值。另外，领域结构是决定VNS 算法搜索效率的关键因素，因此下一步的研究工作将针对静态JIT 调度问题，构造更高效的领域结构，以有效缩减VNS／MP的计算时间。

［1］BAPTISTE P，FLAMINI M，SOURD F.Lagrangian bounds for just-in-time job-shop scheduling［J］.Computers &Operations Research，2008，35（3）：906-915.

［2］LI Junfang，LI Tieke，WANG Weiling，Hybrid constraint satisfaction algorithm for solving earliness／tardiness Job Shop scheduling problem［J］.Computer Engineering and Applications，2010，46（16）：12-15（in Chinese）.［李俊芳，李铁克，王伟玲.约束满足混合算法求解提前／拖期Job Shop 调度问题［J］.计算机工程与应用，2010，46（16）：12-15.］

［3］LI J Q，PAN Q K，XIE S X.A hybrid pareto-based tabu search for multi-objective flexible job shop scheduling problem with E／T penalty［J］.Lecture Notes in Computer Science，2010，6145：620-627.

［4］MONETTE J N，DEVILL Y，HENTENRYCK P.Just-intime scheduling with constraint programming［C］／／Proceedings of the 19th International Conference on Automated Planning and Scheduling.Palo Alto，Cal.，USA：AAAI，2009：241-248.

［5］SANTOS A，ARAUJO R，ARROYO J.A combination of evolutionary algorithm，mathematical programming，and a new local search procedure for the just-in-time job-shop scheduling problem ［J］.Lecture Notes in Computer Science，2010，6073：10-24.

［6］YANG H，LI J，QI L.An improved genetic algorithm for just-in-time job-shop scheduling problem ［J］.Advanced Materials Research，2012，472-475：2462-2467.

［7］LI Haining，SUN Shudong，YANG Hong'an，Taboo search and mathematical programming for just-in-time job-shop［J］.Computer Integrated Manufacturing Systems，2012，18（6）：1176-1181（in Chinese）.［李海宁，孙树栋，杨宏安.TS／MP混合算法求解作业车间JIT 调度问题［J］.计算机集成制造系统，2012，18（6）：1176-1181.］

［8］HANSEN P，MLADENOVIC N.Variable neighborhood search：Principles and applications［J］.European Journal of Operational Research，2001，130（3）：449-467.

［9］LIAO C J，CHENG C C.A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date［J］.Computers &Industrial Engineering，2007，52（4）：404-413.

［10］CHENG T，JIANG J.Job shop scheduling for missed duedate performance［J］.Computers &Industrial Engineering，1998，34（2）：297-307.

［11］MUROVEC B，SUHEL P.A repairing technique for the local search of the job-shop problem ［J］.European Journal of Operational Research，2004，153（1）：220-238.

［12］BALAS E，VAZACOPOULOS A.Guided local search with shifting bottleneck for job shop scheduling［J］.Management Science，1998，44（2）：262-275.

［13］ZANDIEH M，ADIBI M.Dynamic job shop scheduling using variable neighbourhood search［J］.International Journal of Production Research，2010，48（8）：2449-2458.