一類帶有deadline約束的作業(yè)車間提前/拖期調(diào)度問題研究

李海寧 孫樹棟

西北工業(yè)大學(xué)，西安，710072

0 引言

以適時(shí)、適量、零庫存為特征的JIT生產(chǎn)模式屬于一類綠色、節(jié)能、低成本的生產(chǎn)方式。而提前/拖期（Earliness/Tardiness，E/T）調(diào)度作為支撐JIT生產(chǎn)的核心技術(shù)之一，現(xiàn)已成為車間調(diào)度領(lǐng)域的重要研究分支。E/T調(diào)度要求訂單或零件在各自的交貨期準(zhǔn)時(shí)完工，提前或拖期完工都會產(chǎn)生相應(yīng)的懲罰成本。如果訂單或零件提前完工，則會產(chǎn)生零件成品庫存成本；對于化學(xué)、食品、藥品等時(shí)效性較強(qiáng)的產(chǎn)品，過早完工則會產(chǎn)生變質(zhì)、失效、揮發(fā)或產(chǎn)品性能退化等問題；另外，訂單或零件的拖期完工則會打亂整個(gè)制造鏈的生產(chǎn)節(jié)拍，使得下游生產(chǎn)環(huán)節(jié)出現(xiàn)整機(jī)配套缺件、停工待料、設(shè)備閑置等諸多問題。因此，關(guān)注訂單或零件的交貨期，以滿足訂單或零件的準(zhǔn)時(shí)化交付為目的，通過E/T調(diào)度來實(shí)現(xiàn)制造車間的精細(xì)運(yùn)作和低成本運(yùn)營，對于改善目前離散制造企業(yè)存在的高投入、低產(chǎn)出、低利潤率等問題具有一定的現(xiàn)實(shí)意義。

文獻(xiàn)［1－2］將車間E/T調(diào)度問題歸結(jié)為單機(jī)E/T調(diào)度和多機(jī)E/T調(diào)度兩類，并指出現(xiàn)有研究主要集中在單機(jī)E/T調(diào)度領(lǐng)域，針對多機(jī)E/T調(diào)度問題的研究相對較少；在多機(jī)E/T調(diào)度研究方面，大多又側(cè)重于并行機(jī)調(diào)度，而對于經(jīng)典的作業(yè)車間調(diào)度研究相對更少。在作業(yè)車間E/T調(diào)度相關(guān)研究中，文獻(xiàn)［3］針對帶有釋放期和交貨期約束的Job shop調(diào)度問題，以最小化總加權(quán)拖期成本為目標(biāo)函數(shù)，采用基于鄰域搜索的遺傳算法進(jìn)行求解，但其目標(biāo)函數(shù)中未考慮提前成本這一指標(biāo)；文獻(xiàn)［4］針對動態(tài)裝配型Job shop的提前/拖期調(diào)度問題，采用一種懲罰加權(quán)系數(shù)呈階梯分布的分配求解規(guī)則，但這種基于規(guī)則的求解方法存在優(yōu)化性能不足的問題；文獻(xiàn)［5］基于模糊控制和遺傳算法，提出求解Job shop提前/拖期問題的聯(lián)合算法，但調(diào)度模型并沒有涉及提前/拖期的懲罰系數(shù)的差異性；文獻(xiàn)［6］將作業(yè)車間E/T調(diào)度轉(zhuǎn)化為約束優(yōu)化問題，并運(yùn)用約束滿足方法進(jìn)行求解。

本文在現(xiàn)有E/T調(diào)度模型的基礎(chǔ)上，添加了零件可接受的最晚完工時(shí)間（即deadline）約束條件，形成了一類帶有零件deadline約束的作業(yè)車間E/T調(diào)度問題（以下簡稱E/T/D調(diào)度問題）。在車間實(shí)際生產(chǎn)中，零部件拖期在所難免，但受下游整機(jī)裝配或客戶訂單的容許拖期范圍限制，零件拖期不能突破零件的deadline，一方面，一旦零件交付延遲于deadline時(shí)限，則會導(dǎo)致下游整機(jī)裝配出現(xiàn)嚴(yán)重拖期或客戶拒收等重大損失；另一方面，在企業(yè)與客戶進(jìn)行訂單交貨期協(xié)商的過程中，企業(yè)利用訂單或零件的deadline來評估客戶訂單的可行性，可以事先避免因訂單交貨期設(shè)置不合理而導(dǎo)致的客戶信譽(yù)受損、丟失客戶等問題。

