繼列批機(jī)器上生產(chǎn)和運(yùn)輸集成排序研究.pdf

1、排序論是運(yùn)籌學(xué)中最有活力的領(lǐng)域之一，大量不同機(jī)器環(huán)境下的排序模型已經(jīng)被學(xué)者們廣泛研究。本文我們是在繼列批機(jī)器環(huán)境下研究工件的加工和運(yùn)輸之間的集成排序問(wèn)題。為了節(jié)約時(shí)間和(或)費(fèi)用，工件生產(chǎn)和工件運(yùn)輸之間的協(xié)調(diào)已經(jīng)在文獻(xiàn)中廣泛研究。文獻(xiàn)中通常有兩種傳統(tǒng)的方法用來(lái)運(yùn)輸工件。第一種方法總是單獨(dú)地運(yùn)輸工件且在工件加工完成之后立即運(yùn)輸給顧客。此時(shí)，通常假設(shè)有足夠多數(shù)量的運(yùn)輸車(chē)。第二種方法是把加工完成的工件成批地運(yùn)輸給顧客。顯然，第二種方法比第一種

2、方法需要更少的車(chē)輛和更低的運(yùn)輸費(fèi)用。本文我們采用第二種方法來(lái)運(yùn)輸所有的工件。此外，在工件的實(shí)際加工和運(yùn)輸過(guò)程中，加工機(jī)器和運(yùn)輸車(chē)輛可能會(huì)存在容量限制。
　　Lu等人[26]引入了“劈開(kāi)”的概念。在“劈開(kāi)”的假設(shè)下，一個(gè)工件Jj可以被劈開(kāi)成兩部分J'j和 J"j，且被劈開(kāi)的兩部分J'j和J"j在加工和運(yùn)輸過(guò)程中可以被看作是兩個(gè)獨(dú)立工件。
　　本文分兩部分研究繼列批機(jī)器上帶有容量限制的工件加工和運(yùn)輸之間的集成排序問(wèn)題。第一部分研

3、宄只有運(yùn)輸車(chē)輛存在容量限制且工件只在運(yùn)輸過(guò)程中允許“劈開(kāi)”的排序問(wèn)題.第二部分研宄加工和運(yùn)輸過(guò)程中均有容量限制的排序問(wèn)題。
　　在第二章，我們研宄了只有運(yùn)輸車(chē)輛存在容量限制且工件只在運(yùn)輸過(guò)程中允許“劈開(kāi)”的排序問(wèn)題：
　　針對(duì)運(yùn)輸車(chē)輛存在一般容量限制且工件只在運(yùn)輸過(guò)程中允許“劈開(kāi)”的情形，我們給出了一個(gè)4/3-近似算法，這改進(jìn)了 Lu等人[26]的3/2-近似算法。
　　對(duì)工件尺寸一致的特殊情形，我們給出了多項(xiàng)式時(shí)間算