李豆豆

(江蘇省郵電規(guī)劃設(shè)計(jì)院有限責(zé)任公司 城市信息工程院，江蘇 南京 210019)

生產(chǎn)調(diào)度的啟發(fā)式規(guī)則研究綜述

李豆豆

(江蘇省郵電規(guī)劃設(shè)計(jì)院有限責(zé)任公司 城市信息工程院，江蘇 南京 210019)

啟發(fā)式規(guī)則是求解生產(chǎn)調(diào)度問題比較簡單有效的方法，與其他生產(chǎn)調(diào)度算法相結(jié)合，在過去50多年里得到了深入研究和廣泛應(yīng)用。首先綜述了國內(nèi)外對生產(chǎn)調(diào)度啟發(fā)式規(guī)則的研究狀況，闡述了啟發(fā)式規(guī)則及其分類，介紹了啟發(fā)式規(guī)則性能評價(jià)指標(biāo)和魯棒性，進(jìn)一步分析了新提出的啟發(fā)式規(guī)則。在總結(jié)啟發(fā)式算法的基礎(chǔ)上，給出了啟發(fā)式規(guī)則應(yīng)用于智能優(yōu)化調(diào)度算法的一般性框架。最后展望了生產(chǎn)調(diào)度啟發(fā)式規(guī)則的進(jìn)一步研究方向。

生產(chǎn)調(diào)度；啟發(fā)式規(guī)則；分配規(guī)則；智能優(yōu)化算法；專家系統(tǒng)

生產(chǎn)調(diào)度問題在過去50多年里得到了深入的研究和發(fā)展，形成了比較完備的理論體系和成熟的應(yīng)用系統(tǒng)，極大地提高了企業(yè)或行業(yè)的生產(chǎn)效率和效益[1-7]。但作為典型的NP問題，生產(chǎn)調(diào)度問題即使規(guī)模很小，也很難得到其最優(yōu)解[5]。而具有求解速度快、容易得到滿意甚至近似調(diào)度最優(yōu)解的啟發(fā)式規(guī)則得到了廣泛的研究。Baker和Dzielinski在1960年首次進(jìn)行了啟發(fā)式規(guī)則的計(jì)算機(jī)仿真研究，分析了在不同處理次數(shù)下的調(diào)度效果和不同啟發(fā)式規(guī)則對調(diào)度的影響作用[8]。Gere對調(diào)度規(guī)則(scheduling rule)、分配規(guī)則(dispatching rule)、優(yōu)先規(guī)則(priority rule)和啟發(fā)式(heuristic)進(jìn)行了定義，明確了這些概念的聯(lián)系和區(qū)別[9]。1970年Day和Hottenstein提出了啟發(fā)式規(guī)則的分類方法，啟發(fā)式規(guī)則被分為局部的或全局的、動(dòng)態(tài)的或靜態(tài)的[10]。Jones于1973年試圖提出一種經(jīng)濟(jì)框架，可對各種作業(yè)車間分配規(guī)則進(jìn)行評價(jià)[11]。1975年，Hershauer和Ebert采用決策因素的線性加權(quán)之和定義排序規(guī)則，提出一種選擇排序規(guī)則的標(biāo)準(zhǔn)化方法，希望在任何作業(yè)車間調(diào)度問題中都能找到一個(gè)最佳的排序規(guī)則[12]。Panwalkar和Iskander在1977年總結(jié)了之前20多年內(nèi)提出的100多個(gè)優(yōu)先分配規(guī)則，給出每個(gè)啟發(fā)式規(guī)則的定義和出處，并將其分為簡單優(yōu)先規(guī)則、組合式優(yōu)先規(guī)則、加權(quán)優(yōu)先規(guī)則、啟發(fā)式調(diào)度規(guī)則和其他規(guī)則等5類[13]。1989年，Haupt通過仿真實(shí)驗(yàn)深入研究了之前30多年提出的優(yōu)先規(guī)則，給出了基本優(yōu)先規(guī)則的分類、描述和評價(jià)[14]。Philipoom和Fry研究了一些著名啟發(fā)式規(guī)則對于負(fù)載均衡和工作流程結(jié)構(gòu)的魯棒性，結(jié)果表明大部分規(guī)則都不受這兩個(gè)因素的影響[15]。Holthaus和Rajendran于1997年給出了評價(jià)啟發(fā)式規(guī)則性能的7個(gè)指標(biāo)：平均在線時(shí)間、最大在線時(shí)間、在線時(shí)間方差、拖期工作比例、平均拖期時(shí)間、最大拖期時(shí)間和拖期時(shí)間方差，這些指標(biāo)越小，啟發(fā)式規(guī)則性能越優(yōu)，并提出了PT+WINQ、PT+WINQ+AT、PT+WINQ+SL、PT+WIGQ+AT+SL和MCOVERT等5個(gè)結(jié)構(gòu)簡單且性能較佳的新啟發(fā)式規(guī)則[16]。Mohanasundaram和Natarajan等依此評價(jià)指標(biāo)，又提出了ECT-FIFO、LF-ECT、JDD-FIFO和LFD-JDD等4個(gè)新的啟發(fā)式規(guī)則[17]。Canbolat 和Gundogar將模糊數(shù)學(xué)應(yīng)用到啟發(fā)式規(guī)則中，提出模糊啟發(fā)式規(guī)則(Fuzzy Priority Rule, FPR)[18]。Natarajan等通過加權(quán)改進(jìn)在線時(shí)間和拖期時(shí)間的相關(guān)評價(jià)指標(biāo)，提出了具有較好性能的新啟發(fā)式規(guī)則[19]。

