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

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

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

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

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