楊宏安，齊亮亮，李錦遠(yuǎn)，王宏浩

（西北工業(yè)大學(xué) 現(xiàn)代設(shè)計(jì)與集成制造教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710072）

0 引言

在以適時(shí)、適量、零庫存為特征的準(zhǔn)時(shí)制（Just in Time，JIT）生產(chǎn)模式下，作業(yè)調(diào)度通過控制零部件的末道工序，以Pull方式實(shí)現(xiàn)上游工序的按需生產(chǎn)［1］。因此，JIT 生產(chǎn)環(huán)境下車間調(diào)度的實(shí)質(zhì)就是傳統(tǒng)的提前／拖期（Earliness／Tardiness，E／T）問題，而且這類E／T 調(diào)度模型［1］比較適合于大批量、生產(chǎn)穩(wěn)定、組織扁平的流水線生產(chǎn)企業(yè)。

航空、航天、裝備等行業(yè)的冷加工車間屬于典型的Job shop類型，其零部件生產(chǎn)具有多品種小批量、加工工藝復(fù)雜、制造周期長和生產(chǎn)準(zhǔn)備工作量大等特征。而基于末道工序準(zhǔn)時(shí)完工的E／T 調(diào)度模型不能保證零部件中間加工過程的均衡性和合理性，還會導(dǎo)致零部件最后兩道工序之間產(chǎn)生大量的中間存儲成本［1］。因此，對于Job shop這類復(fù)雜的作業(yè)車間而言，對零部件的關(guān)鍵工序甚至所有中間工序的加工過程和進(jìn)度進(jìn)行精細(xì)化管控非常必要；另外，對于加工周期較長的大型復(fù)雜零部件，只有對其內(nèi)部中間工序集進(jìn)行嚴(yán)格的過程管控，才能保證零部件成品最終按期交付。

因此，將零部件的交貨期分解至所有中間工序（或關(guān)鍵工序），并對這些工序的E／T 完工施加相應(yīng)的E／T 懲罰成本，以通過中間工序的按期完工來保證最終零部件的準(zhǔn)時(shí)交付，從而形成一類作業(yè)車間JIT調(diào)度問題（Just in Time Job shop Scheduling Problem，JIT-JSP）。傳統(tǒng)的E／T 調(diào)度模型只要求零部件的末道工序準(zhǔn)時(shí)完工，而JIT 調(diào)度則要求所有工序（或關(guān)鍵工序集）盡可能都在各自的交貨期準(zhǔn)時(shí)完工，因此JIT 調(diào)度問題可以視為一類精細(xì)化至工序準(zhǔn)時(shí)交付的E／T 調(diào)度問題。

目前，針對非正規(guī)指標(biāo)的Job shop調(diào)度問題，E／T調(diào)度方面的研究文獻(xiàn)相對較多［1-3］，而有關(guān)JIT-JSP的研究甚少。Baptiste等［1］于2008年在國際上首次提出了JIT-JSP 模型，采用拉格朗日松弛方法獲得了調(diào)度解的下界，并通過局域搜索方法得到調(diào)度解的上界，72個(gè)Benchmark算例的仿真結(jié)果表明，大部分算例上、下屆之間的偏差仍然較大；Monette 等［4］在約束規(guī)劃（Constraint Programming，CP）方法框架內(nèi)，通過嵌入過濾算法和局域搜索方法來改進(jìn)JIT-JSP調(diào)度解；Santos等［5］采用進(jìn)化算法、局域搜索和數(shù)學(xué)規(guī)劃（Evolutionary Alorithms，Local Search，Mathematical Programming，EA／LS／MP）混合方法求解JIT-JSP，即運(yùn)用EA 和LS方法優(yōu)化各機(jī)器上的工序加工序列，然后通過MP方法確定序列中各工序的開工時(shí)間，實(shí)驗(yàn)結(jié)果表明該混合方法在求解較大規(guī)模的JIT-JSP算例方面具有一定的優(yōu)勢；Yang等［6］采用與文獻(xiàn)［5］類似的求解思路，運(yùn)用遺傳算法和MP 混合方法求解JIT-JSP；李海寧［7］采用禁忌搜索（Tabu Search，TS）和MP混合策略求解JIT-JSP，但該方法在調(diào)度規(guī)模較大時(shí)其優(yōu)化性能將出現(xiàn)劣化現(xiàn)象。