在E/T調(diào)度中引入零件deadline約束后，即可形成一類零件交貨期窗口，即零件的交貨期和deadline之間的交貨期容許范圍。如果零件在該交貨期窗口內(nèi)完工，則會產(chǎn)生拖期懲罰成本；如果零件實(shí)際完工時(shí)間突破該交貨期窗口，則調(diào)度結(jié)果被視為非法解。這種帶有硬約束的交貨期窗口和文獻(xiàn)［7－8］提出的交貨期窗口存在本質(zhì)差異，文獻(xiàn)［7－8］中的交貨期窗口實(shí)質(zhì)上屬于一類軟約束，即如果零件在此交貨期窗口內(nèi)完工則不受懲罰；若零件拖期完工則產(chǎn)生拖期懲罰成本，但并不會產(chǎn)生非法調(diào)度解。因此，這類帶有交貨期窗口硬約束的作業(yè)車間E/T調(diào)度問題對零部件交貨期的控制更為嚴(yán)格，也更符合JIT對準(zhǔn)時(shí)制生產(chǎn)的管理理念，它適用于對交貨期控制嚴(yán)格的諸如軍工類、外貿(mào)類和配件供應(yīng)類制造企業(yè)或生產(chǎn)車間。

將零件deadline約束條件引入作業(yè)車間E/T調(diào)度問題后，調(diào)度算法設(shè)計(jì)面臨的首要問題是如何避免因零件完工時(shí)間違反deadline約束而出現(xiàn)非法調(diào)度解；另外，在滿足零件deadline約束的前提下，接下來面臨的主要問題就是如何降低E/T調(diào)度總成本。為此，本文提出了一種改進(jìn)型遺傳算法（enhanced genetic algorithm，EGA），以期解決這類對交貨期控制更為嚴(yán)格的作業(yè)車間E/T調(diào)度問題。

1 作業(yè)車間E/T/D調(diào)度模型

對于作業(yè)車間E/T/D調(diào)度問題而言，其調(diào)度任務(wù)是指在滿足工藝路線、機(jī)床能力、零件釋放期和零件deadline等約束的前提下，合理安排承制零件在各機(jī)床上的加工序列和開工時(shí)間，使得提前/拖期總懲罰成本最小。

1.1 相關(guān)變量說明

相關(guān)變量說明如下：rdi為零件Ji的釋放期；di為零件Ji的交貨期為零件Ji的deadline（即可接受的最晚交貨時(shí)間），在同一零件Ji內(nèi)，rdi為零件Ji的開始加工時(shí)間；Ci為零件Ji的加工完成時(shí)間；αi為零件Ji的單位提前懲罰系數(shù)；βi為零件Ji的單位拖期懲罰系數(shù)；為工 序的加工時(shí)間為工序的開工時(shí)間；為工序的完工時(shí)間，）為工序的承制機(jī)床

1.2 數(shù)學(xué)模型

該問題的數(shù)學(xué)模型描述如下：其中，式（1）為目標(biāo)函數(shù)，使得整個(gè)調(diào)度任務(wù)集的提前/拖期懲罰總成本最小化。式（2）為零件Ji的提前懲罰成本。式（3）為零件Ji的拖期懲罰成本。式（4）為工藝路線約束，即同一零件Ji內(nèi)兩道相鄰工序之間的時(shí)序關(guān)系約束。式（5）為機(jī)床能力約束，即同一承制機(jī)床上加工工序隊(duì)列的時(shí)序關(guān)系約束。式（6）為零件釋放期約束，即Ji的開工時(shí)間不應(yīng)早于其釋放期rdi。式（7）為零件deadline約束，即Ji的加工完成時(shí)間不能遲于該零件的。由式（7）可知，零件Ji的交貨期容許范圍為［］。若di＜Ci≤di，則Ji產(chǎn)生拖期懲罰成本；若Ci＞，則因Ji違反零件deadline約束而出現(xiàn)非法調(diào)度解。

2 改進(jìn)型遺傳算法設(shè)計(jì)

