帶有安裝時(shí)間與維修活動(dòng)的單機(jī)排序問(wèn)題

趙玉芳, 葛秋利

(沈陽(yáng)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽(yáng) 110034)

0 引 言

生活中,帶有維修和交貨期窗口的問(wèn)題受到了廣泛的關(guān)注,具有重要的實(shí)際意義[1]。在某些情況下,在工件加工之前需要有安裝時(shí)間,在加工過(guò)程中通過(guò)維修活動(dòng)可以使機(jī)器的生產(chǎn)效率提高。Mor和Mosheiov[1]研究了帶有交貨期窗口和維修的單機(jī)排序問(wèn)題;Wang等[2]研究了帶有學(xué)習(xí)效應(yīng)、退化效應(yīng)和交貨期窗口的單機(jī)排序問(wèn)題;Cheng等[3]研究了維修時(shí)間與開(kāi)始時(shí)間相關(guān)的帶有退化效應(yīng)和交貨期窗口的單機(jī)排序問(wèn)題;Janiak等[4]總結(jié)了關(guān)于交貨期窗口的研究進(jìn)展;王吉波等[5]討論了同時(shí)具有學(xué)習(xí)和惡化效應(yīng)的不同工期指派問(wèn)題,并給出了多項(xiàng)式算法。

在帶有安裝時(shí)間的模型中,Koulamas和Kyparisis[6]提出了線性和非線性的安裝時(shí)間模型,討論了目標(biāo)函數(shù)分別為最大完工時(shí)間、總完工時(shí)間及總完工時(shí)間的絕對(duì)差之和的單機(jī)排序問(wèn)題,給出了計(jì)算復(fù)雜性都為O(nlogn)的多項(xiàng)式最優(yōu)算法;Kuo和Yang[7]研究了帶有安裝時(shí)間和學(xué)習(xí)效應(yīng)的單機(jī)排序問(wèn)題;Wang等[8]研究了帶有安裝時(shí)間和學(xué)習(xí)效應(yīng)與退化效應(yīng)的單機(jī)排序問(wèn)題;Huang等[9]討論了帶有安裝時(shí)間、與位置有關(guān)的學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)排序問(wèn)題;Lee[10]討論了帶有安裝時(shí)間與學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)排序問(wèn)題;關(guān)于帶有交貨期窗口和維修的問(wèn)題,Mosheiov和Oron[11]研究了帶有交貨期窗口的單機(jī)排序問(wèn)題,給出了計(jì)算復(fù)雜性為O(nlogn)多項(xiàng)式算法,對(duì)于加工時(shí)間與位置相關(guān)的帶有交貨期窗口的單機(jī)排序問(wèn)題,給出了計(jì)算復(fù)雜性為O(n3)多項(xiàng)式算法;Wu和Ji[12]對(duì)于加工時(shí)間分別具有退化效應(yīng)與學(xué)習(xí)效應(yīng)的含有交貨期窗口的單機(jī)排序問(wèn)題進(jìn)行了研究,給出了計(jì)算復(fù)雜性為O(n4)的多項(xiàng)式算法。

Zhao和Tang[13]研究了帶有安裝時(shí)間和交貨期窗口與退化效應(yīng)的單機(jī)排序問(wèn)題,給出了計(jì)算復(fù)雜性都為O(nlogn)的多項(xiàng)式算法;Zhu等[14]研究了帶有交貨期窗口和維修的單機(jī)排序問(wèn)題,其中維修存在資源且分為與位置相關(guān)和維修開(kāi)始時(shí)間相關(guān)2種情況,給出了復(fù)雜性為O(n4)的多項(xiàng)式算法。在實(shí)際問(wèn)題中,常常同時(shí)帶有安裝時(shí)間和交貨期窗口與維修活動(dòng),本文同時(shí)考慮了帶有上述情況的模型,并給出了在2種維修情況下的多項(xiàng)式最優(yōu)算法。

