預防性維護下的混合型平行機調度問題研究.pdf

1、傳統(tǒng)的調度研究假設機器可以一直被使用，直到加工完所有需要加工的工件.然而，在現(xiàn)實生產活動中，往往需要對機器進行預防性的維護.常見的維護類型有:單次維護、周期維護和工具更換維護.
　　本文研究了預防性維護下一類混合型平行機調度問題:有n個工件需要加工，有兩臺平行機可供使用，其中一臺需要工具更換維護，另一臺需要周期維護，目標是確定每次工具更換維護的開始時刻和每個工件所對應的機器及其開始加工時刻使得這n個工件的時間表長（即最后完工的工件

2、的完工時刻）最小.本文的主要工作如下.
　　(1)分析了該問題的計算復雜性和不可逼近性.證明了該問題是強NP-難的并且不存在最壞情況界小于2的多項式時間算法除非P=NP.
　　(2)為求解中小規(guī)模的調度實例，基于“把維護看作工件”、“機器拼接”和“工件與加工位置一一對應”的思想給出了兩個數(shù)學規(guī)劃模型，基于“裝箱問題”的思想給出了另外兩個數(shù)學規(guī)劃模型，并編程實現(xiàn)了上述四個模型.
　　(3)為求解大規(guī)模的調度實例，基于“工

3、件完成時間優(yōu)先分配機制”，“機器完成時間優(yōu)先分配機制”，經典的“LPT規(guī)則”和“LS規(guī)則”設計了四個啟發(fā)式算法.通過對上述四個算法所生成的調度方案的研究，提出了對上述算法得到的調度方案進行“后優(yōu)化”想法并以此為基礎設計了四個新的算法.注意到存在實例表明沒有一個算法占絕對優(yōu)勢，于是把上述八個算法的輸出結果中最好的一個做為最終輸出，這樣就得到了第九個啟發(fā)式算法.
　　(4)從理論上對上述九個算法進行了最壞情況分析.證明了當最后一個非空

4、維護間隔中至少有兩個工件時，上述九個算法的最壞情況界均為2.
　　(5)通過數(shù)值實驗對上述九個算法進行了平均誤差分析和最大誤差分析.為了避免使用數(shù)學規(guī)劃模型求解大規(guī)模的調度實例，根據機器的特點設計了“逐次半毫升水量轉移算法”來求最優(yōu)時間表長的一個下界，根據工件加工的特點得到了最優(yōu)時間表長的另外一個下界.取這兩個下界中較大者做為數(shù)值實驗中的比較對象，通過編程實現(xiàn)了上述九個算法和下界，給出了工件規(guī)模為20，200和2000下各36組參