文獻(xiàn)［5-6］均采用兩階段的求解策略，首先采用近似算法得到機(jī)器上的工序加工序列，然后通過MP方法進(jìn)行工序開工時(shí)間優(yōu)化設(shè)置。在文獻(xiàn)［5-6］的基礎(chǔ)上，本文提出采用變鄰域搜索（Variable Neighborhood Search，VNS）和MP 的混合方法（VNS／MP）來求解JIT-JSP，在VNS的每次迭代過程中，通過調(diào)用嵌入VNS內(nèi)的MP 方法對VNS得到的機(jī)器加工序列進(jìn)行工序開工時(shí)間優(yōu)化計(jì)算。VNS／MP方法與文獻(xiàn)［5-6］的本質(zhì)區(qū)別是：前者需要多次調(diào)用MP方法，后者只需調(diào)用一次MP 方法來進(jìn)行工序開工時(shí)間的優(yōu)化計(jì)算。

1 JIT-JSP模型

JIT-JSP可以描述為：n個(gè)零件J=｛J1，J2，…，Jn｝在m 臺機(jī)器M=｛M1，M2，…，Mm｝上加工，每個(gè)零件Ji包括ni道工序，調(diào)度任務(wù)是在滿足基本工藝路線和機(jī)器能力約束的條件下，使所有工序的E／T 懲罰的總成本最小。

對于零件Ji的任一工序，其相關(guān)JIT 調(diào)度參數(shù)為：工序加工時(shí)間、工序交貨期、開工時(shí)間、完工時(shí)間、承制機(jī)器、工序提前完工的單位時(shí)間懲罰系數(shù)、工序拖期完工的單位時(shí)間懲罰系數(shù)。則JIT-JSP調(diào)度模型為：

其中：式（1）為JIT 調(diào)度目標(biāo)函數(shù)，即要求所有工序的E／T懲罰的總成本最?。皇剑?）為工序的提前完工量；式（3）為工序的拖期完工量；式（4）為工藝路線約束，即同一零件Ji內(nèi)相鄰工序之間的時(shí)序關(guān)系約束；式（5）為機(jī)器析取（能力）約束，即同一機(jī)器上工序隊(duì)列的時(shí)序關(guān)系約束。

2 VNS／MP混合調(diào)度算法

針對JIT-JSP 這類復(fù)雜的非正規(guī)指標(biāo)調(diào)度問題，其調(diào)度最優(yōu)解必然需要合理地插入機(jī)器空閑時(shí)間，而插入機(jī)器空閑時(shí)間的前提則是需要已知各機(jī)器上的工序加工序列。因此，采用兩階段的JITJSP求解策略：首先優(yōu)化機(jī)器加工序列，然后合理插入機(jī)器空閑時(shí)間（即工序開工時(shí)間優(yōu)化）。

VNS是Hansen 等［8］提出的一種元啟發(fā)近似算法，它通過在不同的鄰域結(jié)構(gòu)內(nèi)跳轉(zhuǎn)搜索來避免傳統(tǒng)局域搜索方法易陷入局部最優(yōu)的缺陷，因此VNS在鄰域搜索方面的優(yōu)勢非常適合求解機(jī)器上的工序加工序列；而當(dāng)機(jī)器加工序列確定后，即松弛了JIT-JSP模型中最難滿足的機(jī)器析取約束，可以為MP這類數(shù)學(xué)方法精確計(jì)算工序開工時(shí)間提供可能。為此，設(shè)計(jì)了如圖1 所示的VNS／MP 混合算法框架。

VNS／MP混合算法是在VNS的搜索框架內(nèi)嵌入了MP方法，在每次迭代過程中，通過VNS的擾動（shaking）和局域搜索獲得新鄰居（機(jī)器加工序列），然后調(diào)用MP方法優(yōu)化當(dāng)前序列內(nèi)各工序的開工時(shí)間取值。為了減少計(jì)算時(shí)間，鄰域結(jié)構(gòu)數(shù)量設(shè)置為。兩類鄰域結(jié)構(gòu)Swap（交換）和Insertion（插入）的詳細(xì)設(shè)計(jì)參見3.2節(jié)。

