一種解決搶占式作業(yè)車間調(diào)度問(wèn)題的基于約束控制規(guī)則的啟發(fā)式算法

CLAUDE LE PAPE
Bouygues, Direction des Technologies Nouvelles, 1, av. E. Freyssinet, F-78061 Saint-Quentin-en-Yvelines
電子郵箱：clp@challenger.bouygues.fr
摘要
近幾年來(lái)，約束規(guī)劃已經(jīng)被廣泛運(yùn)用于解決各種學(xué)科以及工業(yè)非搶占式調(diào)度問(wèn)題，舉例來(lái)說(shuō)：優(yōu)先問(wèn)題即：活動(dòng)不能被中斷的問(wèn)題。相比而言，運(yùn)籌學(xué)和人工智能領(lǐng)域幾乎都沒(méi)有注意到搶占式調(diào)度問(wèn)題。由于一些特殊應(yīng)用需求的激發(fā)，我們從事一個(gè)關(guān)于解決搶占式調(diào)度問(wèn)題的約束規(guī)劃技術(shù)適應(yīng)性的研究。本文將介紹那些我們推廣的算法和那些我們得到的關(guān)于搶占式的各種有名的“作業(yè)車間調(diào)度問(wèn)題”的研究結(jié)果。相比較文獻(xiàn)中使用的兩種眾所周知的連續(xù)作業(yè)車間調(diào)度實(shí)例，十種啟發(fā)式研究戰(zhàn)略結(jié)合兩種不同約束傳播技術(shù)都表明：最好的結(jié)合基于“極限差異研究”和“邊界發(fā)現(xiàn)”技術(shù)，已經(jīng)顯示出能為優(yōu)化車間調(diào)度問(wèn)題提供很好的解決方案。以10項(xiàng)作業(yè)和10臺(tái)機(jī)器（100個(gè)活動(dòng)）為例，一個(gè)離最優(yōu)化解決方案相對(duì)距離0.32%的平均值可以在5分鐘內(nèi)達(dá)到。

關(guān)鍵字：搶占式調(diào)度 作業(yè)車間調(diào)度 約束規(guī)劃 約束傳播 資源約束 時(shí)間表 臨界發(fā)現(xiàn) 極限差異研究

1．緒論
廣泛的說(shuō)，約束規(guī)劃可以被定義為基于以下3種規(guī)則的規(guī)劃方法：
 在一個(gè)基于約束的規(guī)劃中，待解決問(wèn)題已經(jīng)以參數(shù)和參數(shù)約束的形式被明確的表示出來(lái)，分離出來(lái)。這個(gè)分離保證待解決（問(wèn)題）被清晰定義。在很多案例中,當(dāng)相應(yīng)的有待的解決問(wèn)題發(fā)生變化時(shí)，它被簡(jiǎn)化為一個(gè)約束規(guī)劃應(yīng)用的修訂或者擴(kuò)展，舉例來(lái)說(shuō)，一個(gè)制造車間的新機(jī)器取代舊機(jī)器可能導(dǎo)致新的約束的引入和舊的約束的移出；但是，在一些案例中，同樣的解決問(wèn)題的算法將繼續(xù)應(yīng)用，以一個(gè)不同問(wèn)題的定義作為輸入。
 給定一個(gè)待解決的基于約束定義的問(wèn)題和一系列結(jié)果，將它們轉(zhuǎn)化為約束：一個(gè)表示“約束傳播”的純粹動(dòng)推論過(guò)程已經(jīng)被用來(lái)傳播約束推論。每次當(dāng)一個(gè)新的