機(jī)器無(wú)等待工件具有區(qū)間限制的兩臺(tái)同構(gòu)并行機(jī)上批在線調(diào)度

霍滿臣,陳忠菊

(1.沈陽(yáng)工程學(xué)院 基礎(chǔ)部，遼寧 沈陽(yáng) 110136； 2.遼寧公安司法管理干部學(xué)院 公共安全系，遼寧 沈陽(yáng) 110161)

?

機(jī)器無(wú)等待工件具有區(qū)間限制的兩臺(tái)同構(gòu)并行機(jī)上批在線調(diào)度

霍滿臣1,陳忠菊2

(1.沈陽(yáng)工程學(xué)院 基礎(chǔ)部，遼寧 沈陽(yáng) 110136； 2.遼寧公安司法管理干部學(xué)院 公共安全系，遼寧 沈陽(yáng) 110161)

摘要：針對(duì)兩臺(tái)同構(gòu)并行機(jī)上的在線批調(diào)度問(wèn)題，提出了使工件加工的最大完成時(shí)間最小的一個(gè)批在線列表調(diào)度算法。即工件組成不同的批，每個(gè)批中有m個(gè)工件，當(dāng)每批到達(dá)等待加工時(shí)，其內(nèi)部的工件加工時(shí)間才已知，且每個(gè)工件加工時(shí)間限定在某個(gè)實(shí)區(qū)間[a,b]上。在對(duì)當(dāng)前批后批中工件的信息不了解的情況下，立即將其中的工件按LPT規(guī)則調(diào)度進(jìn)行調(diào)度，調(diào)度過(guò)程中不允許中斷。 解決了算法的可使用性的度量問(wèn)題，對(duì)其最壞情況進(jìn)行了分析，給出了算法的最壞情況比。

關(guān)鍵詞：最壞情況比；兩臺(tái)同構(gòu)并行機(jī)；批工件列；最大完成時(shí)間；加工時(shí)間

現(xiàn)代流程工業(yè)中存在大量批在線調(diào)度問(wèn)題。在生產(chǎn)調(diào)度過(guò)程中，存在大量的不確定性，需要根據(jù)生產(chǎn)實(shí)際實(shí)時(shí)調(diào)整調(diào)度安排,產(chǎn)生動(dòng)態(tài)的調(diào)度算法[1,2]。批在線調(diào)度理論適用于解決這一類問(wèn)題。

離線調(diào)度理論假設(shè)在調(diào)度前已經(jīng)掌握了工件的全部信息，而在實(shí)際生產(chǎn)應(yīng)用中，工件的許多信息在調(diào)度前是不確定的，考慮這種動(dòng)態(tài)不確定性，產(chǎn)生了在線調(diào)度問(wèn)題[3~8]。Graham于1966年給出了在線列表調(diào)度算法并證明了其最好情況比為2-1/m[5]，但他沒(méi)有考慮工件按批方式到達(dá)的情況。實(shí)際上存在大量批加工問(wèn)題，而批調(diào)度比一次調(diào)度一個(gè)工件實(shí)用[9,10]。因此，以每次來(lái)m個(gè)工件的批到達(dá)情況為例，將批調(diào)度與在線調(diào)度相結(jié)合，針對(duì)一個(gè)批在線調(diào)度問(wèn)題，給出了一個(gè)在線批調(diào)度算法，分析了其最壞情況并給出了其最壞情況比。

1批在線調(diào)度問(wèn)題及算法

兩臺(tái)同構(gòu)并行機(jī)上批在線調(diào)度問(wèn)題可以描述如下：有兩臺(tái)用于加工工件的同構(gòu)并行機(jī)，工件組成一個(gè)批工件表列，工件以批形式按列表到達(dá)，將第i批工件記為bi (i=1,2,…,n)。其中每個(gè)工件的加工時(shí)間隨其批的到達(dá)便已知，且每個(gè)工件加工時(shí)間在某個(gè)實(shí)數(shù)區(qū)間[a,b]上。這里每個(gè)批中都有m個(gè)工件，每批一個(gè)接一個(gè)地到達(dá)形成一個(gè)批工件序列，且每批工件到達(dá)時(shí)，在不依賴其后面批的信息情況下，立即對(duì)該批中工件進(jìn)行調(diào)度，調(diào)度過(guò)程不允許被打斷。問(wèn)題的目標(biāo)是使調(diào)度的最大完成時(shí)間最小。

批在線調(diào)度算法記為A：當(dāng)一批工件bi (i=1,2,…,n-1)到達(dá)時(shí)，將該批中的工件進(jìn)行編號(hào)使它們滿足pi1≥pi2≥…≥pim，再根據(jù)LPT規(guī)則將該批中的工件調(diào)度到兩臺(tái)同構(gòu)并行機(jī)上，當(dāng)bi+1(i=1,2,…,n)中最后一個(gè)工件加工完成時(shí)，立即再調(diào)度bi(i=2,3,…,n)中所有工件，機(jī)器不允許空閑。

2批在線調(diào)度算法A的最壞情況分析

批在線算法A的最壞情況可用調(diào)度算法A對(duì)批工件列產(chǎn)生的最大完成時(shí)間與離線最優(yōu)算法產(chǎn)生的最大完成時(shí)間的比來(lái)度量。這個(gè)比定義為：R=sup{A(BL)/OPT(BL)}，其中BL為批工件列，A(BL)表示算法A對(duì)BL的最大完成時(shí)間,OPT(BL)表示離線最優(yōu)調(diào)度對(duì)BL的最大完成時(shí)間。