3 機(jī)器加工序列優(yōu)化方法VNS

對于非正規(guī)指標(biāo)的調(diào)度問題，單一鄰域結(jié)構(gòu)難以適應(yīng)JIT 調(diào)度中提前和拖期的不同需求，因此需要尋找一種適用于E／T 特征的多鄰域結(jié)構(gòu)。VNS在迭代搜索過程中通過改變鄰域結(jié)構(gòu)來拓展搜索范圍，因此選擇VNS方法求解JIT 調(diào)度中的機(jī)器加工序列是合理的。

將MP方法嵌入VNS迭代搜索框架內(nèi)有助于提高JIT 調(diào)度解的質(zhì)量，但由此帶來了計(jì)算時(shí)間成本較大的弊端。優(yōu)良的初始解和鄰域結(jié)構(gòu)可以提高VNS的搜索效率，減少頻繁調(diào)用MP方法導(dǎo)致混合算法計(jì)算成本較高的問題；另外，局域搜索是VNS算法中的另一關(guān)鍵操作。因此，以下從VNS 的初始解、鄰域結(jié)構(gòu)和局域搜索三方面進(jìn)行重點(diǎn)說明。

3.1 基于EDD 和ALL-JIT 排序規(guī)則的初始解產(chǎn)生方法

初始解的質(zhì)量直接影響VNS這類鄰域搜索算法的搜索效率，因此本文采用文獻(xiàn)［5］提出的初始解產(chǎn)生方法，即分別采用最早交貨期（Earliest Due Date，EDD）規(guī)則和ALL-JIT 排序規(guī)則［10］產(chǎn)生兩類機(jī)器加工序列，再通過調(diào)用MP 方法獲得對應(yīng)的兩類JIT 調(diào)度解，最后依據(jù)調(diào)度目標(biāo)值進(jìn)行擇優(yōu)，以獲得初始JIT 調(diào)度解。

3.2 Swap和Insertion鄰域結(jié)構(gòu)設(shè)計(jì)

采用Swap 和Insertion 兩類移動方式來定義VNS的鄰域結(jié)構(gòu)。根據(jù)JIT 調(diào)度問題的特點(diǎn)，將Swap和Insertion的移動原則設(shè)定為：使各工序的完工時(shí)間盡可能向各自的交貨期靠攏，以減少提前或拖期懲罰成本。

（1）相關(guān)定義和移動條件設(shè)定

定義1 緊鄰工序?qū)ΑＶ竿慌_機(jī)器上兩道緊鄰加工的工序，且兩道工序之間不存在機(jī)器空閑時(shí)間。這兩道工序稱為緊鄰機(jī)器前續(xù)工序和緊鄰機(jī)器后續(xù)工序。

定義2 塊。指同一臺機(jī)器上依次緊鄰加工的工序集，且各工序之間不存在機(jī)器空閑時(shí)間。其中：塊內(nèi)的首道工序稱為塊首，末道工序稱為塊尾。

Swap和Insertion 兩類操作的移動條件設(shè)定如下：

1）提前工序移動條件 若工序u 提前完工，且u存在緊鄰機(jī)器的后續(xù)工序，則選擇u 作為移動對象。

2）拖期工序移動條件 若工序u 拖期完工，且u存在緊鄰機(jī)器的前續(xù)工序，則選擇u 作為移動對象。

（2）變量說明

對于任一工序u，根據(jù)u 所屬零件的工藝路線，用JP［u］表示工序u 的零件前續(xù)工序，JS［u］表示工序u的零件后續(xù)工序；依據(jù)u所需的加工機(jī)器，用MP［u］表示工序u的機(jī)器前續(xù)工序，MS［u］表示工序u的機(jī)器后續(xù)工序。這里的機(jī)器前續(xù)或后續(xù)工序表示了某臺機(jī)器上的相鄰加工工序，而相鄰加工工序之間則容許存在機(jī)器空閑時(shí)間，這與上述緊鄰工序?qū)Σ煌?/p>