針對作業(yè)車間E/T/D調(diào)度模型，在標(biāo)準(zhǔn)遺傳算法框架內(nèi)，重點(diǎn)對解碼操作進(jìn)行了改進(jìn)，形成了圖1所示的EGA求解框架（包含EGA算法的偽代碼和染色體解碼過程兩部分）。在EGA算法設(shè)計(jì)中，染色體編碼采用基于工序的編碼方法［9］；初始種群完全隨機(jī)產(chǎn)生；選擇操作采用精英保留策略和錦標(biāo)賽方法［9］；交叉操作采用文獻(xiàn)［10］提出的POX交叉算子；變異操作采用逆轉(zhuǎn)變異方法［9］。

圖1 EGA求解框架

在車間實(shí)際生產(chǎn)中，零件拖期會帶來諸如整機(jī)裝配延遲、訂單損失和企業(yè)信用度降低等弊端，因此，相對提前問題而言，拖期問題更為嚴(yán)重。首先，零件不拖期或少拖期可以避免或者減小發(fā)生違反零件deadline約束的概率，因此，如何減少零件拖期是求解E/T/D調(diào)度問題首先需要解決的問題；然后，在零件拖期嚴(yán)重導(dǎo)致違反deadline約束時(shí)，如何通過算法內(nèi)部的修復(fù)機(jī)制來及時(shí)調(diào)整調(diào)度結(jié)果以盡可能滿足deadline約束，是E/T/D調(diào)度問題有別于傳統(tǒng)E/T調(diào)度問題的特殊之處；最后，在滿足deadline約束條件下，如何在降低零件拖期懲罰成本的基礎(chǔ)上，進(jìn)一步壓縮零件提前懲罰成本，從而最終保證提前/拖期總懲罰成本最低，這是求解E/T調(diào)度問題區(qū)別于傳統(tǒng)正規(guī)性能指標(biāo)調(diào)度問題的關(guān)鍵所在。

基于以上三個(gè)問題的分析，同時(shí)為了降低E/T調(diào)度問題求解的復(fù)雜度，在設(shè)計(jì)EGA算法時(shí)，采取了拖期優(yōu)先的調(diào)度策略，即將E/T/D調(diào)度問題分解為拖期子問題、修復(fù)子問題和提前子問題，并將一個(gè)染色體的解碼過程劃分為主動解碼、染色體修復(fù)和逆向重調(diào)度三個(gè)階段。

（1）拖期子問題?；谕掀趦?yōu)先的調(diào)度策略，可以將非正則性能指標(biāo)的E/T調(diào)度問題轉(zhuǎn)化為正規(guī)性能指標(biāo)的拖期調(diào)度問題。文獻(xiàn)［11］指出：對于正規(guī)性能指標(biāo)的調(diào)度問題，最優(yōu)調(diào)度解必在主動調(diào)度集中。因此，針對這類拖期調(diào)度子問題，采用主動解碼方法［11］得到主動調(diào)度結(jié)果，以此來降低拖期懲罰成本，同時(shí)可以降低違反deadline約束的發(fā)生概率。

（2）修復(fù)子問題。針對第一階段主動解碼中出現(xiàn)的違反deadline約束的染色體，采用左移修復(fù)和逆轉(zhuǎn)變異［9］相結(jié)合的染色體修復(fù)方法來調(diào)整問題染色體的基因序列，以促使修復(fù)后的染色體滿足deadline約束條件。

（3）提前子問題。在主動解碼得到的主動調(diào)度結(jié)果的基礎(chǔ)上，針對提前子問題，第三解碼階段采用逆向重調(diào)度方法，促使第一階段的主動調(diào)度結(jié)果盡可能向零件的各自交貨期靠攏，以期在保持已有零件拖期成本不變的基礎(chǔ)上進(jìn)一步壓縮提前懲罰成本。

下面針對EGA算法中的染色體修復(fù)和逆向重調(diào)度兩部分進(jìn)行重點(diǎn)闡述。表1所示的調(diào)度算例用來輔助說明操作算子。

表1 調(diào)度算例

2.1 基于關(guān)鍵路徑的染色體修復(fù)方法

在初始種群和經(jīng)過交叉、變異等操作產(chǎn)生的新種群內(nèi)，因deadline約束的存在，在染色體解碼過程中有可能產(chǎn)生非法調(diào)度解。為此，在EGA算法設(shè)計(jì)中，一旦解碼過程出現(xiàn)非法解，則立即中斷當(dāng)前主動解碼操作，并轉(zhuǎn)入染色體修復(fù)環(huán)節(jié)。