國內(nèi)對生產(chǎn)調(diào)度啟發(fā)式規(guī)則的研究較晚。1995年王家廞提出了一種新的啟發(fā)式調(diào)度規(guī)則(RH)，在以拖期時(shí)間為準(zhǔn)則的前提下，RH優(yōu)于簡單的調(diào)度規(guī)則[20]。任艷頻等對啟發(fā)式規(guī)則的內(nèi)涵和分類進(jìn)行了系統(tǒng)的研究，從3個(gè)不同方面詳細(xì)分析了啟發(fā)式規(guī)則在生產(chǎn)調(diào)度問題中的應(yīng)用[21]。2006年曾相戈提出了一個(gè)新的啟發(fā)式規(guī)則(Family Slack, FSLACK)，在求解雙目標(biāo)帶約束工件成類的平行機(jī)器調(diào)度問題上具有較好的效果[22]。黃竹君對11種啟發(fā)式規(guī)則在各種仿真參數(shù)下的調(diào)度性能進(jìn)行了評價(jià)分析，總結(jié)了不同啟發(fā)式規(guī)則的調(diào)度性能，為啟發(fā)式規(guī)則的應(yīng)用提供了有價(jià)值的參考[23]。舒海生等提出了2個(gè)新的啟發(fā)式規(guī)則，較好地解決了FMS混合調(diào)度系統(tǒng)中的工件選擇和運(yùn)刀小車的啟發(fā)式調(diào)度問題[24]。

由于啟發(fā)式規(guī)則具有較快找到可行解的能力，很多研究者嘗試將啟發(fā)式規(guī)則融入到其他算法中，建立啟發(fā)式規(guī)則庫，加快算法收斂的速度，提高全局最優(yōu)解的質(zhì)量[25-31]。

本文系統(tǒng)綜述了各啟發(fā)式規(guī)則的定義和描述，啟發(fā)式規(guī)則的分類方法、性能評價(jià)指標(biāo)和魯棒性，總結(jié)了新近提出的啟發(fā)式規(guī)則，介紹了如何利用這些啟發(fā)式規(guī)則快速尋找生產(chǎn)調(diào)度問題的近似最優(yōu)解。在此基礎(chǔ)上，給出了啟發(fā)式規(guī)則與智能優(yōu)化算法相結(jié)合求解生產(chǎn)調(diào)度問題的一般性框架，并指出了啟發(fā)式規(guī)則進(jìn)一步研究和應(yīng)用的方向。

1 啟發(fā)式規(guī)則

1.1定義及分類

生產(chǎn)調(diào)度的啟發(fā)式規(guī)則，或稱為調(diào)度規(guī)則，是由若干個(gè)優(yōu)先規(guī)則和啟發(fā)式組合而成。其中，優(yōu)先規(guī)則是依據(jù)某種方法計(jì)算等待工序的優(yōu)先數(shù)，并按優(yōu)先數(shù)的大小選擇下一道在當(dāng)前空閑機(jī)器上將進(jìn)行加工的工序，而啟發(fā)式則是簡單的某種經(jīng)驗(yàn)法則。

啟發(fā)式規(guī)則按照所使用計(jì)算信息范圍可分為局部啟發(fā)式規(guī)則、全局啟發(fā)式規(guī)則，按照優(yōu)先數(shù)與時(shí)間關(guān)系可分為靜態(tài)啟發(fā)式規(guī)則、動(dòng)態(tài)啟發(fā)式規(guī)則，按照啟發(fā)式規(guī)則的復(fù)雜程度可分為簡單啟發(fā)式規(guī)則、組合式啟發(fā)式規(guī)則、加權(quán)啟發(fā)式規(guī)則、專家經(jīng)驗(yàn)啟發(fā)式規(guī)則等。

