若干新型混合車間作業(yè)排序問(wèn)題研究.pdf

1、排序是運(yùn)籌學(xué)組合優(yōu)化領(lǐng)域中研究最為活躍的分支之一.近年來(lái)，隨著理論研究及實(shí)際的需要，產(chǎn)出了很多新型排序問(wèn)題.本文主要研究三類新型混合車間作業(yè)排序問(wèn)題，并且這些混合問(wèn)題都可以看成是不同機(jī)器環(huán)境意義下的混合.研究的核心是近似算法的設(shè)計(jì)和最壞情況界的分析.全文共分為四章.
　　第一章首先介紹了排序問(wèn)題、計(jì)算復(fù)雜性和算法等的基本概念和理論，接著論述了與本文相關(guān)的若干排序問(wèn)題的相關(guān)研究成果.
　　第二章研究了一類源于服裝生產(chǎn)流水線等領(lǐng)

2、域的新型混合車間排序問(wèn)題.在該問(wèn)題中，工件的有些工序之間的加工順序是確定的且每個(gè)工件都相同，而其他工序的加工順序則是不確定的，可以看成是若干臺(tái)流水作業(yè)機(jī)器與開(kāi)放作業(yè)機(jī)器的混合模型，目標(biāo)函數(shù)是極小化最大完工時(shí)間.首先，證明了該問(wèn)題是一般NP-困難的.其次，對(duì)于兩臺(tái)流水作業(yè)機(jī)器和一臺(tái)開(kāi)放作業(yè)機(jī)器的混合情況，給出了問(wèn)題的一個(gè)3/2-近似算法，且說(shuō)明界是緊的.最后，將問(wèn)題推廣，考慮兩臺(tái)流水作業(yè)機(jī)器與任意臺(tái)平行機(jī)的混合模型，給出了問(wèn)題的一個(gè)2-近

3、似算法，并同樣說(shuō)明界是緊的.
　　第三章研究了一類開(kāi)放作業(yè)環(huán)境下的帶運(yùn)輸排序問(wèn)題.考慮在兩臺(tái)開(kāi)放作業(yè)的機(jī)器環(huán)境下，工件加工完后需要由唯一的一輛運(yùn)輸工具運(yùn)輸?shù)筋櫩吞?，運(yùn)輸工具有容量限制，每個(gè)工件占用的運(yùn)輸工具的空間也不同（工件尺寸不同），目標(biāo)是極小化最后完工工件運(yùn)輸?shù)筋櫩吞幫瑫r(shí)運(yùn)輸工具返回機(jī)器的時(shí)間.對(duì)于該問(wèn)題的一般情況，給出了問(wèn)題的一個(gè)2-近似算法，且說(shuō)明界是緊的.對(duì)于運(yùn)輸工具每次只能運(yùn)輸一個(gè)工件的情況，給出了問(wèn)題的一個(gè)改進(jìn)的3/