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

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

0 引 言

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

1 問題描述

本文討論的問題描述如下:給定工件集N={1,2,…,n}和m臺無關(guān)機(jī)M={1,2,…,m}.工件j或者被接受并被安排到某臺機(jī)器上進(jìn)行不中斷的加工,或者被拒絕并支付拒絕費(fèi)用ej. 設(shè)A與R分別表示接受工件集和拒絕工件集. 為方便起見,安排在機(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)效率,我們可以對每臺機(jī)器執(zhí)行至多一次的退化維護(hù)活動,機(jī)器在維護(hù)時段不能加工任何工件. 根據(jù)文獻(xiàn) [2],假設(shè)機(jī)器i上退化維護(hù)活動 (MAi) 的維護(hù)時間Ti是其開始時刻的線性非減函數(shù),表示為Ti=ti+δit,其中ti>0是基本維護(hù)時間,δi>0為維護(hù)系數(shù),t為退化維護(hù)活動的開始時刻. 為方便起見,如果機(jī)器i上MAi在第ki個位置上的工件開始加工之前恰好執(zhí)行完成,那么稱機(jī)器i上MAi的位置為ki. 特別地,ki=1表示機(jī)器i在 0 時刻執(zhí)行MAi,ki=ni+1表示機(jī)器i不執(zhí)行MAi. 定義bij與aij分別表示工件j在機(jī)器i的退化維護(hù)活動之前與之后的加工時間,且0

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

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

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

2 預(yù)備知識

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

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

3 主要結(jié)論

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

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

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

情形1 維護(hù)活動MAi在 0 時刻開始執(zhí)行,即ki=1.

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

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

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

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

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

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

其中

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

因此,對于給定的工件分配向量P(n,m+1)=(n1,…,nm,nm+1)與維護(hù)活動的位置向量Q(n,m)=(k1,…,km),其中hi+1≤ki≤ni+1,i=1,2,…,m,將問題重新描述為下面的指派問題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,可以得到

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

其中

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

算法A

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