平行工件在線排序及一類三階段排序問(wèn)題研究.pdf

1、本文主要研究?jī)膳_(tái)平行機(jī)上平行工件的在線排序和一類三階段供應(yīng)鏈排序問(wèn)題。
　　 全文共四章。
　　 第一章介紹排序問(wèn)題的基本概念和相關(guān)知識(shí),并總結(jié)國(guó)內(nèi)外研究現(xiàn)狀及本文研究結(jié)果。
　　 第二章主要討論帶懲罰時(shí)間的兩臺(tái)平行機(jī)上平行工件的在線排序問(wèn)題。對(duì)于平行工件Jj,若放在單臺(tái)機(jī)上加工,其執(zhí)行時(shí)間為tj=pj;若安排在兩臺(tái)機(jī)上加工,則需要給一個(gè)懲罰時(shí)間cj,即此時(shí)工件的執(zhí)行時(shí)間為tj=pj/2+cj。目標(biāo)函數(shù)是極小化最

2、大完工時(shí)間。當(dāng)懲罰時(shí)間不同時(shí),給出競(jìng)爭(zhēng)比為1+α1的最優(yōu)算法(其中α1=(√5-1)/2);當(dāng)懲罰時(shí)間相同時(shí),分別給出了漸近性能比為3/2和絕對(duì)性能比為α2≈1.54的在線近似算法,α2為α32-2α22+2α2-22=0的根。
　　 第三章研究一類三階段供應(yīng)鏈排序問(wèn)題。儲(chǔ)存工件的倉(cāng)庫(kù)和工廠在不同的地點(diǎn),工件加工前需要從倉(cāng)庫(kù)運(yùn)到工廠,加工完后再運(yùn)回倉(cāng)庫(kù)。文中主要考慮兩種模型,第一種是兩輛有容量限制的同類型車和單臺(tái)機(jī);第二種是一輛