一種解決搶占式作業(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)被廣泛運用于解決各種學科以及工業(yè)非搶占式調(diào)度問題，舉例來說：優(yōu)先問題即：活動不能被中斷的問題。相比而言，運籌學和人工智能領域幾乎都沒有注意到搶占式調(diào)度問題。由于一些特殊應用需求的激發(fā)，我們從事一個關于解決搶占式調(diào)度問題的約束規(guī)劃技術適應性的研究。本文將介紹那些我們推廣的算法和那些我們得到的關于搶占式的各種有名的“作業(yè)車間調(diào)度問題”的研究結果。相比較文獻中使用的兩種眾所周知的連續(xù)作業(yè)車間調(diào)度實例，十種啟發(fā)式研究戰(zhàn)略結合兩種不同約束傳播技術都表明：最好的結合基于“極限差異研究”和“邊界發(fā)現(xiàn)”技術，已經(jīng)顯示出能為優(yōu)化車間調(diào)度問題提供很好的解決方案。以10項作業(yè)和10臺機器（100個活動）為例，一個離最優(yōu)化解決方案相對距離0.32%的平均值可以在5分鐘內(nèi)達到。

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

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