1.2生產(chǎn)調(diào)度模型

生產(chǎn)調(diào)度問題是對資源、工單和優(yōu)化目標(biāo)三要素，在滿足資源、工藝順序、交貨期等物理性約束和非物理性約束條件下，尋找工單在相關(guān)資源上的加工順序和開工時(shí)刻，使得某一或某些優(yōu)化目標(biāo)最優(yōu)。可通過三域表示法α|β|γ對生產(chǎn)調(diào)度問題進(jìn)行分類和建模，其中α代表生產(chǎn)環(huán)境，β代表生產(chǎn)環(huán)境、資源和工單的加工性質(zhì)及約束，γ代表優(yōu)化目標(biāo)[7， 32-33]。

域α描述的主要生產(chǎn)環(huán)境包括：單機(jī)(l)、同速同類并行機(jī)(Pm)、不同速同類并行機(jī)(Qm)、非同類并行機(jī)(Rm)、流水作業(yè)車間(Fm)、柔性流水作業(yè)車間(FFc)、作業(yè)車間(Jm)、柔性作業(yè)車間(FJc)和自由作業(yè)車間(Qm)。

域β描述的主要資源、工單加工特點(diǎn)和約束條件包括：最早開工時(shí)刻約束(rj)、最小準(zhǔn)備時(shí)間約束(sijk)、加工中斷(prmp)、加工次序約束(prec)、工單簇(fmls)、批處理(batch(b))、設(shè)備異常(brkdwn)、設(shè)備質(zhì)量等級約束(Mj)、排列約束(prmu)、阻滯(block)、不可等待(nwt)和重入(rcrc)。

域γ描述的主要優(yōu)化目標(biāo)包括：最大完工時(shí)刻(Cmax)、最大在線時(shí)間(Fmax)、最大拖期時(shí)間(Lmax)、加權(quán)完工時(shí)刻之和(∑wjCj)、加權(quán)在線時(shí)間之和(∑wjFj)、加權(quán)完工時(shí)刻折算之和(∑wj(1-erCj))、加權(quán)拖期時(shí)間之和(∑wjTj)和加權(quán)拖期工單數(shù)量之和(∑wjUj)。

1.3基本啟發(fā)式規(guī)則

目前，已提出的啟發(fā)式規(guī)則有100多種，但是很多啟發(fā)式規(guī)則都是對最原始啟發(fā)式規(guī)則的改進(jìn)或組合，這些最原始啟發(fā)式規(guī)則稱之為基本啟發(fā)式規(guī)則。定義和描述基本啟發(fā)式規(guī)則是研究啟發(fā)式規(guī)則的基礎(chǔ)，表1給出了基本啟發(fā)式規(guī)則的名稱、定義和優(yōu)先數(shù)的數(shù)學(xué)模型[13-14]。

表1 基本啟發(fā)式規(guī)則

接上表

名稱定義Zi(t)OCR工序臨界比越小越優(yōu)先dij-tpijALL/OPN每一剩余工序可用時(shí)間越小越優(yōu)先di-tni-j+1S/OPN每一剩余工序松弛時(shí)間越小越優(yōu)先di-t-∑niq=jpiqni-j+1S/WKR每單位剩余工作量松弛時(shí)間越小越優(yōu)先di-t-∑niq=jpiq∑niq=jpiqWINQ下一工序等待隊(duì)列的總加工時(shí)間越小越優(yōu)先Yi，j+1(t)NINQ下一工序等待隊(duì)列的總工序數(shù)越小越優(yōu)先Ni，j+1(t)

其中，數(shù)學(xué)模型中用到的符號說明如下：n代表工單的數(shù)量；m代表設(shè)備的數(shù)量；pij代表工序Qij(設(shè)為當(dāng)前等待加工工序)的加工時(shí)間，i=1,2,…,n，j=1,2,…,ni；Zi(t)代表工單i在調(diào)度時(shí)刻t的優(yōu)先數(shù)，其值越小越優(yōu)先選擇；ri代表工單i的最早開工時(shí)刻；rij代表工單i在設(shè)備j上的最早開工時(shí)刻，i=1,2,…,n，j=1,2,…,m；di代表工單i的交貨期；dij代表工序Oij的最晚完工時(shí)刻。

2 啟發(fā)式規(guī)則性能分析

