霍滿臣，陳忠菊

(1.沈陽工程學(xué)院 基礎(chǔ)部，遼寧 沈陽 110136；

2.遼寧公安司法管理干部學(xué)院 公共安全系，遼寧 沈陽 110161)

?

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

霍滿臣1，陳忠菊2

(1.沈陽工程學(xué)院 基礎(chǔ)部，遼寧 沈陽 110136；

2.遼寧公安司法管理干部學(xué)院 公共安全系，遼寧 沈陽 110161)

摘要：研究兩臺(tái)同構(gòu)并行機(jī)上的批在線調(diào)度問題，工件以批方式到達(dá)且每個(gè)批中有m個(gè)工件，每個(gè)工件的處理時(shí)間限定在一個(gè)區(qū)間上，只有當(dāng)前批中工件全部加工完成后才可以加工其后面的工件，目標(biāo)函數(shù)是使最大完成時(shí)間最小。針對(duì)這一問題，給出了1個(gè)批在線啟發(fā)式調(diào)度算法，在同一批中的工件按LPT規(guī)則調(diào)度。對(duì)算法的最壞情況進(jìn)行了分析并給出了算法的最壞情況比與批中工件數(shù)有關(guān)，并由計(jì)算機(jī)程序進(jìn)行了驗(yàn)證。

關(guān)鍵詞：批在線列表調(diào)度；最壞情況比；同構(gòu)并行機(jī)；最大完成時(shí)間；加工時(shí)間

在流程工業(yè)中存在大量的在線批調(diào)度問題。對(duì)生產(chǎn)工序進(jìn)行優(yōu)化,使生產(chǎn)資源配置的變化降到最低是重要的問題。在生產(chǎn)調(diào)度中，要充分考慮過程的不確定性，根據(jù)生產(chǎn)實(shí)績實(shí)時(shí)調(diào)整調(diào)度安排,產(chǎn)生新的調(diào)度信息[1,2]。

古典的調(diào)度問題中，假設(shè)在調(diào)度前已經(jīng)給出了工件的全部信息，而在實(shí)際問題中，在調(diào)度前許多工件的信息是未知的，針對(duì)這一情況，提出了在線調(diào)度理論[3-8]。Graham于1966年提出了算法最壞情況為2-1/m的列表在線調(diào)度理論[5]，但他沒考慮批形式調(diào)度的情況。而實(shí)際中存在大量的在線批調(diào)度的情況，利用在線批調(diào)度比一次調(diào)度一個(gè)工件更經(jīng)濟(jì)實(shí)用[9-11]。

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

1.1兩臺(tái)同構(gòu)并行機(jī)上的批在線調(diào)度問題

有2臺(tái)同構(gòu)并行機(jī)和1個(gè)批工件序列，即工件以批方式按列表到達(dá)，將第i批工件記為bi(i=1,2,…,n)，每個(gè)工件加工時(shí)間在某個(gè)實(shí)數(shù)區(qū)間[a,b]上。這里假定每個(gè)批中都有m個(gè)工件，每批一個(gè)接一個(gè)地到達(dá)，形成1個(gè)批工件序列表，且當(dāng)每批工件到達(dá)時(shí)，在不知其后面批工件列信息的情況下，對(duì)該批中工件立即進(jìn)行調(diào)度。當(dāng)該批工件全部加工完時(shí)，才調(diào)度其后面批中的工件。目標(biāo)函數(shù)是使調(diào)度的最大完成時(shí)間(makespan)最小。

1.2批在線調(diào)度算法A

當(dāng)1批工件bi(i=1,2,…,n-1)到達(dá)時(shí)，將該批中的工件進(jìn)行編號(hào)，使它們加工時(shí)間滿足pi1≥pi2≥…≥pim，其中Pij(i=1，2，…，n-1；j=1，2，…，m)表示第i個(gè)批中第j個(gè)工件的處理時(shí)間，且所有加工時(shí)間pij∈[a,b]。然后根據(jù)LPT規(guī)則將該批中的工件調(diào)度到兩臺(tái)同構(gòu)并行機(jī)上，當(dāng)bi+1(i=1,2,…,n)中所有工件加工完成時(shí)，立即再調(diào)度bi(i=2,3,…,n)中所有工件。

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

在線批調(diào)度算法A的最壞情況可用調(diào)度算法A對(duì)批工件列產(chǎn)生的最大完成時(shí)間與離線最優(yōu)算法產(chǎn)生的最大完成時(shí)間的比來度量。這個(gè)比定義為

R=sup{A(BL)/OPT(BL)}

其中，BL為批工件列，A(BL)表示算法A對(duì)BL的最大完成時(shí)間(makespan),OPT(BL)表示離線最優(yōu)調(diào)度對(duì)BL的最大完成時(shí)間。

2.1實(shí)例

現(xiàn)有3批工件，每批有5個(gè)工件要調(diào)度到兩臺(tái)并行機(jī)上，如表1所示，其中pij∈[3,6]。

算法A產(chǎn)生的調(diào)度算法A如圖1所示。

