關(guān)于兩類排序模型的若干結(jié)果.pdf

1、排序問題是指在一定的約束條件下考慮如何對工件和機器分配時間資源,從而使一個或多個目標達到最優(yōu)。本文中主要研究了兩類排序模型:
　　(1)帶有分批費用的單機平行分批排序問題;
　　(2)具有相同工期的單機最小化加權(quán)總誤工問題。
　　(1)帶有分批費用的單機平行分批排序問題我們研究的問題是在單機平行分批排序中將通常的正則目標函數(shù)加入分批費用。模型可以描述如下:假設(shè)有n個工件J1,J2,…,Jn,一臺可以同時至多加工b個工件

2、的批處理機。每個工件Jj具有加工時間pj。假設(shè)工件和批處理機都在零時刻到達。工件被成批地進行加工,并且一旦開始加工就不允許中斷。每批的加工時間等于該批中工件的最大加工時間。目標函數(shù)為通常的正則函數(shù)與分批費用之和。用f表示一般的正則函數(shù),V表示分批所產(chǎn)生的總的分批費用。以下假定每分一批產(chǎn)生的分批費用為v。若共分了m批,那么總的分批費用V=mv。我們的問題可以簡記為1|p-batch,b=∞(b

3、分批費用的不同目標函數(shù)的模型分別給出了其最優(yōu)解的算法。
　　(2)具有相同工期的單機最小化加權(quán)總誤工問題盡管單機最小化加權(quán)總誤工問題經(jīng)常在實際中遇到,但由于對工期為任意值的研究比較困難,因此有關(guān)結(jié)果在文獻中出現(xiàn)的卻并不是很多。近來人們研究的興趣越來越多地放在工期取特殊值的模型。例如,具有相同工期dj=d,工期等量松弛(SLK)dj=pj+q,其中q為給定的常數(shù),以及更一般情形工時加等待工期(PPW)dj=αpj+q,其中α、q都為

4、給定的常數(shù)。還有一些學(xué)者則關(guān)注了在其他參數(shù)上進行特殊限制的情形,如問題1|wj=1|∑wjTj,1|wj=kpj|∑wjTj,1|pj=p|∑wjTj在文獻中都有所研究。我們研究的問題1|dj=d|∑wjTj已知是一般意義下的NP-困難問題。Lawler和Moore對該問題給出了一個擬多項式時間算法。而問題1||∑wjTj是強NP-困難的。Cheng等人給出了此問題的O(n2)時間的近似算法。我們把該算法得到的目標值作為問題1|dj=d