為了客觀正確評價(jià)啟發(fā)式規(guī)則應(yīng)用于不同調(diào)度問題所表現(xiàn)出的調(diào)度性能，已有文獻(xiàn)對啟發(fā)式規(guī)則的評價(jià)指標(biāo)和調(diào)度效果進(jìn)行了大量的研究[16，34-37]，表2總結(jié)了啟發(fā)式規(guī)則通用評價(jià)指標(biāo)，是啟發(fā)式規(guī)則性能分析和新啟發(fā)式規(guī)則提出的基礎(chǔ)。其中，F(xiàn)i代表工單i的在線時(shí)間，Ti代表工單i的拖期時(shí)間，nT代表拖期工單數(shù)。

表2 啟發(fā)式規(guī)則評價(jià)指標(biāo)

基于加工時(shí)間的SPT規(guī)則是最著名、應(yīng)用最廣泛和性能最優(yōu)的啟發(fā)式規(guī)則之一，在高負(fù)荷率作業(yè)車間和流水線車間環(huán)境下，對于最小化平均在線時(shí)間和最小化平均拖期時(shí)間評價(jià)指標(biāo)具有較好的性能。EDD和ODD規(guī)則是基于交貨期僅有的重要靜態(tài)規(guī)則，對于最小化拖期時(shí)間表現(xiàn)出良好性能，但隨著負(fù)載程度的提高，其性能逐漸下降。全局啟發(fā)式規(guī)則中最有名的WINQ規(guī)則，在許多情況下都表現(xiàn)出良好的性能，其目的是盡量保持加工中心的持續(xù)性，減少暫態(tài)瓶頸效應(yīng)。而基于松弛時(shí)間的動(dòng)態(tài)啟發(fā)式規(guī)則，對于最小化平均拖期時(shí)間和最小化拖期時(shí)間方差具有優(yōu)越的性能。基于基本啟發(fā)式規(guī)則組合而成的規(guī)則，其性能都優(yōu)于單個(gè)啟發(fā)式規(guī)則。PT+WINQ規(guī)則的優(yōu)化性能優(yōu)于SPT規(guī)則和WINQ規(guī)則，對于最小化平均在線時(shí)間性能更優(yōu)。PT+WINQ+AT規(guī)則和PT+WINQ+AT+SL規(guī)則對于最小化最大在線時(shí)間和最小化在線時(shí)間方差具有較好性能。PT+WINQ+SL規(guī)則和PT+WINQ+AT+SL規(guī)則對于最小化最大拖期時(shí)間和最小化拖期時(shí)間方差具有較好性能[14,16,39]。

3 啟發(fā)式規(guī)則魯棒性

已有文獻(xiàn)對啟發(fā)式規(guī)則的研究主要基于以下兩個(gè)假設(shè)：(1)自由作業(yè)車間環(huán)境，即有無限多個(gè)工藝路線；(2)所有設(shè)備的能力都是均衡的，不存在長期性瓶頸。而實(shí)際上制造生產(chǎn)線往往有更多標(biāo)準(zhǔn)化的工藝路線，能力也是不均衡的，Philipoom等提出研究啟發(fā)式規(guī)則對于負(fù)載均衡和工藝流程結(jié)構(gòu)的魯棒性[15]，只有不受這兩種因素影響的啟發(fā)式規(guī)則，才能被更好地應(yīng)用于各種生產(chǎn)調(diào)度。

研究[16-17,19,40]表明,大部分已提出的啟發(fā)式規(guī)則對于負(fù)載均衡并不敏感，僅僅WINQ不具有魯棒性。而對于工藝流程結(jié)構(gòu)，啟發(fā)式規(guī)則表現(xiàn)出很高的敏感性，SLK/NOP規(guī)則、MODD規(guī)則、CoverT規(guī)則和WINQ規(guī)則完全不具有魯棒性，SLK/NOP規(guī)則對于工藝流程結(jié)構(gòu)最敏感，在自由車間環(huán)境下其性能更好。一般在某個(gè)環(huán)境下性能較好的啟發(fā)式規(guī)則，在其他環(huán)境下其性能也較優(yōu)。

4 啟發(fā)式規(guī)則發(fā)展及應(yīng)用

4.1新提出的啟發(fā)式規(guī)則

