劉其佳，張利齊，馮　琪

(1.鄭州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 鄭州 450001；2.河南農(nóng)業(yè)大學(xué) 信息與管理科學(xué)學(xué)院，河南 鄭州 450003；3.中原工學(xué)院 理學(xué)院，河南 鄭州 450007)

考慮運(yùn)輸?shù)耐嘶ぜ诰€排序問(wèn)題研究

劉其佳1，張利齊2，馮琪3

(1.鄭州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 鄭州 450001；2.河南農(nóng)業(yè)大學(xué) 信息與管理科學(xué)學(xué)院，河南 鄭州 450003；3.中原工學(xué)院 理學(xué)院，河南 鄭州 450007)

摘要：本文研究了單臺(tái)機(jī)器上工件具有退化效應(yīng)并且需要考慮工件運(yùn)輸?shù)脑诰€排序問(wèn)題.目標(biāo)函數(shù)是最小化最大運(yùn)輸完工時(shí)間.對(duì)于這個(gè)在線排序問(wèn)題，主要是設(shè)計(jì)一個(gè)有效的在線算法.首先采用對(duì)手法找到問(wèn)題的下界，即設(shè)計(jì)一個(gè)壞實(shí)例，使得算法得到的目標(biāo)值與離線最優(yōu)目標(biāo)值的比盡可能的大，之后依據(jù)下界設(shè)計(jì)給出一個(gè)在線算法.通過(guò)對(duì)手法的應(yīng)用，給出問(wèn)題的下界，并設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比為2的在線算法.

關(guān)鍵詞：排序；退化工件；運(yùn)輸

0引言

排序問(wèn)題是一類重要的優(yōu)化問(wèn)題.在經(jīng)典的排序問(wèn)題中，所有工件在機(jī)器上的加工時(shí)間為一個(gè)常數(shù).然而在實(shí)際問(wèn)題中，許多工件的加工時(shí)間依賴于工件的開(kāi)工時(shí)間.例如：在鋼鐵企業(yè)的生產(chǎn)過(guò)程中，工件的加工是有著嚴(yán)格的溫度要求的.如果工件在加工前有等待時(shí)間，將會(huì)引起工件溫度下降.這樣，必須重新加溫到規(guī)定的溫度才能加工工件，從而導(dǎo)致加工時(shí)間變長(zhǎng).再比如，機(jī)器長(zhǎng)時(shí)間加工出現(xiàn)老化現(xiàn)象同時(shí)工人的長(zhǎng)時(shí)間工作會(huì)出現(xiàn)疲勞操作，這些都會(huì)導(dǎo)致開(kāi)工晚的工件所需要的加工時(shí)間變長(zhǎng).文獻(xiàn)[1]和[2]分別獨(dú)立提出了具有退化效應(yīng)的排序問(wèn)題.文獻(xiàn)[3]對(duì)單機(jī)上工件的加工時(shí)間是開(kāi)工時(shí)間的簡(jiǎn)單線性函數(shù)的排序問(wèn)題進(jìn)行研究.但是在實(shí)際問(wèn)題中，決策者并不能在決策時(shí)刻知道工件的完整信息.因此線排序問(wèn)題受到越來(lái)越多人的關(guān)注.文獻(xiàn)[4]研究了3個(gè)工件具有退化效應(yīng)的在線排序問(wèn)題，目標(biāo)函數(shù)分別為最小化最大運(yùn)輸完工時(shí)間、完工時(shí)間和以及最大時(shí)間表長(zhǎng).對(duì)于這3個(gè)問(wèn)題，作者給出了最好可能的在線算法.文獻(xiàn)[5]中工件的加工時(shí)間是關(guān)于開(kāi)工時(shí)間的簡(jiǎn)單線性函數(shù)，目標(biāo)函數(shù)是最小化完工時(shí)間和.對(duì)于這個(gè)問(wèn)題，文獻(xiàn)[5]給出問(wèn)題的下界并設(shè)計(jì)出達(dá)到下界的最好可能的在線算法.