相關(guān)符號說明：設(shè)工序u的完工時(shí)間為cu、交貨期為du，則u對應(yīng)的零件后續(xù)工序JS［u］的開工時(shí)間為stJS［u］、完工時(shí)間為cJS［u］、交貨期為dJS［u］；而u對應(yīng)的零件前續(xù)工序JP［u］的開工時(shí)間為stJP［u］、完工時(shí)間為cJP［u］、交貨期為dJP［u］。

（3）Swap鄰域結(jié)構(gòu)設(shè)計(jì)

Swap移動操作方法為在緊鄰工序?qū)?nèi)隨機(jī)選取滿足上述移動條件的某一工序u，若u 提前完工，則將u與其緊鄰機(jī)器的后續(xù)工序進(jìn)行位置交換；若u為拖期完工，則將u 與其緊鄰機(jī)器的前續(xù)工序進(jìn)行位置交換。

文獻(xiàn)［11］指出，交換機(jī)器上兩道相鄰工序（工序之間可以存在空閑時(shí)間）可能導(dǎo)致死鎖，而將交換操作限定在緊鄰工序?qū)ι?，產(chǎn)生的新鄰居一定是可行的。另外，將交換操作限定在緊鄰工序?qū)Γ兄诖蟠鬁p小鄰域搜索空間，而且這種交換方式可以避免交換（拖期完工工序，提前完工工序）這樣的緊鄰工序?qū)?，因?yàn)榻粨Q這類工序?qū)?dǎo)致兩道工序的完工時(shí)間更加背離各自的交貨期。

在VNS的每次迭代過程中，通過MP 這類精確數(shù)學(xué)方法得到的調(diào)度解是當(dāng)前機(jī)器加工序列條件下的最優(yōu)解，因此各工序的完工時(shí)間已經(jīng)盡可能靠近各自的交貨期。在此條件下，提前（或拖期）工序和其對應(yīng)的零件后續(xù)（或前續(xù)）工序之間滿足以下兩個(gè)性質(zhì)：

性質(zhì)1 若工序u 提前完工，且不存在緊鄰機(jī)器后續(xù)工序，則u 對應(yīng)的零件后續(xù)工序JS［u］必然提前完工。

證明 若工序u 提前完工，且沒有緊鄰機(jī)器后續(xù)工序，則cu＜du，且cu=stJS［u］，cJS［u］=stJS［u］+pJS［u］=cu+pJS［u］＜du+pJS［u］。因?yàn)閡 和JS［u］的交貨期 滿 足du+pJS［u］≤dJS［u］，所 以cJS［u］≤dJS［u］，即工序JS［u］提前完工，證畢。

性質(zhì)2 如果工序u 拖期完工，且不存在緊鄰機(jī)器前續(xù)工序，則u對應(yīng)的零件前續(xù)工序JP［u］必然拖期完工。

證明 若工序u 拖期完工，且不存在緊鄰機(jī)器前續(xù)工序，則（stu+pu=cu）＞du，且stu=cJP［u］，由此得到stu＞du-pu；因?yàn)閡 和JP［u］的交貨期滿足dJP［u］+pu≤du，所以stu＞du-pu≥dJP［u］，又因?yàn)閟tu=cJP［u］，故cJP［u］≥dJP［u］，即工序JP［u］拖期 完工，證畢。

根據(jù)上述兩個(gè)性質(zhì)有助于快速定位滿足上述移動條件的提前或拖期工序。即當(dāng)選擇的工序u提前完工且沒有緊鄰機(jī)器后續(xù)工序時(shí)，依據(jù)性質(zhì)1可知u 的零件后續(xù)工序也是提前完工，因此依次追溯u的零件后續(xù)工序，直到某一工序滿足提前工序移動條件，則將該工序作為移動對象，通過Swap移動操作來獲得新鄰居；如果u 拖期完工且沒有緊鄰機(jī)器的前續(xù)工序，依據(jù)性質(zhì)2可知u 的零件前續(xù)工序也是拖期完工，則依次追溯u的零件前續(xù)工序，直至某道工序滿足拖期工序的移動條件后，方可進(jìn)行Swap移動操作。