已提出的啟發(fā)式規(guī)則及對其性能評價(jià)和魯棒性分析的研究成果,對于在不同生產(chǎn)調(diào)度環(huán)境下啟發(fā)式規(guī)則的選擇、新啟發(fā)式規(guī)則的設(shè)計(jì)都具有一定的指導(dǎo)和借鑒作用。Holthaus等基于加工時(shí)間啟發(fā)式規(guī)則、基于交貨期啟發(fā)式規(guī)則和動(dòng)態(tài)啟發(fā)式規(guī)則的性能特點(diǎn)，提出了綜合性能較優(yōu)的PT+WINQ、PT+WINQ+AT、PT+WINQ+SL、PT+WINQ+AT+SL和MCOVERT等5個(gè)啟發(fā)式規(guī)則[16]。為了最小化最大在線時(shí)間和在線時(shí)間方差、最大拖期時(shí)間和拖期時(shí)間方差，Mohanasundaram等提出了ECT-FIFO規(guī)則、LF-ECT規(guī)則、JDD-FIFO規(guī)則和LFD-JDD規(guī)則，在優(yōu)化評價(jià)指標(biāo)方面具有較好的性能[17]。針對離散型制造車間的特點(diǎn)，郝文育等在保證交貨期前提下，提出了一種啟發(fā)式調(diào)度算法，加入了工時(shí)變動(dòng)容忍系數(shù)、批量拆分次數(shù)等參數(shù)，并對算法進(jìn)行了擴(kuò)充和驗(yàn)證[40]。Natarajan等對評價(jià)指標(biāo)進(jìn)行了改進(jìn)，提出了加權(quán)評價(jià)指標(biāo)，并提出了6個(gè)加權(quán)組合式啟發(fā)式規(guī)則，表現(xiàn)出優(yōu)于已存在啟發(fā)式規(guī)則的性能[19]。李崢峰等針對沖壓車間生產(chǎn)線無等待并行流水作業(yè)特點(diǎn)，提出了沖壓作業(yè)的重復(fù)、折回和前行等排程規(guī)則，保證得到可行的調(diào)度解[41]。針對FMS混合調(diào)度系統(tǒng)中的工件選擇和運(yùn)刀小車的啟發(fā)式調(diào)度問題，舒海生等提出了兩個(gè)新的啟發(fā)式規(guī)則，能夠較好地改善FMS的各項(xiàng)性能指標(biāo)[24]。

4.2啟發(fā)式算法

早期的啟發(fā)式算法求解生產(chǎn)調(diào)度問題多采用啟發(fā)式規(guī)則，目的是在有效時(shí)間內(nèi)產(chǎn)生可接受的調(diào)度，主要分為兩類[6,42]：

a.一次通過啟發(fā)式。

通過基于啟發(fā)式規(guī)則一次固定一個(gè)工序，簡單地構(gòu)造一個(gè)完全解，其特點(diǎn)是快且能找到不太壞的解。

b.多次通過啟發(fā)式(也稱搜索啟發(fā)式)。

重復(fù)應(yīng)用一次通過啟發(fā)式，通過產(chǎn)生多個(gè)解來得到更好的解，其特點(diǎn)是解的質(zhì)量較高，但卻以損失計(jì)算時(shí)間為代價(jià)。

3類不同調(diào)度[1,43]的提出，從解空間角度為啟發(fā)式算法的應(yīng)用奠定了基礎(chǔ)，其在解空間的分布情況如圖1所示。

一個(gè)調(diào)度方案中若不存在局部左移動(dòng)，則稱為半活動(dòng)調(diào)度(Semi-active Scheduling)，若不存在全局左移動(dòng)，則稱為活動(dòng)調(diào)度(Active Scheduling)，若沒有機(jī)器在開始加工時(shí)處于閑置狀態(tài)，則稱為無延遲調(diào)度(Non-delay Scheduling)。

圖1 三類調(diào)度在解空間的分布

產(chǎn)生活動(dòng)調(diào)度的啟發(fā)式算法流程如圖2所示，其中PSt為階段t已調(diào)度工序的部分調(diào)度，St為階段t可調(diào)度工序集合，Ti為工序i的加工時(shí)間，σi為工序i(i∈St)能夠開始的最早時(shí)刻，φi為工序i(i∈St)能夠完成的最早時(shí)刻，φi=σi+Ti。

圖2 產(chǎn)生活動(dòng)調(diào)度啟發(fā)式算法流程

4.3與智能優(yōu)化算法結(jié)合的一般框架

近年來，一些智能優(yōu)化算法如遺傳算法、模擬退火算法、粒子群算法、禁忌搜索算法、螞蟻算法、生存遷移算法[44]、免疫算法等，由于具有全局收斂性、普遍適應(yīng)性和較低的經(jīng)驗(yàn)復(fù)雜性等優(yōu)點(diǎn)，得到了廣泛的研究和應(yīng)用[6]，為解決生產(chǎn)調(diào)度問題提供了比較可行的方法。