染色體修復(fù)操作包括定位產(chǎn)生非法解的源頭和修復(fù)問題染色體兩個(gè)環(huán)節(jié)。非法解的源頭定位通過臨界工序和關(guān)鍵路徑來進(jìn)行篩選和過濾；修復(fù)操作則通過染色體修復(fù)方法來完成。如果染色體修復(fù)成功，即產(chǎn)生滿足E/T/D調(diào)度模型全部約束的新染色體，則用新染色體替換種群中的原不可行染色體。

定義1 臨界工序是指在解碼過程中，導(dǎo)致其所屬零件違反deadline約束所對應(yīng)的當(dāng)前工序。

定義2 關(guān)鍵路徑是由臨界工序依據(jù)“首尾相抵”原則逆向組成的工序鏈。

在關(guān)鍵路徑｛o1，o2，…，ol｝中，ol為臨界工序，o1為依據(jù)零件釋放期開工的工序，“首尾相抵”的原則 是 指 滿 足stl＝stl－1＋pl－1，stl－1＝stl－2＋pl－2，…，st2＝st1＋p1；另外，若ok∈ ｛o1，o2，…，ol｝，oi和ok均屬于同一零件，oj和ok由同一機(jī)床加工，且滿足（stk＝sti＋pi）∧ （stk＝stj＋pj），則選擇oi作為關(guān)鍵路徑上的工序。

定義3：關(guān)鍵塊是指在關(guān)鍵路徑｛o1，o2，…，ol｝內(nèi)，滿足sti＝sti－1＋pi－1（1＜i≤l），且在同一臺機(jī)床上加工的工序所組成的工序集。

圖2 關(guān)鍵路徑和關(guān)鍵塊示例

識別出非法解產(chǎn)生源頭后，若執(zhí)行左移修復(fù)操作的次數(shù)Ml沒有超出其上限值max（Ml），則繼續(xù)執(zhí)行左移操作；否則，執(zhí)行逆轉(zhuǎn)變異［9］修復(fù)操作以大幅度更改染色體基因特征。

左移修復(fù)操作是將在關(guān)鍵路徑上的臨界零件的工序盡量向左移動，使得臨界零件在其deadline之前完工。若某個(gè)塊Bi中有臨界工件工序u，JP［u］為工序u的工件前續(xù)工序，v為塊Bi中位于u左側(cè)的工序；Cv和CJP［u］分別為工序v和JP［u］的完工時(shí)間；由滿足Cv≥CJP［u］的工序v組成集合V。左移操作的具體步驟是遍歷關(guān)鍵路徑上的所有塊，若某塊中有臨界工件工序u，且V≠?，那么任選一個(gè)v∈V，將u移動到v的左側(cè)。

圖3 修復(fù)后的染色體主動解碼結(jié)果

2.2 逆向重調(diào)度

實(shí)際上，在保持第一解碼階段拖期成本不變的基礎(chǔ)上，延遲零件和工序的開工時(shí)間有助于降低提前懲罰成本。為此，在EGA算法設(shè)計(jì)中，引入逆向重調(diào)度方法，具體計(jì)算步驟如下：

（1）確定逆向重調(diào)度的坐標(biāo)原點(diǎn)。染色體完成解碼后，對于提前完工的零件集E＝｛Ji｜Ci≤di｝，選擇其交貨期最大值me；對于拖期完工的零件集T＝｛Ji｜Ci＞di｝，選擇其完工時(shí)間的最大值mt，取坐標(biāo)原點(diǎn)為Or＝ max（me，mt）。

圖4 逆向重調(diào)度結(jié)果

圖5 解碼最終結(jié)果

3 仿真實(shí)驗(yàn)

為了測試EGA算法性能，選擇混合整數(shù)規(guī)劃（MIP）方法和EGA算法進(jìn)行比較。EGA通過MATLAB 7.0編程實(shí)現(xiàn)，利用 FICOTMXpress軟件對上述E/T/D調(diào)度模型進(jìn)行MIP求解。二者都在1.73GHz、1.0GB RAM 的計(jì)算機(jī)上運(yùn)行。時(shí)間閾值為1200s，即當(dāng)求解某個(gè)調(diào)度子問題的計(jì)算時(shí)間超過1200s時(shí)，則認(rèn)為該調(diào)度問題無解。

3.1 調(diào)度用例

在文獻(xiàn)［12］構(gòu)造的算例基礎(chǔ)上，本文通過調(diào)整問題規(guī)模、交貨期松弛度和deadline松弛度產(chǎn)生18組參數(shù)組合，每個(gè)參數(shù)組合隨機(jī)生成10個(gè)調(diào)度子問題，則共有180個(gè)調(diào)度問題作為測試用例。

