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

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

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

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