智能優(yōu)化算法具有搜索效率高、容易跳出局部最優(yōu)、開放式結(jié)構(gòu)、適應(yīng)性強(qiáng)和魯棒性好等特點(diǎn)，在生產(chǎn)調(diào)度領(lǐng)域得到了深入研究和應(yīng)用。其與啟發(fā)式規(guī)則的結(jié)合，不僅保證了解的全局最優(yōu)性，而且提高了算法的搜索效率和搜索質(zhì)量[25-31]。

智能優(yōu)化算法一般由初始化種群、搜索(進(jìn)化)算子、適應(yīng)度計(jì)算和終止條件構(gòu)成，初始化種群和進(jìn)化算子兩個(gè)部分都很容易產(chǎn)生非法解或不太理想解，會(huì)大大降低算法的搜索效率，而引入啟發(fā)式規(guī)則后，既能提高算法進(jìn)入搜索空間的質(zhì)量，又能減少大量非法搜索路徑，提升算法綜合性能。圖3給出了啟發(fā)式規(guī)則與智能優(yōu)化算法結(jié)合的一般框架。

圖3 啟發(fā)式規(guī)則與智能優(yōu)化算法結(jié)合的一般框架

5 總結(jié)和展望

啟發(fā)式規(guī)則仍然是生產(chǎn)調(diào)度問題求解方法研究的一個(gè)重要分支，由于在實(shí)際生產(chǎn)中的實(shí)用性，以及隨著實(shí)際應(yīng)用經(jīng)驗(yàn)的不斷累計(jì)和與其他調(diào)度方法的廣泛交叉，其研究的深度和廣度將不斷提升。進(jìn)一步的研究工作可從以下幾個(gè)方面展開：

a.繼續(xù)研究和分析已有啟發(fā)式規(guī)則的性能。

從啟發(fā)式規(guī)則性能評價(jià)指標(biāo)、生產(chǎn)環(huán)境、資源和工單加工特點(diǎn)、約束條件等角度，全面分析各啟發(fā)式規(guī)則的更詳細(xì)性能，逐步構(gòu)建比較系統(tǒng)的啟發(fā)式規(guī)則性能分析庫，為啟發(fā)式規(guī)則的更好應(yīng)用和新啟發(fā)式規(guī)則的提出打下基礎(chǔ)。

b.基于實(shí)際生產(chǎn)經(jīng)驗(yàn)提出新的啟發(fā)式規(guī)則。

大部分啟發(fā)式規(guī)則都是對生產(chǎn)實(shí)踐的抽象和總結(jié)，是專家經(jīng)驗(yàn)的累計(jì)，來源于實(shí)踐又服務(wù)于實(shí)踐。根據(jù)對已有啟發(fā)式規(guī)則的分析，并結(jié)合實(shí)際生產(chǎn)需要，改進(jìn)和提出新的啟發(fā)式規(guī)則，不斷豐富啟發(fā)式規(guī)則庫。

c.建立基于啟發(fā)式規(guī)則庫的專家系統(tǒng)。

啟發(fā)式規(guī)則是人類解決生產(chǎn)調(diào)度問題的結(jié)晶，而這些規(guī)則的有機(jī)組合將為專家系統(tǒng)的構(gòu)建提供基礎(chǔ)，因此建立一個(gè)基于啟發(fā)式規(guī)則庫的智能專家系統(tǒng)對于解決生產(chǎn)調(diào)度問題具有重要意義。

d.與其他調(diào)度方法結(jié)合解決生產(chǎn)調(diào)度問題的研究。

啟發(fā)式規(guī)則具有操作簡單、求解速度快且解的質(zhì)量不太差等優(yōu)點(diǎn)，能夠較好地彌補(bǔ)其他調(diào)度算法搜索盲目性和非法性等缺點(diǎn)，提高搜索的效率和質(zhì)量。研究和分析各種啟發(fā)式規(guī)則與其他調(diào)度算法的結(jié)合效果，對于改進(jìn)這些算法性能以及實(shí)際應(yīng)用具有重要指導(dǎo)作用。

[1] GIFFLER B, THOMPSON G L. Algorithms for solving production scheduling problems[J]. Operations Research, 1960,8(4):487-503.

[2] DAVID W S. A survey of approaches to the job shop scheduling problem[C]//System Theory. IEEE Proceedings of the Twenty-Eighth Southeastern Symposium on System Theory, March 31—April 2, 1996, Louisiana State University, Baton Rouge, Louisiana. California:IEEE Computer Society, 1996:396-400.

[3] 熊銳，吳澄. 車間生產(chǎn)調(diào)度問題的技術(shù)現(xiàn)狀與發(fā)展趨勢[J]. 清華大學(xué)學(xué)報(bào):自然科學(xué)版，1998，38(10):55-60.

