預(yù)防性維護(hù)下的混合型平行機(jī)調(diào)度問(wèn)題研究.pdf

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

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

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

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