具有多個受限制可用時間段的單機供應(yīng)鏈排序問題

范靜(上海第二工業(yè)大學理學院,上海201209)

?

具有多個受限制可用時間段的單機供應(yīng)鏈排序問題

范靜
(上海第二工業(yè)大學理學院,上海201209)

摘要:在文中所研究的單機供應(yīng)鏈排序問題中,機器可用時間段的長度不大于給定常數(shù),且每個不可用時間段長度確定。工件僅可以在機器的可用時間段內(nèi)被加工,完工后可與其他完工工件組成一批,由一個容量無限制的運輸工具發(fā)送給客戶。運輸工具在機器的每個可用時間段結(jié)束時間進行發(fā)送,且每次發(fā)送的費用固定。問題的目標是安排工件的加工、發(fā)送,以及機器的不可用時間段,以使總發(fā)送時間與總發(fā)送費用之和達到最小。對于工件允許中斷的情況,可在多項式時間O(nlogn)內(nèi)得到最優(yōu)序(n為工件的個數(shù))。對于工件不允許中斷的情況,證明了問題是強NP-難的,并提出了2-近似算法。

關(guān)鍵詞:可用時間段;供應(yīng)鏈排序;強NP-難;近似算法

0　引言

供應(yīng)鏈排序是把生產(chǎn)、分批和發(fā)送三者集成在一起,研究集成優(yōu)化的模型及其算法[1]。實際上,供應(yīng)鏈排序就是在排序決策范疇內(nèi)研究供應(yīng)鏈管理,是排序論在供應(yīng)鏈管理中的應(yīng)用。供應(yīng)鏈排序的第一篇論文是由Potts[2]于1980年發(fā)表的。2003年Hall和Potts[3]在論文中系統(tǒng)地提出了供應(yīng)鏈排序模型。此后,學者們對于供應(yīng)鏈排序問題的研究就越來越多了。本文研究的是兩階段供應(yīng)鏈排序問題,即工件在機器上加工后由運輸工具,如卡車、輪船等,從工廠出發(fā)運輸給客戶。由于運輸任務(wù)往往是由第三方物流公司負責的,所以可以認為運輸工具的數(shù)量無限制,但會產(chǎn)生一定的運輸費用。對于最小化總發(fā)送時間與總發(fā)送費用之和的目標,當運輸工具容量無限制時,Hall等[3]給出了時間復(fù)雜度為O(n2)的最優(yōu)動態(tài)規(guī)劃算法(n為工件的個數(shù));當運輸工具容量有限制時,Chen和Vairaktarakis[4]給出了多項式時間為O(nlogn + nc)的最優(yōu)動態(tài)規(guī)劃算法,其中c表示運輸工具的容量。

在大多數(shù)供應(yīng)鏈排序問題的研究中,機器一直是可用的。但在實際的工作生產(chǎn)中,機器需要定期檢修保養(yǎng),以保證其生產(chǎn)質(zhì)量,因而會出現(xiàn)多個不可用時間段。對于機器的可用時間段長度確定的情況,Chen[5]研究了目標為最小化完工時間和的問題,給出一個啟發(fā)式算法及分支定界算法;Fan和Lu[6]研究了目標為最小化總發(fā)送時間與總發(fā)送費用之和的問題,其中每個可用時間段內(nèi)完工工件在可用時間段結(jié)束時刻發(fā)送,證明了問題是強NP-難的,并提出了2-近似算法與分支定界算法。對于機器可用時間段長度不大于給定常數(shù)、且不可用時間段也需要安排的情況,Qi等[7]對于目標為最小化總完工時間的問題進行了研究,證明問題是強NP-難的,并給出3個近似算法與分支定界算法;Akturk等[8-9]從實際生產(chǎn)情況出發(fā)也研究了該問題,將變更加工工具所需時間視為不可用時間,并且在文獻[9]中證明基于工件按加工時間的非降序(SPT序)安排加工所得的算法性能比為2;Qi[10]將這個性能比進行了改進。據(jù)查,目前尚未見研究不可用時間段需要安排,且同時考慮工件的加工與發(fā)送的供應(yīng)鏈排序問題的相關(guān)報道。