1 問(wèn)題描述

1=φ(0)≤φ(1)≤φ(2) ≤…≤φ(n-1)

用三參數(shù)表示法將2個(gè)問(wèn)題分別表示如下:

其中tdcrm表示與時(shí)間相關(guān)的維修活動(dòng),pdcrm表示與位置相關(guān)的維修活動(dòng),Spsd表示安裝時(shí)間。

2 對(duì)于帶有固定長(zhǎng)度維修活動(dòng)的最優(yōu)排序的性質(zhì)

對(duì)于帶有交貨期窗口的單機(jī)排序問(wèn)題,Mosheiov和Oron[10]證明了交貨期窗口的開(kāi)始時(shí)間和完工時(shí)間不能發(fā)生在工件加工過(guò)程中,且維修活動(dòng)如果發(fā)生,必排在一個(gè)延誤的工件之前。對(duì)于帶有安裝時(shí)間、維修活動(dòng)和交貨期窗口的單機(jī)排序問(wèn)題也有同樣結(jié)論。也就是:如果執(zhí)行了維修活動(dòng),維修活動(dòng)的開(kāi)始時(shí)間一定被排在一個(gè)工件的完工時(shí)刻之后(或者在0時(shí)刻)。假設(shè)維修活動(dòng)發(fā)生在第m個(gè)位置(l≤m),容易驗(yàn)證本文有類似的結(jié)論如下:

3 維修活動(dòng)長(zhǎng)度與時(shí)間相關(guān)的問(wèn)題

引理1 在最優(yōu)排序中,若維修活動(dòng)排在第m個(gè)位置,維修活動(dòng)的位置只能屬于下列3種情況之一:

情況1 維修并未發(fā)生,即m=n+1;

情況2 維修活動(dòng)在開(kāi)始處發(fā)生,即m=0;

情況3 維修活動(dòng)排在交貨期窗口之后,即l≤m

證明 假設(shè)排序?yàn)棣?(J[1],…,J[n]),下面具體討論這個(gè)問(wèn)題:

1) 維修并未發(fā)生。

(3) 交貨期窗口開(kāi)始時(shí)間之和為

(4) 交貨期窗口的長(zhǎng)度之和為

因?yàn)槲窗l(fā)生維修活動(dòng),所以g(u)=g(0)=0。

則目標(biāo)函數(shù)為

其中Wj為j位置的權(quán),有

為了得到目標(biāo)函數(shù)Z的最小值,將工件的加工時(shí)間p[j]與j位置的權(quán)Wj按照相反的順序排列。因此可以在O(nlogn)時(shí)間內(nèi)得到最優(yōu)排序。

2) 維修在機(jī)器開(kāi)始加工時(shí)發(fā)生。

此時(shí)s=0,則維修活動(dòng)的時(shí)間t(s,u)=t0+σs-τ(u)=t0-τ(u)

(1)Ej=max(0,dj[1]-Cj),總提前量為

(3) 交貨期窗口開(kāi)始時(shí)間之和為

(4) 交貨期窗口的長(zhǎng)度之和為

則目標(biāo)函數(shù)為

其中G(u)=γn(t0-τ(u))+g(u),Wj為j位置的權(quán),

