高 潔, 隋玉康, 鄒 娟, 孫安寧

(曲阜師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,273165,山東省曲阜市)

0 引 言

本文的結(jié)構(gòu)如下:第1節(jié)對(duì)研究的問(wèn)題進(jìn)行了描述;第2節(jié)給出相關(guān)的引理;第3節(jié)給出問(wèn)題的多項(xiàng)式時(shí)間算法;第4節(jié)對(duì)本文的研究進(jìn)行了總結(jié).

1 問(wèn)題描述

本文討論的問(wèn)題描述如下:給定工件集N={1,2,…,n}和m臺(tái)無(wú)關(guān)機(jī)M={1,2,…,m}.工件j或者被接受并被安排到某臺(tái)機(jī)器上進(jìn)行不中斷的加工,或者被拒絕并支付拒絕費(fèi)用ej. 設(shè)A與R分別表示接受工件集和拒絕工件集. 為方便起見(jiàn),安排在機(jī)器i上加工的工件集記為Ai,ni表示在機(jī)器i上加工的工件數(shù)量,i=1,2,…,m. 顯然,Ai可以為空集,|Ai|=ni,Ai∩Aj=?(i≠j)且A=A1∪A2∪…∪Am.

為了提高機(jī)器的生產(chǎn)效率,我們可以對(duì)每臺(tái)機(jī)器執(zhí)行至多一次的退化維護(hù)活動(dòng),機(jī)器在維護(hù)時(shí)段不能加工任何工件. 根據(jù)文獻(xiàn) [2],假設(shè)機(jī)器i上退化維護(hù)活動(dòng) (MAi) 的維護(hù)時(shí)間Ti是其開(kāi)始時(shí)刻的線性非減函數(shù),表示為T(mén)i=ti+δit,其中ti>0是基本維護(hù)時(shí)間,δi>0為維護(hù)系數(shù),t為退化維護(hù)活動(dòng)的開(kāi)始時(shí)刻. 為方便起見(jiàn),如果機(jī)器i上MAi在第ki個(gè)位置上的工件開(kāi)始加工之前恰好執(zhí)行完成,那么稱(chēng)機(jī)器i上MAi的位置為ki. 特別地,ki=1表示機(jī)器i在 0 時(shí)刻執(zhí)行MAi,ki=ni+1表示機(jī)器i不執(zhí)行MAi. 定義bij與aij分別表示工件j在機(jī)器i的退化維護(hù)活動(dòng)之前與之后的加工時(shí)間,且0

對(duì)于一個(gè)給定的排序,令Cij表示工件j在機(jī)器i上的完工時(shí)間,令D=(d1,d2,…,dm)表示公共交貨期向量,其中di表示機(jī)器i上工件集的公共交貨期.Eij=max{0,di-Cij}和Tij=max{0,Cij-di}分別表示工件j在機(jī)器i上的提前時(shí)間和延誤時(shí)間. 我們的目標(biāo)是尋找退化維護(hù)活動(dòng)的位置、接受工件的排序以及每臺(tái)機(jī)器上接受工件的公共交貨期,使得目標(biāo)函數(shù)

最小,其中α>0與β>0分別表示單位時(shí)間的提前懲罰和延誤懲罰. 依據(jù)傳統(tǒng)的三參數(shù)表示法[8],將本文研究的問(wèn)題表示為

其中,rej表示工件可拒絕,Ti=ti+δit表示機(jī)器i上維護(hù)活動(dòng)的維護(hù)時(shí)長(zhǎng),pij=(bij,aij)分別表示基礎(chǔ)加工時(shí)間和縮短加工時(shí)間.

2 預(yù)備知識(shí)

為了解決問(wèn)題(P),我們首先給出如下幾個(gè)重要的結(jié)論.

引理2.3[2]在單機(jī)環(huán)境下,在最優(yōu)排序中,維護(hù)活動(dòng)或者在0時(shí)刻執(zhí)行,或者在最優(yōu)公共交貨期d之后執(zhí)行.

3 主要結(jié)論

由引理 2.2 與引理 2.3,可以得到無(wú)關(guān)機(jī)環(huán)境下的兩個(gè)結(jié)論. 為了敘述的方便，令i[j]表示機(jī)器i上的第j個(gè)位置.

引理3.2在最優(yōu)排序中,機(jī)器i(1≤i≤m)上的退化維護(hù)活動(dòng)或者在0時(shí)刻執(zhí)行,或者在di時(shí)刻之后執(zhí)行.

為了分析出本文研究問(wèn)題的最優(yōu)排序,首先,根據(jù)維護(hù)活動(dòng)的不同位置,分別計(jì)算機(jī)器i上的總提前和延誤懲罰:

情形1 維護(hù)活動(dòng)MAi在 0 時(shí)刻開(kāi)始執(zhí)行,即ki=1.

情形2 維護(hù)活動(dòng)MAi在di時(shí)刻之后執(zhí)行,即hi+1≤ki≤ni.

情形3 不執(zhí)行維護(hù)活動(dòng)MAi,即ki=ni+1.

可以看到,對(duì)于情形2,若取ki=ni+1,則可以得到與情形3相同的表達(dá)式,故將這兩類(lèi)歸為一類(lèi). 因此,討論任意機(jī)器i上退化維護(hù)活動(dòng)的位置,只需要考慮ki=1與hi+1≤ki≤ni+1這兩種情形.