本文安排如下:第1節(jié)對所研究問題進行具體介紹;第2節(jié)針對工件加工允許中斷的情況,借助其最優(yōu)序的性質(zhì),得到問題的最優(yōu)算法;第3節(jié)針對工件加工不允許中斷的情況,證明問題是強NP-難的,進一步提出近似算法,并通過分析得到算法的近似比為2。

1　問題的描述

給定一臺機器及一個含n個工件的工件集J = {J1,J2,···,Jn}。這臺機器1次最多只能加工1個工件,而且僅在可用時間段內(nèi)加工工件,在不可用時間段內(nèi)不可加工工件。機器的每個可用時間段長度不超過T,每個不可用時間段的長度為t。工件Jj的加工時間為pj(j = 1,2,···,n),且在零時刻即可開始加工。由于機器存在不可用時間段,工件的加工有兩種情形:允許中斷與不允許中斷。工件的加工允許中斷是指,若工件的加工被機器當前的不可用時間段中斷,則在機器的下一個可用時間段內(nèi)加工可繼續(xù)進行;工件的加工不允許中斷是指,若工件在機器當前的可用時間段內(nèi)無法完全加工,則在機器的下一個可用時間段內(nèi)加工。多個已完工工件可組成一批由一個無容量限制的運輸工具發(fā)送給客戶。第j批工件的發(fā)送時間為第j個可用時間段的結(jié)束時間,記為Dj。每次發(fā)送的費用為α,總發(fā)送費用記為CT。如何安排工件的加工、發(fā)送,以及不可用時間段,使總發(fā)送時間與總發(fā)送費用之和最小化,是問題的目標。因此,研究的問題有兩個,采用三參數(shù)法可將兩個問題分別表示為:

其中,hk表示加工機器有多個不可用時間段;pmtn表示工件的加工允許中斷。

值得注意的是,如果工件的加工是不允許中斷的,那么由于機器的可用時間長度至多為T,所以在問題P2中任意工件Jj(j = 1,2,···,n)的加工時間pj應(yīng)滿足pj≤T,否則,實例無可行序。

2　工件允許中斷的情形

對于問題P1:1,hk|pmtn|ΣDj+ CT,即工件加工允許中斷的情形,先分析最優(yōu)序的性質(zhì),然后尋求問題的最優(yōu)序。

2.1問題P1最優(yōu)序的性質(zhì)

(1)工件按加工時間的非降序(SPT序)進行加工;

(2)機器的每個不可用時間段的開始時間為kT +(k-1)t(k = 1,2,···),而且在所有工件完工之前,加工機器除不可用時間段之外無空閑;

(3)如果工件Ji在工件Jj之前完工,則工件Ji的發(fā)送時間不晚于工件Jj;

(4)運輸工具的發(fā)送時間為kT+(k-1)t(k=1,2,···)。

利用文獻[3,10]中的方法,易得引理1是正確的。

2.2問題P1的最優(yōu)算法A1

算法A1執(zhí)行步驟如下:

步驟1從0時刻開始,在機器上按照工件加工時間的非降序(SPT序)盡早地加工工件;

步驟2在kT +(k-1)t(k = 1,2,···)時刻將所有已完工工件組成一批發(fā)送給客戶,并安排不可用時間段。

定理1算法A1可在多項式時間O(nlogn)內(nèi)得到問題P1:1,hk|pmtn|ΣDj+ CT的最優(yōu)序。

證明算法A1的步驟1滿足引理1中的(1),即工件的加工階段與最優(yōu)序相同。步驟2中要求在時刻kT +(k-1)t(k = 1,2,···)安排完工工件的發(fā)送及不可用時間段,這滿足了引理1中的(2)～(4),即完工工件的發(fā)送及不可用時間段的安排與最優(yōu)序相同。因此,算法A1得到的排序即為最優(yōu)序。

另外,算法A1中工件的排序需要時間O(nlogn),其余步驟需要時間O(n),因此,算法A1的時間復(fù)雜度為O(nlogn)。

3　工件不允許中斷的情形

3.1問題P2的性質(zhì)

