一類新型混合shop排序問(wèn)題研究.pdf

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

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

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