[4] 徐俊剛，戴國忠，王宏安. 生產(chǎn)調(diào)度理論和方法研究綜述[J]. 計(jì)算機(jī)研究與發(fā)展，2004，41(2):257-267.

[5] 金鋒，吳澄. 大規(guī)模生產(chǎn)調(diào)度問題的研究現(xiàn)狀與展望[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2006，12(2):161-168.

[6] 王萬良，吳啟迪. 生產(chǎn)調(diào)度智能算法及其應(yīng)用[M]. 北京:科學(xué)出版社，2007.

[7] PINEDO M L. Scheduling: Theory, Algorithms, and Systems[M]. Berlin, Germany: Springer Verlag, 2008.

[8] BAKER C T, DZIELINSKI B P. Simulation of a simplified job shop[J]. Management Science, 1960, 6(3): 311-323.

[9] WILLIAM S, GERE J R. Heuristics in job shop scheduling[J]. Management Science, 1966, 13(3): 167-190.

[10] DAYJ E, HOTTENSTEIN M P. Review of sequencing research[J]. Naval Research Logistics Quarterly, 1970, 17: 11-39.

[11] JONES C H. An economic evaluation of job shop dispatching rules[J]. Management Science, 1973, 20(3):293-307.

[12] HERSHAUER J C, EBERT R J. Search and simulation selection of a job-shop sequencing rule[J]. Management Science, 1975, 21(7):833-843.

[13] PANWALKAR S S, ISKANDER W. A survey of scheduling rules[J]. Operations Research, 1977, 25(1):45-46.

[14] HAUPT R. A survey of priority rule-based scheduling[J]. OR Spektrum, 1989, 11: 3-16.

[15] PHILIPOOM P R, FRY T D. The robustness of selected job-shop dispatching rules with respect to load balance and work-flow structure[J]. The Journal of the Operational Research Society, 1990, 41(10):897-906.

[16] HOLTHAUS O, RAJENDRAN C. Efficient dispatching rules for scheduling in a job shop[J]. International Joural of Production Economics, 1997, 48:87-105.

[17] MOHANASUNDARAM K M, NATARAJAN K, VISWANATHKUMAR G, RADHAKRISHNAN P, RAJENDRAN C. Scheduling rules for dynamic shops that manufacture multi-level jobs[J]. Computers & Industrial Engineering, 2002, 44:119-131.

[18] CANBOLAT Y B, GUNDOGAR E. Fuzzy priority rule for job shop scheduling[J]. Journal of Intelligent Manufacturing, 2004, 15:527-533.

[19] NATARAJAN K, MOHANASUNDARAM K M, SHOBAN B B, et al. Performance evaluation of pirority dispatching rules in multi-level assembly job shops with jobs having weights for flowtime and tardiness[J]. International Journal of Advanced Manufacturing Technology, 2007, 31:751-761.

[20] 王家廞. 生產(chǎn)調(diào)度的一種啟發(fā)式規(guī)則[J]. 清華大學(xué)學(xué)報(bào)：自然科學(xué)版，1995，35(5):27-32.

[21] REN Yanpin, ZHANG Zuo, WU Qiufeng. An analysis of scheduling rules[C]//Intelligent Processing Systems. IEEE International Conference on Intelligent Processing Systems, Beijing:International Academic Publishers,1997:1351-1355.

[22] 曾相戈. 一種雙目標(biāo)帶約束工件成類的平行機(jī)器調(diào)度啟發(fā)式規(guī)則[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識，2006，36(4):144-150.

[23] 黃竹君. 基于啟發(fā)式調(diào)度規(guī)則的車間作業(yè)計(jì)劃算法及仿真研究[D]. 武漢：武漢科技大學(xué)，2009.

[24] 舒海生，趙剛，趙丹. FMS混合調(diào)度中的兩種啟發(fā)式規(guī)則[J]. 制造技術(shù)與機(jī)床，2010(7):29-32.

[25] 李巖，吳智銘. 基于GA和機(jī)器學(xué)習(xí)的啟發(fā)式規(guī)則調(diào)度方法[J]. 控制與決策，1999(14):561-564.

[26] 戰(zhàn)德臣，陳偉，王忠杰. 基于啟發(fā)式規(guī)則的混合遺傳算法及其在生產(chǎn)計(jì)劃優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用，2003，(8):215-218.

[27] 代勇，付宜利，馬玉林. 與啟發(fā)式規(guī)則相結(jié)合的遺傳算法在車間調(diào)度問題中的研究[J]. 現(xiàn)代制造工程，2003(3):48-51.

[28] 王也仿，楊建國. 基于規(guī)則與生物免疫機(jī)理的多目標(biāo)作業(yè)調(diào)度方法應(yīng)用研究[J]. 東華大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，31(4):52-56.

[29] 牛群，顧幸生. 基于啟發(fā)式規(guī)則的新型進(jìn)化算法在流水車間調(diào)度中的應(yīng)用[J]. 華東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，32(12):1472-1477.

[30] 肖志嬌，常會(huì)友，衣楊. 啟發(fā)式規(guī)則與GA結(jié)合的優(yōu)化方法求解工作流動(dòng)態(tài)調(diào)度優(yōu)化問題[J]. 計(jì)算機(jī)科學(xué)，2007, 34(2):157-160.

[31] HE Yaohua, HUI Chiwai. A rule-based genetic algorithm for the scheduling of single-stage multi-product batch plants with parallel units[J]. Computers & Chemical Engineering, 2008, 32:3067-3083.

[32] GRAHAM R L, LAWLER E L, LENSTRA J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annal of Discrete Mathematics, 1979, 5:287-326.

[33] 左燕. 大規(guī)模復(fù)雜生產(chǎn)調(diào)度問題瓶頸分解方法研究[D]. 上海：上海交通大學(xué)，2007.

[34] HOLLOWAY C A, NELSON R T. Job shop scheduling with due dates and overtime capability[J]. Management Science, 1974, 21(1):68-78.

[35] BAKER K R. Sequencing rules and due-date assignments in a job shop[J]. Management Science, 1984, 30(9):1093-1104.

[36] VEPSALAINEN A P J, MORTON T E. Priority rules for job shops with weighted tardiness costs[J]. Management Science, 1987, 33(8):1035-1047.

[37] THOMAS R R, GARY S. A comparison of order-release and dispatch rules for the dynamic weighted early/tardy problem[J]. Production and Operations Management, 1993, 2(3):221-238.

[38] SHAUKAT A B, GLORIA E Wheeler. Comparison of scheduling rules in a flow shop with multiple processors: a simulation[J]. Society for Modeling and Simulation International, 1998, 71(5):302-311.

[39] STRUSEVICH V A. A greedy open shop heuristic with job priorities[J]. Annals of Operations Research, 1998, 83:253-270.

[40] 郝文育，李亞白，王寧生. 一種啟發(fā)式車間作業(yè)調(diào)度算法的研究與應(yīng)用[J]. 機(jī)械科學(xué)與技術(shù)，2005，24(7):861-864.

[41] 李崢峰，喻道遠(yuǎn)，楊超英，等. 基于啟發(fā)規(guī)則的雙向沖壓生產(chǎn)線調(diào)度研究[J]. 華中科技大學(xué)學(xué)報(bào)：自然科學(xué)報(bào)，2009，37(6):60-63.

[42] NEUMANN K, SCHNEIDER W G. Heuristic algorithms for job-shop scheduling problems with stochastic precedence constraints[J]. Annals of Operations Research, 1999, 92:45-63.

[43] CHRISTIAN A, PIERRE L, Pierre-Dimitri A. Schedule generation schemes for the job-shop problem with sequence-dependent setup times: dominance properties and computational analysis[J]. Annals of Operations Research, 2005, 138(1):21-52.

[44] 李豆豆，邵世煌，齊金鵬. 生存遷移算法[J]. 系統(tǒng)仿真學(xué)報(bào)，2008(8):2034-2038.

AnOverviewonHeuristicRulesfortheProductionSchedulingProblem

LI Doudou

(Jiangsu Posts & Telecommunications Planning And Designing Institute Co., Ltd., Jiangsu Nanjing, 210019, China)

Scheduling rules are very simple and quite effective to the solution of scheduling problems, especially very complex ones. They have been intensively investigated over the last 50 years by means of extensive and rigorous simulation study, and widely used in other scheduling algorithms to get better solution. It briefly introduces the survey of scheduling rules in the literature, and discusses a summary on classification, characterization, evaluation, robustness and new presented scheduling rules. And finally it presents the framework of heuristic rules applied in intelligent optimization scheduling algorithm, describes the future research and application on scheduling rules.

Production Scheduling; Scheduling Rules; Dispatching Rules; Intelligent Optimization Algorithm; Expert System

10.3969/j.issn.2095-509X.2014.02.011

2013-11-21

李豆豆(1983—),男,江蘇徐州人,江蘇省郵電規(guī)劃設(shè)計(jì)院有限責(zé)任公司，碩士,主要研究領(lǐng)域?yàn)樯a(chǎn)調(diào)度、空中交通、城市交通、復(fù)雜網(wǎng)絡(luò)、智能優(yōu)化算法等。

TP18

A

2095-509X(2014)02-0051-06