首先,需要分析工件加工不允許中斷時問題P2的困難性。于是,得到下面的定理。

定理2問題P2:1,hk‖ΣDj+CT是強NP-難的。

證明考慮問題P2:1,hk‖ΣDj+ CT的特殊情況:當機器可用時間段長度等于給定常數(shù)時,問題P2轉(zhuǎn)化為文獻[6]所研究的問題,而后者被證明是強NP-難的。因此,問題P2:1,hk‖ΣDj+ CT至少也是強NP-難的。

接下來,討論問題P2最優(yōu)序所具備的一些性質(zhì)。

引理2若問題P2:1,hk‖ΣDj+ CT存在最優(yōu)序,則最優(yōu)序一定滿足以下條件:

(1)工件按加工時間的非降序(SPT序)進行加工;

(2)在所有工件完工之前,加工機器除不可用時間段之外無空閑;

(3)若工件Ji在工件Jj之前完工,則工件Ji的發(fā)送時間不晚于工件Jj。

顯然,由引理1可推出引理2的證明。

3.2問題P2的算法A2

定理3說明除非P = NP,否則不可能在多項式時間內(nèi)找到問題P2的最優(yōu)解。因此,提出一個近似算法來求解問題P2。

為方便起見,將工件按加工時間的非降序(SPT 序)重新編號,使得p1≤p2≤···≤pn。

算法A2執(zhí)行步驟如下:

步驟1從0時刻開始,在機器上按照工件加工時間的非降序(SPT序)盡早地加工工件,在保證可用時間段盡量長以及工件加工不被中斷的前提下,盡量晚地安排不可用時間段;

步驟2在每個可用時間段結(jié)束時間將所有已完工工件組成一批發(fā)送給客戶。

下面,分析算法A2的性能比。

定理4對于問題P2:1,hk‖ΣDj+ CT,算法A2是2-近似算法。

證明用σ?、δ?及δ分別表示問題P1的最優(yōu)序、問題P2的最優(yōu)序及由算法A2得到的問題P2的排序。用F(σ?)、F(δ?)及F(δ)分別表示問題P1的最優(yōu)值、問題P2的最優(yōu)值及排序δ得到的目標函數(shù)值。

由于δ?也是問題P1的可行序,于是

同時,根據(jù)問題P1的最優(yōu)序σ?,構(gòu)造一個新的排序?δ:如果在σ?中工件Jj被某不可用時間段中斷,那么在?δ中,工件Jj被單獨安排在一個可用時間段內(nèi)加工,在其完工時間發(fā)送Jj并且增加一個不可用時間段;其余未中斷工件盡早加工發(fā)送,且不可用時間段的安排不變。

顯然,?δ是問題P2的一個可行序。圖1、圖2與圖3分別為工件Jj、Jj+1、Jj+2及Jj+3在問題P1的最優(yōu)序σ?、算法A2求解問題P2的所得序δ以及問題P2的可行序?δ中加工情況的示例。

圖1　在σ?中Jj與Jj+3的加工被中斷Fig.1 Jobs Jjand Jj+3are interrupted in σ?

圖2　在δ中Jj、Jj+1與Jj+2在同一個可用時間段內(nèi)加工Fig.2 Jobs Jj,Jj+1and Jj+2are processed in the same available time interval in δ

圖3　在?中Jj、Jj+3分別單獨在一個可用時間段內(nèi)加工Fig.3 Jobs Jjand Jj+3are processed in the respective available time interval in?δ

由?δ的構(gòu)造過程可以看出,δ中每個工件的完工時間都不超過?δ中相應(yīng)工件的完工時間。于是,δ中每個工件的發(fā)送時間都不超過?δ中相應(yīng)工件的發(fā)送時間。又因為δ中的總發(fā)送次數(shù)比?δ中的總發(fā)送次數(shù)少,所以

式中,F(?δ)表示排序?δ得到的目標函數(shù)值。

