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

劉其佳，張利齊，馮　琪

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

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

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

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

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

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

0引言

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

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

1問題的描述

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

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

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

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

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

2問題的下界

定理1對于排序問題

不存在競爭比小于1+α的在線算法.

進而當k→+∞時，得到

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

當k→+∞且ε→0時，有

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

→1+α.此定理得證.

3設計在線算法及競爭比分析

3.1算法Dc

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

運輸階段.

步驟3如果0

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

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

步驟4回到步驟 1.

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

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

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

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

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

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

(2).已知在任意一個可行的排序中始終有δ(Bi)≥ρ(Bi).因為車輛在緊挨著時刻δ(Bi)之前是空閑的，有δ(Bi-1)+T<δ(Bi)，說明在δ(Bi)時刻之前運輸批Bi中還有沒有完工的工件，因而有δ(Bi)=ρ(Bi).

現(xiàn)在我們來分析算法Dc的競爭比為2.

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

定理2對于排序問題是

算法Dc是一個競爭比為2的在線算法.

4結(jié)論

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

參考文獻：

[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

中圖分類號：O223

文獻標志碼：A

doi:10.3969/j.issn.1671-6833.2015.02.027

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

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

基金項目:國家自然科學基金資助項目(11401604; 11401605); 河南省基礎與前沿技術(shù)研究計劃資助(132300410392)

收稿日期:2014-08-30；

修訂日期：2014-11-25