3) 維修在第m個(gè)位置發(fā)生,(l≤m

(3) 交貨期窗口開(kāi)始時(shí)間之和為

(4) 交貨期窗口的長(zhǎng)度之和為

則目標(biāo)函數(shù)為

其中G(u)=β(n-m)(t0-τ(u))+g(u),Wj為j位置的權(quán)。

家長(zhǎng)要為孩子營(yíng)造溫馨、寬松、自由的閱讀氛圍。閱讀時(shí)要安靜，沒(méi)有打擾，家長(zhǎng)要帶領(lǐng)孩子開(kāi)展形式新穎、內(nèi)容豐富的閱讀活動(dòng)。閱讀時(shí)，家長(zhǎng)要給予孩子想象的空間，鼓勵(lì)孩子說(shuō)出自己的想法，使孩子在愉悅的環(huán)境中快樂(lè)閱讀。

假設(shè)j工件排在第i個(gè)位置上,那么xij=1,否則xij=0。為了得到目標(biāo)函數(shù)Z的最小值,可以將其轉(zhuǎn)化為指派問(wèn)題:

其中:

對(duì)于資源分配的費(fèi)用G(u)的最小值可以由u*=argmin{β(n-m)(t0-τ(u))+g(u)}得到,因?yàn)榫S修活動(dòng)位置的不同,每一個(gè)位置需要求解一個(gè)相應(yīng)的指派問(wèn)題,因此可以在O(n4)時(shí)間內(nèi)得到最優(yōu)排序。

由以上討論,得到定理1。

4 維修活動(dòng)長(zhǎng)度與位置相關(guān)的問(wèn)題

問(wèn)題4與問(wèn)題3的性質(zhì)類似,下面分別在3種情況下分析:

情況1 維修并未發(fā)生,即m=n+1;

情況2 維修活動(dòng)在開(kāi)始處發(fā)生,即m=0;

情況3 維修活動(dòng)排在交貨期窗口之后,即l≤m

證明 假設(shè)排序?yàn)棣?(J[1],…J[n]),維修活動(dòng)的時(shí)間為t(m,u)=t0φ(m) -τ(u)。

維修并未發(fā)生與維修在開(kāi)始時(shí)間發(fā)生的情況,與問(wèn)題(1)和(2)一致,不再繼續(xù)討論,接下來(lái)討論維修并未發(fā)生與維修在開(kāi)始時(shí)間發(fā)生的情況,與問(wèn)題(1)和(2)一致,不再繼續(xù)討論,接下來(lái)討論維修在第m個(gè)位置發(fā)生的情況:

維修在第m個(gè)位置發(fā)生,(l≤m

3) 交貨期窗口開(kāi)始時(shí)間之和為

4) 交貨期窗口的長(zhǎng)度之和為

則目標(biāo)函數(shù)為:

其中G(u)=β(n-m)(t0φ(m)-τ(u))+g(u),Wj為j位置的權(quán),

假設(shè)j工件排在第i個(gè)位置上,那么xij=1,否則xij=0。為了得到目標(biāo)函數(shù)Z的最小值,可以將其轉(zhuǎn)化為指派問(wèn)題:

其中:

對(duì)于資源分配的費(fèi)用G(u)的最小值可以由u*=argmin{β(n-m)(t0φ(m)-τ(u))+g(u)}得到。因?yàn)榫S修活動(dòng)位置的不同,每一個(gè)位置需要解一個(gè)相應(yīng)的指派問(wèn)題,因此可以在O(n4)時(shí)間內(nèi)得到最優(yōu)排序。

由以上討論,可以得到下列定理:

5 結(jié) 論

本文研究了每個(gè)工件都有自己的交貨期窗口、安裝時(shí)間是加工時(shí)間的線性函數(shù)、維修帶有資源的單機(jī)排序問(wèn)題。其中維修活動(dòng)使工件的加工時(shí)間縮短,可以通過(guò)資源分配使維修活動(dòng)長(zhǎng)度減少。目標(biāo)是找到交貨期窗口的大小和位置、維修的位置,使得提前懲罰、延誤懲罰、交貨期窗口的位置和長(zhǎng)度、以及資源的總費(fèi)用最小。在2種維修情況下,根據(jù)維修活動(dòng)的位置不同分為3類,證明了問(wèn)題是多項(xiàng)式可解的。另外,還可以在此基礎(chǔ)上繼續(xù)將模型推廣,比如帶有學(xué)習(xí)效應(yīng)與退化效應(yīng)的情況,也可以考慮工件的加工時(shí)間是帶有資源分配的。