（1）調(diào)度問題規(guī)模n×m分別為10×10、15×10和20×10。

（2）每個(gè)零件隨機(jī)遍歷所有機(jī)器，加工時(shí)間在［1，99］間隨機(jī)產(chǎn)生。

（3）所有零件的釋放期為0。

（4）各零件交貨期在［0.75tlblf，1.25tlblf］區(qū)間內(nèi)隨機(jī)產(chǎn)生。其中，tlb為零件的完工時(shí)間下限值，由文獻(xiàn)［13］中的公式計(jì)算得到；lf∈ ｛1.3，1.5｝為交貨期松弛度。

（5）零件Ji的deadline為di＝ddi，其中，d∈｛1.0，1.2，1.4｝為deadline松弛度。

（6）提前懲罰系數(shù)和拖期懲罰系數(shù)在［1，20］區(qū)間內(nèi)隨機(jī)產(chǎn)生。

因此，3個(gè)問題規(guī)模、2個(gè)交貨期松弛度、3個(gè)deadline松弛度，共同構(gòu)成18種參數(shù)組合，采用N－M－lf－d標(biāo)記一種參數(shù)組合。

EGA算法的參數(shù)設(shè)置如下：種群規(guī)模為50，最大迭代次數(shù)為100，交叉概率為0.9，變異概率為0.1，錦標(biāo)賽選擇算子中的競賽規(guī)模K從｛2，3｝中隨機(jī)選取，最大修復(fù)次數(shù)max（Mr）＝10000，左移修復(fù)操作的上限次數(shù)max（Ml）＝200。

3.2 評價(jià)指標(biāo)

①有解數(shù)。每組10個(gè)調(diào)度子問題中，在1200s內(nèi)求得調(diào)度解的個(gè)數(shù)。

②平均計(jì)算時(shí)間。每組10個(gè)調(diào)度子問題計(jì)算時(shí)間的平均值，無解子問題以1200s參與計(jì)算。

③最小成本值。每組10個(gè)調(diào)度子問題中，有解子問題對應(yīng)的提前/拖期調(diào)度總成本的最小值，用以評測調(diào)度算法的尋優(yōu)能力。

④平均成本值。每組10個(gè)調(diào)度子問題中，有解子問題的提前/拖期調(diào)度總成本的平均值，用以評測算法在某類調(diào)度環(huán)境下的搜索能力。

⑤平均空閑時(shí)間。每組10個(gè)調(diào)度子問題中，各零件最后兩道工序之間的空閑時(shí)間的平均值，用來評測調(diào)度結(jié)果的均衡性。

⑥平均流動時(shí)間。每組10個(gè)調(diào)度子問題中，所有零件流動時(shí)間的平均值。

3.3 仿真結(jié)果及分析

EGA和MIP的實(shí)驗(yàn)結(jié)果見表2，表2中的N/A表示在限定時(shí)間1200s內(nèi)算法未得到調(diào)度解。圖6、圖7所示分別為兩種算法在平均空閑時(shí)間、平均流動時(shí)間兩個(gè)指標(biāo)方面的比較結(jié)果。

表2 仿真實(shí)驗(yàn)結(jié)果

由表2可知，除較小規(guī)模10－10－1.3－1.0組算例外，EGA算法在每組算例中的有解數(shù)均優(yōu)于MIP方法；尤其當(dāng)調(diào)度問題規(guī)模逐漸增大時(shí)，EGA解決問題數(shù)的優(yōu)勢愈加明顯。在限定的1200s內(nèi)，MIP方法在180個(gè)算例中只取得了92個(gè)算例的調(diào)度解，這是因?yàn)镸IP方法的計(jì)算代價(jià)隨著調(diào)度問題規(guī)模的增大而呈指數(shù)增加，導(dǎo)致MIP方法在限定時(shí)間內(nèi)解決問題數(shù)量相對較少。從最小成本值指標(biāo)來看，EGA算法和MIP方法在較小規(guī)模算例上取得的最優(yōu)值一致，由于MIP方法屬于一類數(shù)學(xué)優(yōu)化方法，而EGA算法能取得與這類精確數(shù)學(xué)方法同樣的結(jié)果，證明EGA算法同樣具有搜索到最優(yōu)解的能力。