近些年，整合生產(chǎn)和運(yùn)輸?shù)脑诰€排序問(wèn)題也得到了廣泛的研究.文獻(xiàn)[6]較早的研究了單機(jī)上考慮工件運(yùn)輸?shù)脑诰€排序問(wèn)題，并給出最好可能的在線算法.文獻(xiàn)[7]是在批處理機(jī)上研究帶工件運(yùn)輸?shù)脑诰€排序問(wèn)題.當(dāng)批處理機(jī)的數(shù)目為2和3時(shí)，分別給出了競(jìng)爭(zhēng)比為2的在線算法.當(dāng)批處理機(jī)的數(shù)目大于4時(shí)，給出競(jìng)爭(zhēng)比為1.5的在線算法.文獻(xiàn)[8]是研究單機(jī)上工件需要分批運(yùn)輸?shù)脑诰€排序問(wèn)題.對(duì)于不同的模型，分別給出了在線算法.文獻(xiàn)[9]研究了兩階段供應(yīng)鏈的半在線排序問(wèn)題，并給出了有效的算法.在此之前的文獻(xiàn)分別研究了退化工件的排序問(wèn)題以及工件具有運(yùn)輸時(shí)間的排序問(wèn)題，但是并沒(méi)有很好的將二者結(jié)合起來(lái).筆者研究了運(yùn)輸車輛的容量有限制的退化工件的在線排序問(wèn)題，不僅將二者有效的結(jié)合在一起，而且更符合實(shí)際生產(chǎn)生活的要求.

1問(wèn)題的描述

假定工件J1,J2,……,Jn按時(shí)間在線到達(dá)，即只有工件Jj到達(dá)了，才能知道它的到達(dá)時(shí)間rj及退化率aj.而且工件的數(shù)目n也是事先不知道的.我們研究的模型中，工件的退化效應(yīng)是指pj=ajt，其中t是該工件的開(kāi)工時(shí)刻.工件的加工時(shí)間依賴于工件的開(kāi)工時(shí)間，通常假定所有的工件是在某個(gè)時(shí)刻及之后到達(dá)的，假定所有工件是在t0時(shí)刻及之后到達(dá)的.這些工件先在一臺(tái)機(jī)器上加工，然后完工的工件再由一臺(tái)容量有限制的車輛運(yùn)送給下了訂單的顧客.目標(biāo)函數(shù)是最小化最大運(yùn)輸完工時(shí)間.令T是車輛在機(jī)器和顧客之間運(yùn)送一個(gè)來(lái)回所花費(fèi)的時(shí)間.由于事先并不會(huì)知道誰(shuí)會(huì)下訂單，因而假定當(dāng)?shù)谝粋€(gè)工件到達(dá)的時(shí)刻，才會(huì)知道T的大小.我們用Dj表示Jj的運(yùn)輸完工時(shí)間，即車輛將Jj由加工地運(yùn)送給顧客并再次返回到加工地的時(shí)刻.這個(gè)在線排序問(wèn)題用三參數(shù)表示為

式中：1→D表示工件先在一臺(tái)機(jī)器上加工，完工的工件再被車輛運(yùn)送給顧客；online,rj≥t0表示這個(gè)排序問(wèn)題中的工件按時(shí)間在線到達(dá)；pj=ajt表示工件的加工時(shí)間依賴于工件的開(kāi)工時(shí)間；v=1,c表示有一臺(tái)容量限制為c的車輛參與運(yùn)輸，即車輛每次運(yùn)送的工件數(shù)最多為c個(gè)；Dmax=max{Dj,1≤j≤n}是目標(biāo)函數(shù)，最大運(yùn)輸完工時(shí)間.

在線排序中，決策者是在不知道未來(lái)工件信息的情況下設(shè)計(jì)在線算法的，因此大部分的問(wèn)題都找不到最優(yōu)的在線算法.通常我們用競(jìng)爭(zhēng)比衡量在線算法的好壞，對(duì)于最小化目標(biāo)函數(shù)的問(wèn)題，我們說(shuō)在線算法A是ρ競(jìng)爭(zhēng)的，如果對(duì)任意實(shí)例I有A(I)≤ρ·opt(I)，其中A(I)是在線算法A的目標(biāo)函數(shù)值，opt(I)是最優(yōu)離線算法生成的目標(biāo)函數(shù)值.研究在線排序問(wèn)題時(shí)，首先要找到問(wèn)題的下界，通常是用對(duì)手法.所謂對(duì)手法是指設(shè)計(jì)一個(gè)壞實(shí)例，使得任意的在線算法應(yīng)用到該實(shí)例上時(shí)得到的目標(biāo)值與離線最優(yōu)目標(biāo)值的比值盡可能大.然后再設(shè)計(jì)在線算法，而設(shè)計(jì)算法的競(jìng)爭(zhēng)比要盡可能的與問(wèn)題的下界接近，而一旦算法的競(jìng)爭(zhēng)比與問(wèn)題的下界吻合，我們稱這樣的算法為最好可能的在線算法，這樣在線問(wèn)題就得到徹底的解決.

