一類新型混合shop排序問題研究.pdf

1、本文主要研究了一類新型的混合shop排序問題，文章中將問題分為兩類，第一類是一類新型的混合flow shop排序問題，第二類是一類新型的混合openshop排序問題。目標函數(shù)是最小化機器最大完工時間。
　　 第一章介紹了排序問題，近似算法和計算復雜性以及競爭比分析的一些的基本概念。第二節(jié)主要介紹了P類，NP類的定義，以及NP—難，強NP—難的定義，并給出了NP—難，強NP—難的證明方法和步驟。第四節(jié)給出了混合shop排序問題的研

2、究成果。
　　 第二章研究第一類問題——一種新型的混合flow shop排序問題。研究了該類問題的兩種特殊情況F(O2，1)|| max和F(O2，O)||Cmax。首先證明了F(O2，1)|Cmax問題為強NP—難問題，從而得到F(O2，O2)|Cmax問題也是強NP—難問題。對于每個問題，都給出了多項式時間近似算法。最后討論了一般情況F(Om2，Om2)||Cmax，對于一般情況，在一個基于Qm||Cnmax問題的近似算法的

3、基礎上，給出了F(Om1，Om2)||Cmax問題的一個多項式時間近似算法，并分析了其競爭比與前者的競爭比的關系。
　　 第三章研究第二類問題——一種新型的混合open shop排序問題，研究了一種特殊情況O(F2，1)||Cmax問題和此類問題的一般情況O(Fm1，F(xiàn)m2)||Cmax。首先證明了O(F2，1)||Cmax問題為一般NP一難的，從而一般情況也是一般NP—難的，然后分別給出了特殊情況和一般情況的多項式時間近似算法