可轉包與資源定時釋放排序問題的研究.pdf

1、排序問題作為組合優(yōu)化問題之一，是許多工廠加工及車間調(diào)度中產(chǎn)生的數(shù)學模型。本文研究的是可轉包加工和資源定時投放的問題：可轉包排序問題，即工件的加工可分為本地加工和轉包加工兩個階段，其中本地加工為把一部分工件放在本地車間加工，會產(chǎn)生一個最大完工時間總和；而轉包加工為把剩余的工件轉包給外包商加工，會產(chǎn)生一個轉包總費用，問題的目標為極小化最大完工時間總與轉包總費用之和。而資源定時投放問題，即將一批待加工的工件放在單臺機上加工，工件的加工需要消耗

2、不可再生的資源，該資源在此單機上有兩個資源投放時刻，目標為極小化工件的總完工時間。全文共分四章描述。
　　本研究分為四個部分：第一章對于近似算法、最壞情況界、計算復雜性等排序領域的經(jīng)典理論進行了羅列，并介紹了其他一些學者的研究結果。第二章介紹了兩臺平行機排序，且工件可轉包加工的問題，其中又分為可轉包兩臺機流水作業(yè)排序、可轉包兩臺機有序化流水作業(yè)排序和可轉包兩臺機自由作業(yè)排序，并分別給出近似算法即最壞情況界分別為2、3/2和3/2。