以圖2為例，工序u提前完工，且不存在緊鄰機(jī)器后續(xù)工序（因機(jī)器M1上的工序v 和u 之間存在空閑時(shí)間）。依據(jù)性質(zhì)1追溯到JS［u］，而JS［u］滿足上述提前工序的移動條件，則對緊鄰工序?qū)Γ↗S［u］，JP［v］）執(zhí)行Swap 移動操作。在交換之后獲得的新機(jī)器加工序列中，各工序都在靠近各自交貨時(shí)間點(diǎn)完工，因此新序列優(yōu)于交換之前的機(jī)器加工序列。

（4）Insertion鄰域結(jié)構(gòu)設(shè)計(jì)

Insertion移動操作借鑒了Balas等［12］提出的鄰域結(jié)構(gòu)，并且滿足他們給出的鄰域中僅包含可行解的條件。具體的移動操作方法如下：

1）提前工序的Insertion移動方法 設(shè)選中的工序?yàn)閡，且u 提前完工，w 為塊尾工序：當(dāng)w 的開工時(shí)間stw≤stJS［u］時(shí)，將u移到w 右側(cè)，產(chǎn)生一個(gè)新鄰居；否則在塊內(nèi)u的右側(cè)隨機(jī)選擇某一工序x，當(dāng)x 的開工時(shí)間stx≤stJS［u］時(shí)，將u 移到x 的右側(cè)，產(chǎn)生一個(gè)新鄰居（如圖3）。

2）拖期工序的Insertion移動方法 設(shè)選中的工序?yàn)閡，且u拖期完工，v為塊首工序：若v的完工時(shí)間大于u 的零件前續(xù)工序的完工時(shí)間，即cv≥cJP［u］，則將u 移至v 左側(cè)以產(chǎn)生新鄰居；否則，在塊內(nèi)u的左側(cè)隨機(jī)選擇某一工序x，當(dāng)x 的完工時(shí)間cx≥cJP［u］時(shí)，將u 移至x 左側(cè)，產(chǎn)生新鄰居（如圖4）。

塊是工序集競爭同一機(jī)器資源的結(jié)果，也是工序向交貨期靠攏的障礙，因此優(yōu)先將滿足上述移動條件的工序移至塊首或塊尾，有助于解除塊對工序集的束縛；另外，利用塊與塊之間的間隙來容納待移動工序，有助于減少Insertion移動操作對其他工序開工時(shí)間的影響，有可能改善調(diào)度解的質(zhì)量。

3.3 局域搜索

作為VNS 算法的關(guān)鍵操作之一，局域搜索是在當(dāng)前解的鄰域內(nèi)搜索局域最優(yōu)解。為了增加搜索空間的多樣性（diversification），設(shè)計(jì)了一種基于閾值接受的LS算法；為了避免Swap移動操作嚴(yán)重劣化調(diào)度解，提出一種基于工序重疊度的Swap鄰域過濾機(jī)制。

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

與基于爬山法的傳統(tǒng)LS 方法不同，基于閾值接受的LS算法首先設(shè)定一個(gè)調(diào)度目標(biāo)值的容許偏差（即閾值dr），如果局域搜索得到的調(diào)度解x″和當(dāng)前解x′的調(diào)度目標(biāo)偏差小于閾值，即f（x″）-f（x′）≤dr，則接受x″。在文獻(xiàn)［13］提出的LS方法的基礎(chǔ)上，引入MP方法來精確計(jì)算機(jī)器加工序列上各工序的開工時(shí)間，即利用MP 方法計(jì)算新鄰居Nu（x′）對應(yīng)的JIT 調(diào)度解x″。LS方法如圖5所示。

（2）基于工序重疊度的Swap 鄰域結(jié)構(gòu)過濾機(jī)制

Swap鄰域結(jié)構(gòu)是交換同一臺機(jī)器上的緊鄰工序?qū)?，而這種交換操作有可能導(dǎo)致調(diào)度解產(chǎn)生劣化現(xiàn)象。因此，在LS方法的Swap移動操作中添加了一種基于工序重疊度的過濾機(jī)制。