圖1　算法A產(chǎn)生的調(diào)度算法

從而有CA=39

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

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

從而有COPT=36

2.2理論分析

對(duì)區(qū)間[a,b]長度 b-a作如下限定：

設(shè) Cij(j=1,2)為第i批工件在第j臺(tái)機(jī)器上的完成時(shí)間。

證明

證明

證：由引理1，2

證明

證：

證：由引理1，2可得

3實(shí)驗(yàn)與數(shù)值計(jì)算結(jié)果

對(duì)于近似算法A的目標(biāo)函數(shù)值A(chǔ)(BL)及相應(yīng)離線最優(yōu)算法的最優(yōu)值OPT(BL)，利用C語言編程。在數(shù)值計(jì)算中，對(duì)于n∈{10，30， 60，70，80，90，100，110，120，140，150}、m∈{5，6，8，10，20，30，40，50，60，80，100}的每種組合，算法A隨機(jī)產(chǎn)生A(BL)的5個(gè)算例，n表示每個(gè)算例中批的數(shù)量，每種情況作50次隨機(jī)模擬，工件的基本處理時(shí)間分別在[10,100]、[20,100]、[20,80]、[10,50]、[1,5]服從均勻分布。表1給出算法相應(yīng)最壞情況比值在各個(gè)比值區(qū)間上模擬出現(xiàn)的次數(shù)，其中比值區(qū)間被分成[1.0，1.1)、[1.1，1.2)、[1.2，1.3)、[1.3，1.4)、[1.4，1.5]。

由表1可得如下的分析結(jié)果：

1)程序計(jì)算結(jié)果表明：當(dāng)批中含有較多工件時(shí)，算法A的最壞情況比較理想，比值基本上分布在區(qū)間[1.0，1.1)中，說明算法性能較好。

2)啟發(fā)式算法對(duì)于批內(nèi)工件較多問題的改進(jìn)比那些批內(nèi)工件少的改進(jìn)更大，從而減小的最大完成時(shí)間更明顯。

表1　算法相應(yīng)最壞情況比值在各個(gè)比值

4結(jié)論

參考文獻(xiàn)

[1]TangLX,LiuJY,RongAY,etal.Areviewofplanningandschedulingsystemsandmethodsforintegratedsteelproduction[J].EuropeanJournalofOperationalResearch,2001,133:1-20.

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

[3]ChenB,VestjensA.P.A.Schedulingonidenticalmachines:HowgoodisLPTinanon-linesetting?[J].OperationsResearchLetters,1998,21(15):165-169.

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

[5]GrahamR.Boundsforcertainmultiprocessinganomalies[J].TheBellSystemTechnicalJournal,1966,45:1563-1581.

[6]EpsteinL.Anoteonon-lineschedulingwithprecedenceconstraintsonidenticalmachines[J].InformationProcessingLetters,2000,76:149-153.

[7]EpsteinL,SgallJ.Alowerboundforon-lineschedulingonuniformlyrelatedmachines[J].OperationsResearchLetters,2000,26(1):17-22.

[8]LuX,SittersRA,StougieL.Aclassofon-lineschedulingalgorithmstominimizetotalcompletiontime[J].OperationsResearchLetters,2003,31:232-236.

[9]PottsCN,KovalyovMY.Schedulingwithbatching:Areview[J].EuropeanJournalofOperationalResearch,2000,120:228-249.

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

[11]霍滿臣，陳忠菊.機(jī)器無等待工件具有區(qū)間限制的兩臺(tái)同構(gòu)并行機(jī)上批在線調(diào)度[J].沈陽工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2015，11(1)：90-92.

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

On-line Batch Scheduling with Constraint on Processing Time in Interval and Machine Waiting

HUO Man-chen1,CHEN Zhong-jiu2

(1.Foundation Department,Shenyang Engineering Institute,Shenyang 110136;2.Public Security Department,Liaoning Administrators College of Police and Justice,Shenyang 110161,Liaoning Province)

Abstract：It was studied with the problem of scheduling jobs in batches on-line on 2 identical parallel machines with objective to minimize the maximum completion time (the completion time of the last job: makespan),where batches arrived over list and every batch had exactly m jobs,and the processing timeswere constrained in some interval.When a batch arrivedthe jobswere scheduled in this batch immediately and irrevocably without the knowledge of later batches.The pre-emptionwas not allowed.An algorithm with scheduling jobs in every batch by LPT rule was proposed.When all the jobs in pre-batch were scheduledthe jobswere schedule in the following batch.The worst case was analyzed and the worst case ratio dependent with number of jobs in batch was given,and the conclusion was proved by program.

Key words：batch on-line list schedule;competitive ratio;identical parallel machines;batch list;maximum completion time;processing time

中圖分類號(hào)：TP301.6

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

文章編號(hào)：1673-1603(2016)01-0092-05

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

作者簡(jiǎn)介：霍滿臣(1963-)，男，遼寧海城人，教授，博士，主要從事系統(tǒng)工程與應(yīng)用數(shù)學(xué)方面的研究。

收稿日期：2015-10-14