工件有優(yōu)先約束的分批排序問題.pdf

1、排序論作為運籌學的一個重要分支，有深刻的實際背景和廣闊的應用前景，一直受到國內(nèi)外學術(shù)界的重視.而其中的分批排序問題，因其明顯的實際意義，更是吸引了許多學者的關(guān)注. 本文研究了工件帶有優(yōu)先約束的單機分批排序問題，工件有優(yōu)先約束是指工件加工時必須按一定先后順序加工，一般的，若工件Ji與Jj有優(yōu)先序，即Ji＜Jj,，它表示Jj必須在Ji完工之后才能開始加工.這里的目標函數(shù)為極小化工件的最大完工時間即最后被加工工件的完成時間.論文共分三

2、部分： 第一部分(引言)主要介紹了排序的產(chǎn)生背景，發(fā)展及其相關(guān)的基礎(chǔ)知識.第二部分，我們討論了工件有不同的到達時間和平行鏈約束的分批排序問題，即問題1|chainas，B，rj|Gmax.平行鏈約束是指每一個工件至多有一個前驅(qū)工件和一個后繼工件，例如工件Ji，Jj和Jk滿足平行鏈約束Ji＜Jj＜Jk，意思是工件Ji是工件Jj的唯一的前驅(qū)而工件Jk是工件Jj的唯一的后繼，換句話說，工件Jj必須在工件Ji之后工件Jk之前加工.

3、 我們先對兩條平行鏈，工件有不同的到達時間，其中一條鏈上有n個工件，另外一條鏈上的工件數(shù)為常數(shù)K的情形給出了計算時間為O(nK)的多項式時間算法；接著考慮有m條鏈，其中一條鏈上包含n個工件，其余的m-1條鏈上的工件數(shù)總和∑mi=2ki為常數(shù)，對于所有工件在不同的時間到達時，我們給出了一個多項式算法，其計算次數(shù)為O(n∑mi=2ki). 同時，我們指出對于一般的正則目標函數(shù)，當有m條鏈，其中一條鏈上包含n個工件，其余的m-1條鏈

4、上的工件數(shù)總和為常數(shù)，且工件在不同的時間到達時，也是多項式時間內(nèi)可解的. 第三部分，我們研究了工件有優(yōu)先約束且尺寸不同的分批排序問題.工件尺寸是指工件的體積.當工件放進某一批加工時，我們既要考慮此工件的尺寸又要考慮工件之間的優(yōu)先約束.對于這類問題，目前很少有人涉及.我們考慮的情形是：加工時間相同但尺寸不同的工件之間有一定的優(yōu)先約束關(guān)系，在滿足優(yōu)先約束的條件下，將工件安排到單臺批處理機上加工，使目標函數(shù)值最大完工時間最小，即問題1

5、|B，sj,prec,rj=e+kjp,pj=p|Gmax其中kj=「rj/p」，e為常數(shù)，且0≤e≤p-1，p，rj，1≤j≤n為整數(shù). 本章先對工件尺寸相同的情況給出了計算次數(shù)為O(n2)的多項式最優(yōu)算法，而后在此基礎(chǔ)上對工件可拆分的情形提出最優(yōu)算法，再把拆分工件放進一批放在可行的位置加工，這樣，我們就得到了此問題的2-近似算法. 其中，文中提出的對于批量有限時工件到達時間的修正法和批量有限且工件有不同尺寸的工件到達