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

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

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

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