帶有公共交貨窗口指派的單機(jī)排序問題.pdf

1、II碩士學(xué)位論文 碩士學(xué)位論文 運(yùn)籌學(xué)與控制論 運(yùn)籌學(xué)與控制論 王爽 王爽 曲阜師范大學(xué) 曲阜師范大學(xué)摘要I摘 要隨著 just-in-time 系統(tǒng)的廣泛應(yīng)用, 關(guān)于交貨期指派的排序問題已成為一個(gè)非?；钴S的研究領(lǐng)域, 并且已經(jīng)擴(kuò)展到對(duì)交貨窗口指派的研究. 在本文中我們研究的公共交貨窗口都是待定的, 即窗口的開始時(shí)間和窗口尺寸大小(窗口的時(shí)間段長(zhǎng)短)都是變量. 工件在零時(shí)刻到達(dá), 工件生產(chǎn)時(shí)沒有優(yōu)先權(quán), 機(jī)器一次只能加工一個(gè)工件, 完工

2、的工件被運(yùn)輸?shù)娇蛻? 每次的運(yùn)輸費(fèi)用都是固定不變的. 我們的目標(biāo)是確定加工工件的生產(chǎn)序,公共交貨窗口的開始時(shí)間及交貨窗口的尺寸等, 來極小化總的費(fèi)用, 總費(fèi)用包含提前時(shí)間懲罰費(fèi)用, 工件延誤費(fèi)用, 運(yùn)輸費(fèi)用以及確定公共交貨窗口開始時(shí)間和尺寸大小應(yīng)付的費(fèi)用等. 對(duì)此, 許多專家學(xué)者都給出了非常有效的多項(xiàng)式時(shí)間算法.但是我們還考慮到, 一方面, 在現(xiàn)實(shí)中制造商并不是接收所有的訂單, 當(dāng)加工一個(gè)訂單花費(fèi)時(shí)間長(zhǎng)且?guī)砝麧?rùn)很少的時(shí)候, 制造商會(huì)拒

3、絕該訂單, 但是會(huì)給予客戶相應(yīng)的補(bǔ)償; 另一方面, 機(jī)器是具有學(xué)習(xí)效應(yīng)的, 比方說工人剛接觸某項(xiàng)工作時(shí), 操作比較生疏, 效率較低, 但是由于工人在工作過程中技能的不斷提升, 效率就會(huì)逐漸提高. 所以我們主要考慮這兩個(gè)方面, 來研究不同的問題.本文包含的三個(gè)問題:（1）帶有學(xué)習(xí)效應(yīng)的公共交貨窗口指派的單機(jī)排序問題考慮帶有公共交貨窗口指派的單機(jī)排序問題, 我們需要指派一個(gè)合適的交貨窗口,并支付相應(yīng)的費(fèi)用, 加工所有的工件, 當(dāng)工件早于或晚

4、于窗口完工, 要支付相應(yīng)的提前費(fèi)用或延誤費(fèi)用．但是我們考慮到, 工件的實(shí)際加工時(shí)間是一個(gè)與加工位置有關(guān)的函數(shù),工件 j J 正常的加工時(shí)間是 j p , 在一個(gè)確定的生產(chǎn)序 ? ? 1 2 , , , n J J J ? ? ? 中, 工件 j J 在整個(gè)生產(chǎn)序中是第 r 個(gè)被加工工件, 則工件 j J 實(shí)際加工時(shí)間就是r aj j p p r ? , 其中a是學(xué)習(xí)因子? ? 0 a ? ．目標(biāo)是確定交貨窗口, 生產(chǎn)序, 來極小化總費(fèi)用

5、, 其包含總提前費(fèi)用, 總延誤費(fèi)用, 窗口開始與尺寸費(fèi)用. 最后我們給出了多項(xiàng)式時(shí)間算法.（2）帶有公共交貨窗口指派的工件可拒絕的單機(jī)排序問題考慮了帶有公共交貨窗口指派的單機(jī)排序問題, 交貨窗口的開始時(shí)間和尺寸大小都是待定的, 并且產(chǎn)生指派費(fèi)用. 工件早于或晚于窗口完工, 要支付相應(yīng)的提前費(fèi)用或延誤費(fèi)用. 由于機(jī)器的生產(chǎn)能力有限, 工件可以被拒絕, 若工件被拒絕, 則產(chǎn)生只與自身有關(guān)的拒絕費(fèi)用. 工件單獨(dú)配送, 運(yùn)輸費(fèi)用固定. 目標(biāo)是確