證明對(duì)于這個(gè)問(wèn)題,可以將其轉(zhuǎn)化為指派問(wèn)題(AP)求解. 對(duì)于任一給定的工件分配向量P(n,m+1)=(n1,…,nm,nm+1)與維護(hù)活動(dòng)的位置向量Q(n,m)=(k1,…,km). 由以上分析,可以將維護(hù)活動(dòng)的位置向量分為以下3類(lèi):(1)Q(n,m)=(1,…,1),即每臺(tái)機(jī)器均在0時(shí)刻執(zhí)行退化維護(hù)活動(dòng);(2)Q(n,m)=(k1,…,km),其中hi+1≤ki≤ni+1,i=1,2,…,m,即每臺(tái)機(jī)器均在di時(shí)刻之后執(zhí)行退化維護(hù)活動(dòng);(3)Q(n,m)=(1,…,1,kl+1,…,km),其中hi+1≤ki≤ni+1,i=l+1,l+2,…,m,即在機(jī)器i=1,…,l上,機(jī)器在 0 時(shí)刻執(zhí)行退化維護(hù)活動(dòng),在機(jī)器i=l+1,…,m上,機(jī)器在di時(shí)刻之后執(zhí)行退化維護(hù)活動(dòng). 令變量xijs=1表示工件j被安排到機(jī)器i的位置s,否則xijs=0;令wijs表示工件j被安排到機(jī)器i的位置s時(shí)的權(quán)重. 我們分別對(duì)Q(n,m)的3個(gè)分類(lèi)進(jìn)行分析. 我們將對(duì)應(yīng)于工件分配向量P(n,m+1)=(n1,…,nm,nm+1)與維護(hù)活動(dòng)的位置向量Q(n,m)=(k1,…,km)的指派問(wèn)題記為AP(n1,…,nm,nm+1,k1,…,km),并將對(duì)應(yīng)的目標(biāo)函數(shù)值記為Z(n1,…,nm,nm+1,k1,…,km),簡(jiǎn)記為Z.

(1)若Q(n,m)=(1,…,1),可以得到

因此,對(duì)于給定的工件分配向量P(n,m+1)=(n1,…,nm,nm+1)與維護(hù)活動(dòng)的位置向量Q(n,m)=(1,…,1),我們將問(wèn)題重新描述為下面的指派問(wèn)題AP(n1,…,nm,nm+1,1,…,1):

其中

(2)若Q(n,m)=(k1,…,km),其中hi+1≤ki≤ni+1,i=1,2,…,m,可以得到

因此,對(duì)于給定的工件分配向量P(n,m+1)=(n1,…,nm,nm+1)與維護(hù)活動(dòng)的位置向量Q(n,m)=(k1,…,km),其中hi+1≤ki≤ni+1,i=1,2,…,m,將問(wèn)題重新描述為下面的指派問(wèn)題AP(n1,…,nm,nm+1,k1,…,km):

其中

(3)若Q(n,m)=(1,…,1,kl+1,…,km),其中hi+1≤ki≤ni+1,i=l+1,l+2,…,m,可以得到

因此,對(duì)于給定的工件分配向量P(n,m+1)=(n1,…,nm,nm+1)與維護(hù)活動(dòng)的位置向量Q(n,m)=(1,…,1,kl+1,…,km),其中hi+1≤ki≤ni+1,i=l+1,…,m,將問(wèn)題重新描述為下面的指派問(wèn)題AP(n1,…,nm,nm+1,1,…,1,kl+1,…,km):

其中

結(jié)合定理1的證明,我們給出如下求解問(wèn)題(P)的算法.

算法A

步驟2 對(duì)于P(n,m+1)=(n1,…,nm,nm+1)與Q(n,m)=(k1,…,km),其中0≤ni≤n(i=1,…,m),0≤nm+1

4 結(jié) 論

本文研究了工件可拒絕與退化維護(hù)活動(dòng)的無(wú)關(guān)機(jī)排序問(wèn)題,目標(biāo)是尋求退化維護(hù)活動(dòng)的位置、接受工件的工件排序以及每臺(tái)機(jī)器上接受工件的公共交貨期,使得所有接受工件的總提前和延誤懲罰與所有拒絕工件的總拒絕成本之和達(dá)到最小. 為此,我們將機(jī)器上維護(hù)活動(dòng)的位置向量分為3類(lèi):(1)每臺(tái)機(jī)器均在 0 時(shí)刻執(zhí)行退化維護(hù)活動(dòng);(2) 每臺(tái)機(jī)器均在其公共交貨期di時(shí)刻之后執(zhí)行退化維護(hù)活動(dòng); (3) 部分機(jī)器在0時(shí)刻執(zhí)行退化維護(hù)活動(dòng),部分機(jī)器在其公共交貨期di時(shí)刻之后執(zhí)行退化維護(hù)活動(dòng). 根據(jù)這三種分類(lèi),分別得到3個(gè)指派問(wèn)題,并借助一些代數(shù)學(xué)知識(shí),得到該問(wèn)題的多項(xiàng)式時(shí)間算法,時(shí)間復(fù)雜度為O(n2m+3).