對于問題P1的最優(yōu)序σ?,用p[j]表示第j個位置工件的加工時間,用L表示總發(fā)送次數(shù),用ni、Di分別表示第i個發(fā)送批Bi中工件的個數(shù)及發(fā)送時間。于是,問題P1的最優(yōu)目標函數(shù)值為而排序?δ對應(yīng)的目標函數(shù)值F(?δ)滿足以下不等式:

又由于

所以,不等式(3)可進一步化簡為

結(jié)合不等式(1)、(2)及(4),可以得到:

4　結(jié)語

在本文研究的單機供應(yīng)鏈排序問題中,加工機器的每個可用時間段長度不超過T。所有工件需在機器的可用時間段內(nèi)加工,完工后由運輸工具在每個可用時間段結(jié)束時間發(fā)送給客戶。如何安排工件的加工、發(fā)送,以及機器的各個不可用時間段,以使總發(fā)送時間與總發(fā)送費用之和最小是問題的目標。如果工件的加工允許中斷,在分析其最優(yōu)序性質(zhì)的基礎(chǔ)上,給出多項式時間最優(yōu)算法。如果工件的加工不允許中斷,證明問題是強NP-難的,并提出一個2-近似算法。

參考文獻:

[1]陳榮軍,唐國春.裝配系統(tǒng)的供應(yīng)鏈排序問題[J].數(shù)學的實踐與認識,2011,41(18):50-56.

[2]POTTS C N.Analysis of a heuristic for one machine sequencing with release dates and delivery times[J].Operations Research,1980,28(6):1436-1441.

[3]HALL N G,POTTS C N.Supply chain scheduling:Batching and delivery[J].Operations Research,2003,51(4):566-584.

[4]CHEN Z L,VAIRAKTARAKIS G L.Integrated scheduling of production and distribution operations[J].Management Science,2005,51(4):614-628.

[5]CHEN W.Minimizing total flow time in the singlemachine scheduling problem with periodic maintenance[J].Journal of Operations Research Society,2006,63(4):567-567.

[6]FAN J,LU X W.Supply chain scheduling problem in the hospital with periodic working time on a single machine[J].Journal of Combinatorial Optimization,2015,30(4):892-905.

[7]QI X,CHEN T,TU F.Scheduling the maintenance on a single machine[J].Journal of Operations Research Society,1999,50(10):1071-1078.

[8]AKTURK M,GHOSH J,GUNES E.Scheduling with tool changes to minimize total completion time:a study of heuristics and their performance[J].Naval Research Logistics,2003,50(1):15-30.

[9]AKTURK M,GHOSH J,GUNES E.Scheduling with tool changes to minimize total completion time:basic results and SPT performance[J].European Journal of Operational Research,2004,157(3):784-790.

[10]QI X.A note on worst-case performance of heuristics for maintenance scheduling problems[J].Discrete Applied Mathematics,2007,155(3):416-422.

簡訊

A Single-machine Supply Chain Scheduling Problem with Restricted Availability Intervals

FAN Jing
(School of Science,Shanghai Polytechnic University,Shanghai 201209,P.R.China)

Abstract:A single-machine supply chain scheduling problem with multiple restricted availability intervals was studied.The length of each availability interval was no more than a given constant and the length of each unavailability interval was fixed.Jobs were processed in availability intervals on the machine and the completed jobs were delivered in batches to a customer by one vehicle without capacity restriction.The departure time of each delivery batch was set to the end time of every availability interval and the cost of each delivery batch was fixed.The objective was to minimize the sum of total delivery time and total delivery cost by scheduling the production and delivery of every job as well as the unavailability intervals.If jobs were preemptive,the optimal schedule in the polynomial time O(nlogn)was obtained.If jobs were non-preemptive,it was proved that the problem is strongly NP-hard and a 2-approximation algorithm was presented.

Keywords:availability interval;supply chain scheduling;strongly NP-hard;approximation algorithm

基金項目:上海第二工業(yè)大學青年教師培養(yǎng)科研項目(No.201513)資助

通信作者:范靜(1979–),女,山西長治人,副教授,碩士,主要研究方向為排序論。電子郵箱fanjing@sspu.edu.cn。

收稿日期:2015-07-01

文章編號:1001-4543(2016)01-0045-05

中圖分類號:O223

文獻標志碼:A