假設(shè)緊鄰工序?qū)Γ╱，v）滿足移動條件。在圖6a中，工序v 的零件前續(xù)工序JP［v］的加工時(shí)間和工序u的加工時(shí)間有部分重疊，且u 的零件后續(xù)工序JS［u］的加工時(shí)段與v 的加工時(shí)段也有重疊。如果交換（u，v），則u 和JS［u］的完工時(shí)間更加延遲，因此在Swap移動操作時(shí)，這類情況應(yīng)該事先避免。在圖6b中，雖然緊鄰工序?qū)Γ╱，v）進(jìn)行Swap操作前也有部分的加工時(shí)段重疊，但可以利用塊間的空隙減小Swap操作的影響，因此這種條件下的Swap操作有助于改進(jìn)調(diào)度解。

因此，工序?qū)Γ╱，v）重疊度的近似計(jì)算方法為

若將工序重疊度的閾值設(shè)定為Overlapmax，則對于某一緊鄰工序?qū)Γ╱，v），只有當(dāng)Overlap（u，v）≤Overlapmax時(shí)，才容許（u，v）進(jìn)行Swap 移動操作。

4 工序開工時(shí)間優(yōu)化方法——數(shù)學(xué)規(guī)劃方法

在VNS算法中，共有以下3類操作產(chǎn)生各機(jī)器上的加工序列：

（1）VNS的初始化階段 通過EDD 或ALLJIT 排序規(guī)則獲得初始的機(jī)器加工序列。

（2）VNS 的shaking階段通過Swap 或Insertion移動操作獲得新的機(jī)器加工序列。

（3）VNS的局域搜索內(nèi)部迭代過程 通過Insertion或Swap移動操作獲得新鄰居。

當(dāng)VNS通過上述任一操作獲得機(jī)器加工序列確定后，即松弛了JIT-JSP 模型中最難滿足的機(jī)器能力約束，將原模型中的式（5）松弛為如下形式：

因此，在VNS／MP混合算法中，首先通過VNS方法確定出機(jī)器加工序列，然后調(diào)用MP 方法來優(yōu)化各工序的開工時(shí)間取值。用式（6）替換JIT-JSP模型中的式（5），其他約束條件和目標(biāo)函數(shù)保持不變，由此得到已松弛機(jī)器能力約束的MP 的JIT 調(diào)度模型；進(jìn)而利用成熟的數(shù)學(xué)規(guī)劃軟件工具對MP調(diào)度模型進(jìn)行精確求解，以獲得當(dāng)前機(jī)器加工序列內(nèi)各工序的開工時(shí)間優(yōu)化取值。

5 仿真實(shí)驗(yàn)及分析

5.1 JIT調(diào)度算例及實(shí)驗(yàn)環(huán)境

采用文獻(xiàn)［1］設(shè)計(jì)的72 個(gè)JIT 調(diào)度的Benchmark 算例，每個(gè)算例用I-n-m-DD-W-ID 表示，其中：

n∈｛10，15，20｝為零件數(shù)量；m∈｛2，5，10｝為機(jī)器數(shù)量。

DD∈｛tight，loose｝表示同一零件內(nèi)兩道相鄰工序交貨期之間的松弛度。當(dāng)時(shí)為tight時(shí)為loose（r為0～10之間的隨機(jī)整數(shù)）。

W ∈｛equal，tard｝表示提前和拖期懲罰系數(shù)之間的關(guān)系，當(dāng)二者均在［0.1，1］區(qū)間隨機(jī)產(chǎn)生時(shí)，W=equal；當(dāng)提前懲罰系數(shù)在［0.1，0.3］區(qū)間隨機(jī)產(chǎn)生、拖期懲罰系數(shù)在［0.1，1］內(nèi)隨機(jī)產(chǎn)生時(shí)，W=tard。

ID∈｛1，2｝作為一個(gè)標(biāo)識符。根據(jù)上述參數(shù)設(shè)定，共有36種參數(shù)組合，每種參數(shù)組合產(chǎn)生兩個(gè)算例，分別標(biāo)記為“1”和“2”，因此共有72個(gè)測試算例。

