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

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

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

3、宄只有運輸車輛存在容量限制且工件只在運輸過程中允許“劈開”的排序問題.第二部分研宄加工和運輸過程中均有容量限制的排序問題。
　　在第二章，我們研宄了只有運輸車輛存在容量限制且工件只在運輸過程中允許“劈開”的排序問題：
　　針對運輸車輛存在一般容量限制且工件只在運輸過程中允許“劈開”的情形，我們給出了一個4/3-近似算法，這改進了 Lu等人[26]的3/2-近似算法。
　　對工件尺寸一致的特殊情形，我們給出了多項式時間算