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

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

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

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