例如，現(xiàn)有3批工件，每批有5個(gè)工件要調(diào)度到兩臺(tái)并行機(jī)上如下表。

表1　不同批次不同工件的處理時(shí)間Pij

Pij(i=1，2，…，n-1；j=1，2，…，m)表示第i個(gè)批中第j個(gè)工件的處理時(shí)間，且所有加工時(shí)間pij∈[a,b]，此處pij∈[3,6]。

圖1　批在線算法A對(duì)批工件列產(chǎn)生的調(diào)度

其中，CA=40。

圖2　離線算法對(duì)批工件列產(chǎn)生的最優(yōu)調(diào)度

其中，COPT=39。

引理2設(shè)算法A產(chǎn)生的在線調(diào)度中，批工件列BL最后到達(dá)的批最后完成。

1)當(dāng)最后完成的工件的開始加工時(shí)間不大于前n-1批中工件的加工時(shí)間和的一半，則

2)當(dāng)工件Jnk的開始加工時(shí)間t超過(guò)前n-1批中全部工件的加工時(shí)間和的一半，則

證明首先，離線最優(yōu)調(diào)度下的最大完成時(shí)間滿足

設(shè)最后一批，即第n批中最后完成加工的工件為Jnk，其開始加工時(shí)間是t，則由算法A產(chǎn)生調(diào)度的最大完成時(shí)間為CA(BL)=t+Pnk。

1)當(dāng)工件Jnk的開始加工時(shí)間t不超過(guò)前n-1個(gè)批中全部工件的加工時(shí)間和的一半，即

2)當(dāng)工件Jnk的開始加工時(shí)間t超過(guò)前n-1批中全部工件的加工時(shí)間和的一半，即

這樣算法A產(chǎn)生的調(diào)度的最大完成時(shí)間

根據(jù)以上的(1)與(2)，得出引理2的結(jié)論。

引理3pij∈[a,b]

證明

3結(jié)論

通過(guò)對(duì)一個(gè)在線批列表調(diào)度問(wèn)題的研究，將以往工件的到達(dá)推廣為工件以批的方式到達(dá)，討論了在限定每一批中恰有m個(gè)工件且工件加工時(shí)間在一定區(qū)間上的情況，最終提出了一個(gè)批在線調(diào)度算法，即每一批中的工件按LPT規(guī)則進(jìn)行調(diào)度，并證明了算法A的最壞情況比不超過(guò)3/2，從理論上證明了以批形式組織生產(chǎn)更能提高生產(chǎn)效率。

參考文獻(xiàn)

[1]Tang L X,Liu J Y,Rong A Y,et al.A review of planning and scheduling systems and methods for integrated steel production[J].European Journal of Operational Research,2001,133:1-20.

[2]唐立新.軋鋼廠的精軋工序軋制批量調(diào)度的優(yōu)化模型[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版,1998,19(6):624-626.

[3]Chen B,Vestjens A.P.A.Scheduling on identical machines:How good is LPT in an on-line setting?[J].Operations Research Letters,1998,21(15):165-169.

[4]霍滿臣，唐立新.面向流程工業(yè)的批在線調(diào)度問(wèn)題[J].控制工程，2005,12(6):511-514.

[5]Pinedo.調(diào)度：原理、算法和系統(tǒng)[M].第2版.北京：清華大學(xué)出版社,2005.

[6]Xiuli Wang,1,2 T.C.Edwin Cheng.Machine Scheduling with an Availability Constraint and Job Delivery Coordination.Naval Research Logistics,2007，54：11-21.

[7]Epstein L,Sgall J.A lower bound for on-line scheduling on uniformly related machines[J].Operations Research Letters,2000,26(1):17-22.

[8]Lu X,Sitters R A,Stougie L.A class of on-line scheduling algorithms to minimize total completion time[J].Operations Research Letters,2003,31:232-236.

[9]Potts C N,Kovalyov M Y.Scheduling with batching:A review[J].European Journal of Operational Research,2000,120:228-249.

[10]霍滿臣，唐立新.基于到達(dá)時(shí)間兩臺(tái)并行機(jī)上在線批調(diào)度[J].控制與決策，2009,12(12):1826-1830.

(責(zé)任編輯張凱校對(duì)佟金鍇)

Batch On-line Scheduling of Workpieces on Two Parallel

Machines with Time Interval Restriction

HUO Man-chen1,CHEN Zhong-ju2

(1.Basic Courses Department,Shenyang Institute of Engineering,Shenyang 110136;

2.Public Security Department,Liaoning Administrators College of Police and Justice,Shenyang 110161,Liaoning Province)

Abstract：An algorithm was put forward to satisfy the batch on-line scheduling on two identical parallel machines with the objective to minimize the maximum completion time.In the algorithm,all workpieces were divided into different batches,and each batch has m workpieces.The processing times of workpieces in every batch were given only when the batch containing them arrived and they were constrained in some interval[a,b].When a batch arrived,the workpieces in this batch were scheduled immediately and irrevocably with the unknown following batches.An algorithm with scheduling workpieces in every batch by LPT rule was proposed.The measurement of the algorithm application was solved,the worst case was analyzed and the worst case ratio was given.

Key words：Worst case ratio;Two identical parallel machines;Batch list;Maximum completion time;Processing time

DOI：10.13888/j.cnki.jsie(ns).2015.01.021

作者簡(jiǎn)介：馬國(guó)強(qiáng)(1960-)，男，遼寧沈陽(yáng)人，助理實(shí)驗(yàn)師。

收稿日期：2014-09-14

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

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-1603(2015)01-0090-03