VNS／MP混合算法的參數(shù)設(shè)定為：VNS 的最大迭代次數(shù)N=100；LS算法中的qmax=50、閾值dr、工序重疊度閾值Overlapmax=0.5；VNS算法采用C++編程實(shí)現(xiàn)，MP 調(diào)度模型采用FICOTMXpress Optimizer數(shù)學(xué)規(guī)劃軟件進(jìn)行求解。

5.2 實(shí)驗(yàn)結(jié)果及分析

選擇文獻(xiàn)［1，4-5，7］提出的JIT 調(diào)度算法與本文的VNS／MP算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表1～表4所示。在4個(gè)實(shí)驗(yàn)結(jié)果表中：

（1）LB（lower bounds）和UB（upper bounds）分別是文獻(xiàn)［1］給出的JIT 調(diào)度解的下界值和上界值。其中，選擇文獻(xiàn)［1］給出的拉格朗日機(jī)器約束松弛下界值（LBR）和拉格朗日工藝順序約束松弛下界值（LBP）的最大值作為JIT 調(diào)度解的下界值LB。

（2）文獻(xiàn)［4］提出4種CP求解方法，本文選擇4種方法中的最優(yōu)JIT 調(diào)度結(jié)果參與比較。

（3）EA／LS／MP算法是文獻(xiàn)［5］提出的一種JIT混合調(diào)度算法。

（4）TS／MP算法是文獻(xiàn)［7］提出的一種JIT 混合調(diào)度算法。

（5）VNS／MP算法是對每一算例進(jìn)行5次實(shí)驗(yàn)，并取其中的最好結(jié)果參與比較。

表1 零件數(shù)量為10的JIT調(diào)度算例實(shí)驗(yàn)結(jié)果

續(xù)表1

表2 零件數(shù)量為15的JIT調(diào)度算例實(shí)驗(yàn)結(jié)果

表3 零件數(shù)量為20的JIT調(diào)度算例實(shí)驗(yàn)結(jié)果

續(xù)表3

表4 72個(gè)JIT調(diào)度算例仿真結(jié)果統(tǒng)計(jì)表

表中每一行加粗?jǐn)?shù)字表示五種方法（UB，CP，EA／LS／MP，TS／MP 和VNS／MP）相比較得到的JIT 調(diào)度目標(biāo)值的最好值；另外，文獻(xiàn)［7］僅給出了零件數(shù)量為10和15的實(shí)驗(yàn)結(jié)果，因此表3中TS／MP對應(yīng)的列表示為“-”。

從獲得的72個(gè)標(biāo)準(zhǔn)JIT 調(diào)度算例的已知最好解的數(shù)量分析如下：VNS／MP 算法遠(yuǎn)優(yōu)于UB、CP方法，也優(yōu)于EA／LS／MP 方法；與文獻(xiàn)［7］給出的前48 個(gè)算例實(shí)驗(yàn)結(jié)果比較，VNS／MP 算法優(yōu)于TS／MP方法。VNS／MP 算法在調(diào)度規(guī)模（n=10）較小時(shí)優(yōu)勢較為明顯，在中規(guī)模（n=15）時(shí)與EA／LS／MP性能相當(dāng)，在較大規(guī)模（n=20）時(shí)稍劣于EA／LS／MP方法。以下對EA／LS／MP和VNS／MP兩類方法進(jìn)行深入分析。

文獻(xiàn)［5］提出的EA／LS／MP 算法采用兩階段調(diào)度策略，即在確定出機(jī)器加工序列后再優(yōu)化工序開工時(shí)間。首先通過EA 這類群優(yōu)化方法獲得一個(gè)近優(yōu)解，然后利用LS方法搜索得到更優(yōu)的機(jī)器加工序列，最后調(diào)用MP 方法確定機(jī)器加工序列內(nèi)各工序的開工時(shí)間，從而最終獲得JIT 調(diào)度解。因此，三者方法的優(yōu)勢互補(bǔ)所形成的EA／LS／MP算法在JIT 調(diào)度解的優(yōu)化性能方面具有一定優(yōu)勢；隨著調(diào)度規(guī)模的增加，工序間的析取約束更為復(fù)雜，增加了各工序交貨期的緊迫程度，工序交貨期越緊迫，越有可能導(dǎo)致大部分工序出現(xiàn)拖期，而EA／LS／MP 在交貨期緊迫的工況下的優(yōu)化效果相對較好［5］。因此，EA／LS／MP算法在較大規(guī)模（n=20）時(shí)的優(yōu)化性能較好。