對比圖6和圖7可知，在平均空閑時(shí)間和平均流動時(shí)間兩項(xiàng)指標(biāo)方面，EGA算法均優(yōu)于MIP方法，這得益于在染色體解碼過程中引入了逆向重調(diào)度方法，使得調(diào)度結(jié)果盡可能右移并接近零件的各自交貨期，從而使得零件中間工序之間的等待時(shí)間大大縮短。

圖6 EGA/MIP在平均空閑時(shí)間指標(biāo)下的比較結(jié)果

圖7 EGA/MIP在平均流動時(shí)間指標(biāo)下的比較結(jié)果

4 結(jié)論

本文在傳統(tǒng)E/T調(diào)度問題的基礎(chǔ)上，引入零件deadline時(shí)間約束條件，形成了帶有零件deadline約束的作業(yè)車間E/T/D調(diào)度問題，這類問題的求解有助于解決目前E/T調(diào)度中存在的零件拖期沒有上界的問題，同時(shí)有利于評估訂單交貨期的可行性，從而避免因零部件或訂單交付嚴(yán)重拖期而導(dǎo)致的訂單拒收、信譽(yù)受損等問題。

針對E/T/D調(diào)度問題，采取拖期優(yōu)先的調(diào)度策略，將這類非正規(guī)性能指標(biāo)的調(diào)度問題轉(zhuǎn)化為拖期子問題、修復(fù)子問題和提前子問題，并在染色體解碼過程中分別采用主動解碼、染色體修復(fù)和逆向重調(diào)度三種方法，以此實(shí)現(xiàn)在滿足零件deadline約束條件下盡可能降低提前/拖期懲罰總成本的目的。最后采用調(diào)度問題規(guī)模、交貨期松弛度和deadline松弛度三個(gè)參數(shù)可調(diào)節(jié)的共計(jì)180個(gè)調(diào)度實(shí)例進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，EGA算法在解決問題數(shù)、尋優(yōu)能力、調(diào)度結(jié)果的均衡性等方面具有一定的優(yōu)勢。

［1］Lauff V，Werner F.Scheduling with Common Due Date，Earliness and Tardiness Penalties for Multimachine Problems：A Survey［J］.Mathematical and Computer Modelling，2004，40（5/6）：637－655.

［2］Sen T，Sulek J M，Dileepan P.Static Scheduling Research to Minimize Weighted and Unweighted Tardiness：A State－of－the－art Survey［J］.Int.J.Production Economics，2003，83（1）：1－12.

［3］Essafi I，Mati Y，Stephane D P.A Genetic Local Search Algorithm for Minimizing Total Weighted Tardiness in the Job－shop Scheduling Problem［J］.Computers ＆ Operations Research，2008，35（8）：2599－2616.

［4］Thiagarajan S，Rajendran C.Scheduling in Dynamic Assembly Job－shops to Minimize the Sum of Weighted Earliness， Weighted Tardiness and Weighted Flowtime of Jobs［J］.Computers ＆ Industrial Engineering，2005，49（4）：463－503.

［5］姚偉力，楊德禮，胡祥培.Job－shop提前/拖期調(diào)度問題的研究［J］.控制與決策，2000，15（3）：322－324.

［6］Sadeh N.Micro－boss：A Micro－opportunistic Factory Scheduler［J］.Expert Systems with Applications，1993，6（3）：377－392.

［7］劉興初，趙千川，鄭大鐘.用GA算法解不同交貨期窗口下的E/T調(diào)度問題［J］.清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2000，40（7）：59－62.

［8］黃德才，朱藝華，王萬良.帶公共交貨期窗口的提前/拖期非等同多機(jī)調(diào)度問題［J］.系統(tǒng)理論與實(shí)踐，2001（4）：64－69.

［9］王凌.車間調(diào)度及其遺傳算法［M］.北京：清華大學(xué)出版社，2003.

［10］張超勇，饒運(yùn)清，李培根，等.基于POX交叉的遺傳算法求解Job－Shop調(diào)度問題［J］.中國機(jī)械工程，2004，15（23）：2149－2153.

［11］Baker K R.Introduction to Sequencing and Scheduling［M］.New York：Wisely，1974.

［12］Beck J C，Refalo P.A Hybrid Approach to Scheduling with Earliness and Tardiness Costs［J］.Annals of Operations Research，2003，118（1/4）：49－71.

［13］Taillard E.Benchmarks for Basic Scheduling Problems［J］.European Journal of Operational Research，1993，64（2）：278－285.