在我們研究的排序問(wèn)題中，車輛的運(yùn)輸容量是有限制的，這也和實(shí)際問(wèn)題一致.我們將放在車輛上同時(shí)運(yùn)輸?shù)墓ぜ戏Q為一個(gè)運(yùn)輸批.令B1,……,Bq是某個(gè)排序中按此標(biāo)號(hào)運(yùn)輸?shù)倪\(yùn)輸批.

U(t): 時(shí)刻t已經(jīng)到達(dá)但尚未加工的工件集合；A(s): 時(shí)刻s已經(jīng)完工但尚未被運(yùn)輸?shù)墓ぜ?；?Bi): 運(yùn)輸批Bi的準(zhǔn)備時(shí)間，即集合Bi里工件的最大完工時(shí)刻；δ(Bi):Bi開(kāi)始被運(yùn)送的時(shí)刻，顯然在一個(gè)可行排序中，始終有δ(Bi)≥ρ(Bi)；如果δ(Bi-1)+T<δ(Bi)，我們說(shuō)車輛在緊挨著時(shí)刻δ(Bi)之前是空閑的；反之，如果δ(Bi-1)+T=δ(Bi)，我們說(shuō)車輛在緊挨著時(shí)刻δ(Bi)之前是忙碌的；D(Bi): 運(yùn)輸批Bi的運(yùn)輸完工時(shí)刻，即D(Bi)=δ(Bi)+T.

2問(wèn)題的下界

定理1對(duì)于排序問(wèn)題

不存在競(jìng)爭(zhēng)比小于1+α的在線算法.

進(jìn)而當(dāng)k→+∞時(shí)，得到

=1+(αt0(1+a1)+αT)/t0(1+a1)+T=1+α.

當(dāng)k→+∞且ε→0時(shí)，有

=1+a1t/(t+kT)≥1+(α(k-1)T)/(t+kT)

→1+α.此定理得證.

3設(shè)計(jì)在線算法及競(jìng)爭(zhēng)比分析

3.1算法Dc

加工階段.在時(shí)刻t，如果機(jī)器是空閑的且有U(t)≠?時(shí)，從U(t)中選擇退化率最小的工件在t時(shí)刻加工.否則，只需等待.

運(yùn)輸階段.

步驟3如果0

①如果機(jī)器在時(shí)刻s是空閑的且U(s)=?，把集合A(s)中的工件放在一個(gè)運(yùn)輸批并在時(shí)刻s運(yùn)送這個(gè)運(yùn)輸批.

②如果機(jī)器在時(shí)刻s是忙碌的或者U(s)≠?，需要等待到機(jī)器是空閑的且U(s′)=?的時(shí)刻(s′>s)或者等待到有新的工件到達(dá)的時(shí)刻.

步驟4回到步驟 1.

事實(shí)上算法Dc的加工階段是一個(gè)相對(duì)獨(dú)立的算法，只要是有已經(jīng)到達(dá)尚未加工的工件，機(jī)器就會(huì)一直忙碌.而算法Dc的運(yùn)輸階段則是要依賴于是否有一定數(shù)目的已經(jīng)完工尚未被運(yùn)送的工件.運(yùn)輸階段中機(jī)器是空閑的說(shuō)明此刻沒(méi)有工件正在加工，而U(s)=?說(shuō)明此刻沒(méi)有已經(jīng)到達(dá)但尚未加工的工件.當(dāng)需要運(yùn)輸?shù)墓ぜ臄?shù)目不超過(guò)c個(gè)時(shí)，必須同時(shí)滿足以上兩個(gè)條件，車輛才有可能開(kāi)始運(yùn)送工件.

證明：引理 1.中的貪婪算法是指在存在已經(jīng)到達(dá)且尚未加工的工件時(shí)，算法可以按照任意的順序?qū)⒐ぜ才旁跈C(jī)器上的加工.由此算法Dc的運(yùn)輸階段就是一個(gè)貪婪算法，依據(jù)引理1知道μ是排序問(wèn)題

假定在研究的排序問(wèn)題中有n個(gè)工件.由于車輛的運(yùn)輸容量是有限的，即每次運(yùn)輸最多能運(yùn)c個(gè)工件，在任意一個(gè)可行排序中，最少需要k*=「n/c?個(gè)運(yùn)輸批.而一個(gè)運(yùn)輸批被稱為滿的，是指這個(gè)運(yùn)輸批中恰好運(yùn)送了c個(gè)工件.否則，我們稱一個(gè)運(yùn)輸批為非滿的.很容易可以得到以下這個(gè)引理.

引理4(1).δ(Bi)≥αT，對(duì)1≤i≤k.

(2). 如果車輛在緊挨著時(shí)刻δ(Bi)之前是空閑的，那么有δ(Bi)=ρ(Bi).