VNS／MP算法在所有72 個(gè)算例中取得了35個(gè)算例的已知最好解，并且更新了其中25個(gè)算例的已知最好解。VNS／MP算法的優(yōu)化性能主要源于：VNS中的兩類Swap和Insertion鄰域結(jié)構(gòu)引導(dǎo)各工序向各自的交貨期移動，由此獲得了一個(gè)較好的機(jī)器加工序列；再通過MP 方法對機(jī)器加工序列上的各工序開工時(shí)間進(jìn)行精確計(jì)算，從而獲得了較好的JIT 調(diào)度結(jié)果。另外，VNS中的兩類鄰域結(jié)構(gòu)都是通過移動緊鄰工序?qū)Χx的，當(dāng)調(diào)度算例的工序交貨期較為緊迫時(shí)，同一臺機(jī)器上的工序大都緊鄰加工，使得滿足移動條件的緊鄰工序?qū)^多，由此導(dǎo)致鄰域搜索空間過大，影響了VNS的搜索效率，這也是VNS／MP 算法在較大規(guī)模（n=20）時(shí)表現(xiàn)稍差的原因之一；而當(dāng)調(diào)度問題規(guī)模較小或交貨期較為寬松時(shí)，機(jī)器加工序列中的緊鄰工序?qū)?shù)量相對較少，鄰域搜索空間相對較小，使得VNS的搜索效率較高。

6 結(jié)束語

本文針對JIT-JSP這類復(fù)雜的非正規(guī)指標(biāo)調(diào)度問題，提出一種VNS／MP 混合調(diào)度算法，在VNS的迭代過程中，通過在Swap和Insertion兩類鄰域結(jié)構(gòu)內(nèi)進(jìn)行跳轉(zhuǎn)搜索，獲得較優(yōu)的機(jī)器加工序列，從而松弛了JIT-JSP調(diào)度模型中最難滿足的機(jī)器析取約束；針對既定的機(jī)器加工序列，利用MP這類數(shù)學(xué)方法進(jìn)行工序開工時(shí)間、機(jī)器空閑時(shí)間等的精確計(jì)算，從而獲得一個(gè)較優(yōu)的JIT 調(diào)度解。

鄰域結(jié)構(gòu)和局域搜索是VNS算法的兩個(gè)關(guān)鍵環(huán)節(jié)。本文針對JIT 調(diào)度問題的特點(diǎn)，以引導(dǎo)工序向各自交貨期移動為鄰域設(shè)計(jì)原則，提出以緊鄰工序?qū)橐苿訉ο蟮腟wap 和Insertion 兩類鄰域結(jié)構(gòu)，利用工序塊之間的間隙優(yōu)化機(jī)器上的工序加工序列；LS方法采用基于調(diào)度目標(biāo)值容許偏差的閾值接受機(jī)制，增加了搜索空間的多樣性。

本文采用72個(gè)JIT 調(diào)度的benchmark算例進(jìn)行了測試驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，VNS／MP 混合算法在JIT 調(diào)度解的優(yōu)化性能方面具有一定的優(yōu)勢。本文研究方法對于項(xiàng)目JIT 調(diào)度、物料JIT 供應(yīng)和離散車間精細(xì)化過程管控等具有一定的應(yīng)用價(jià)值。另外，領(lǐng)域結(jié)構(gòu)是決定VNS 算法搜索效率的關(guān)鍵因素，因此下一步的研究工作將針對靜態(tài)JIT 調(diào)度問題，構(gòu)造更高效的領(lǐng)域結(jié)構(gòu)，以有效縮減VNS／MP的計(jì)算時(shí)間。

［1］BAPTISTE P，F(xiàn)LAMINI 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 調(diào)度問題［J］.計(jì)算機(jī)工程與應(yīng)用，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混合算法求解作業(yè)車間JIT 調(diào)度問題［J］.計(jì)算機(jī)集成制造系統(tǒng)，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.