不相容工件族的平行批序的一些結(jié)果.pdf

1、排序就是在一定的約束條件下對(duì)工件和機(jī)器按時(shí)間進(jìn)行分配和安排加工次序,使一個(gè)或多個(gè)目標(biāo)達(dá)到最優(yōu).平行批排序是發(fā)展比較迅速的現(xiàn)代排序模型.工件分族排序則是平行批排序中的新概念.
　　本文主要對(duì)于同一族內(nèi)加工時(shí)間等長(zhǎng)的不相容工件族平行批排序進(jìn)行了研究,作了以下兩方面的工作:(1)同一族內(nèi)工件加工時(shí)間相同時(shí)不相容工件族的平行批加權(quán)總完工時(shí)間問(wèn)題;(2)同一族內(nèi)工件加工時(shí)間相同時(shí)不相容工件族的誤工總數(shù)問(wèn)題.平行批排序是指一臺(tái)機(jī)器可以同時(shí)加工

2、多個(gè)工件,每批包含的工件同時(shí)開(kāi)工且同時(shí)完工,批的加工時(shí)間是這批工件中加工時(shí)間的最大者.一旦一批工件開(kāi)始加工就不能被中斷,其他工件也不能加入該批.本文中研究的問(wèn)題可描述如下:有n個(gè)工件J1, J2,…,Jn,它們被分成m個(gè)不同的工件族F1,F2,…,Fm.不同族的工件是不能在同一批加工的.工件是成批被加工處理的.這里的一批是指工件的一個(gè)子集.這些批(子集)構(gòu)成了工件集的一個(gè)劃分.我們稱此排序模型為平行批排序問(wèn)題,記為這里f為ΣwjCj或Σ

3、Uj.
　　本文的主要結(jié)果如下:(1)同一族內(nèi)加工時(shí)間相同的不相容工件族的單機(jī)平行批加權(quán)總完工時(shí)間問(wèn)題.基于對(duì)平行批加權(quán)總完工時(shí)間問(wèn)題最優(yōu)解性質(zhì)的分析,我們提出了工件分批的最優(yōu)性質(zhì),對(duì)同一族內(nèi)加工時(shí)間相同的批容量有界情形和無(wú)界情形分別給出了最優(yōu)排序規(guī)則,當(dāng)工件有常數(shù)個(gè)到達(dá)時(shí)間時(shí),我們分別對(duì)批容量有界和無(wú)界情形提出了兩種啟發(fā)式算法,并給出其算法復(fù)雜性.(2)同一族內(nèi)加工時(shí)間相同的不相容工件族的誤工總數(shù)問(wèn)題.對(duì)r和d一致及p與d一致的