可轉(zhuǎn)包與資源定時(shí)釋放排序問(wèn)題的研究.pdf

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

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