證明：(1).由算法Dc運(yùn)輸階段(步驟 1)的執(zhí)行規(guī)則，顯然有δ(Bi)≥αT，對(duì)1≤i≤k.

(2).已知在任意一個(gè)可行的排序中始終有δ(Bi)≥ρ(Bi).因?yàn)檐囕v在緊挨著時(shí)刻δ(Bi)之前是空閑的，有δ(Bi-1)+T<δ(Bi)，說(shuō)明在δ(Bi)時(shí)刻之前運(yùn)輸批Bi中還有沒(méi)有完工的工件，因而有δ(Bi)=ρ(Bi).

現(xiàn)在我們來(lái)分析算法Dc的競(jìng)爭(zhēng)比為2.

由引理5和引理6，可以得到下面的定理.

定理2對(duì)于排序問(wèn)題是

算法Dc是一個(gè)競(jìng)爭(zhēng)比為2的在線算法.

4結(jié)論

研究了工件具有退化效應(yīng)且有一臺(tái)容量有限制的車輛參與運(yùn)輸?shù)脑诰€排序問(wèn)題.用對(duì)手法找到一個(gè)壞例子來(lái)說(shuō)明了任意一個(gè)在線算法它的競(jìng)爭(zhēng)比不會(huì)小于1+α.然后設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比為2的在線算法.對(duì)于該問(wèn)題的下界是否能夠增大，又或者能否找到競(jìng)爭(zhēng)比小于2的在線算法是進(jìn)一步的研究課題.

參考文獻(xiàn)：

[1]GUPTA J N D, GUPTA S K. Single facility scheduling with nonlinear processing times [J]. Computer and Industrial Engineering, 1988, 14(4): 387-393.

[2]BROWNE S, YECHIALI U. Scheduling deteriorating jobs on a single processor [J]. Operations Research, 1990, 38(3): 495-498.

[3]MOSHEIOV G. Scheduling jobs under simple linear deteriorating [J]. Computer and Operations Research, 1994, 21(6): 653-659.

[4]LIU Ming, ZHENG Fei-feng, WANG Shi-jin, et al. Optimal algorithms for online single machines with deteriorating jobs [J]. Theoretical Computer Science, 2012, 445: 75-81.

[5]YU Sheng, PRODENCE W.H.WONG. Online scheduling of simple linear deteriorating jobs to minimize the total general completion time [J]. Theoretical Computer Science, 2013, 487: 95-102

[6]HOOGEVEEN J A, VESTJEN A P A. A best possible Deterministic online algorithm for minimizing maximum delivery time on a single machine [J]. SIAM Journal on Discrete Mathematics, 2000, 13(1): 56-63.

[7]FANG Yang, LU Xi-wen, LIU Pei-hai. Online batch scheduling on parallel machines with delivery times [J]. Theoretical Computer Science, 2011, 412(39): 5333-5339.

[8]NG C T, LU Ling-fa. On-line integrated production and outbound distribution scheduling to minimize the maximum delivery completion time [J]. Journal of Scheduling, 2012, 15(3): 391-398.

[9]IGOR A, MEHMET B. Semi-online two-level supply chain scheduling problems [J]. Journal of Scheduling, 2012, 15(3): 381-390.

Research on Online Scheduling with Deteriorating Jobs and Delivery Times

LIU Qi-jia1, ZHANG Li-qi2, FENG Qi3

(1.School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China; 2.College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, China; 3.College of Science, Zhongyuan University of Technology, Zhengzhou 450007, China)

Abstract:In this paper, we study the online scheduling on a single machine with deteriorating jobs and delivery times. The objective function is to minimize the maximum delivery completion time of these jobs. For this online scheduling problem, the objective is to design an effective online algorithm. We establish a lower bound by adversary strategy, i.e., design a bad instance to make the ratio of the objective by online algorithm and offiine objective as big as possible, then we present an online algorithm by this lower bound. Thus we get a lower bound by adversary strategy and an online algorithm with the competitive ratio of 2.

Key words:scheduling; deteriorating jobs; delivery

中圖分類號(hào)：O223

文獻(xiàn)標(biāo)志碼：A

doi:10.3969/j.issn.1671-6833.2015.02.027

文章編號(hào):1671-6833(2015)02-0125-04

作者簡(jiǎn)介:劉其佳(1987-)，女，河南尉氏人，鄭州大學(xué)博士生，主要研究方向:圖論與組合最優(yōu)化，E-mail:liuqijia39@163.com.

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(11401604; 11401605); 河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃資助(132300410392)

收稿日期:2014-08-30；

修訂日期：2014-11-25