王吉波,趙伯來

(沈陽航空航天大學 理學院,沈陽 110136)

基礎科學與工程

具有獨立安裝時間和惡化效應的單機成組排序問題研究

王吉波,趙伯來

(沈陽航空航天大學 理學院,沈陽 110136)

研究具有惡化效應且?guī)в袦蕚鋾r間的單機成組排序問題,其中同一組內工件的加工時間具有簡單線性惡化效應和獨立的常數(shù)準備時間,各組之間的調整時間為獨立的常數(shù)安裝時間。目標是確定同一組內工件的排列順序和各組之間的排列順序使所有工件的最大完工時間最小。對此問題給出了一個下界和一個啟發(fā)式算法,即上界,從而可以用分支定界算法來求此問題的最優(yōu)解。

排序;單機;惡化效應;準備時間;分支定界算法

在經(jīng)典排序中,假設工件的加工時間為常數(shù),但在許多實際問題中,工件的加工時間可能與其開工時間有著某種聯(lián)系。如在鋼鐵制造企業(yè)的連鑄-軋制生產(chǎn)過程中,煉鋼的基本單元是爐次,它是指同一座轉爐一次共同冶煉的鋼水。在煉鋼的連鑄階段,高溫熔融鋼水在連鑄機底部連續(xù)凝固成鋼坯。當?shù)却龝r間增加時(即加工開始時間延后),在連鑄機上加工的爐次的溫度將會降低,從而造成爐次加工時間的惡化(如劉鵬等[1])。具有惡化工件的這類問題在塑料工業(yè)、軍事以及醫(yī)療等其他方面也有著廣泛的應用(如Browne和Yechiali[2],Mosheiov[3-4],Ji和Cheng[5],Ng等[6],Sun等[7],Pei等[8])。關于工件加工時間具有惡化效應的綜述,可參考文獻Gawiejnowicz[9]。

隨著市場競爭的日趨激烈,為適應多品種小批量生產(chǎn)方式的需求,成組技術成為排序問題研究領域中的一類熱點問題。在成組排序問題中,工件可以分成“類似”工件的工件組。同組的工件連續(xù)加工時,不需要或需要較少的安裝時間;不同組的工件接連加工時,需要一定的或需要較多的安裝時間。柔性制造系統(tǒng)的發(fā)展給成組技術帶來新的生機和活力,這是因為數(shù)控機床的高度柔性可以適應加工越來越多的不同種類的工件,避免和大大減少工件的安裝時間,從而減少成本。近年來,國內外不僅重視成組技術的研究,更重視分組后組內工件的排序和組與組之間的排序。研究基于成組技術下的排序問題,對于提高柔性制造系統(tǒng)的生產(chǎn)能力具有重大的意義(如Potts和Van Wassenhove[10],Webster和Baker[11],唐國春等[12],Neufeld等[13])。

由以上兩方面,很自然地會考慮具有惡化工件的成組排序問題。Wu等[14]研究了組內工件加工時間和組間安裝(調整)時間都為惡化效應的排序問題,這里的惡化效應指的是加工時間(安裝時間),是開工時間的簡單函數(shù)。對最大完工時間問題和加權總完工時間問題,他們分別給出了多項式時間最優(yōu)算法。Wang等[15]研究了組內工件加工時間和組間安裝時間都為成比例線性惡化函數(shù),對最大完工時間問題和加權總完工時間問題,他們同樣給出了多項式時間最優(yōu)算法。

Wu等[16]研究了組內工件加工時間和組間安裝時間都為開工時間的線性惡化函數(shù)問題,其中組內工件惡化率相同,組間安裝時間的惡化率也相同。對最大完工時間極小化問題,他們給出了多項式時間最優(yōu)算法。對總完工時間極小化問題,他們證明了組內工件按基本加工時間的非減順序排列,當各組工件個數(shù)相同時,能夠得到多項式時間最優(yōu)算法。對于各組內工件個數(shù)不同的總完工時間問題,他們猜測是NP-難的,并且給出了一個啟發(fā)式算法。Wang等[17]研究了組內工件加工時間和組間安裝時間都為一般線性函數(shù)的問題,目標函數(shù)為極小化最大完工時間,對這個問題,他們給出了多項式時間最優(yōu)算法。Wei等[18]研究了組內工件加工時間和組間安裝時間都為開工時間的簡單惡化函數(shù)的排序問題,對加權完工時間平方和問題與加權等待時間平方和問題,他們分別給出了多項式時間最優(yōu)算法。Lee等[19]研究了組內工件加工時間和組間安裝時間都為開工時間的簡單惡化函數(shù)的排序問題,對加權誤工數(shù)問題,他們給出了一些優(yōu)勢性質,一個下界,一個啟發(fā)式算法和分支定界法。并用數(shù)值例子進行了模擬,結果表明這個分支定界法非常有效。Wang等[20]研究了組內工件帶有準備時間的簡單線性惡化排序問題,其中組間的安裝時間為獨立的,即與開工時間無關。對最大完工時間極小化問題的一種特殊情況,他們給出了多項式時間最優(yōu)算法。Xu等[21]研究了同Wang等[20]類似的問題,只是組內工件的加工時間為開工時間的成比例惡化函數(shù)。對最大完工時間極小化問題的一種特殊情況,他們給出了多項式時間最優(yōu)算法,他們還對一般情況給出了啟發(fā)式算法。

Wang等[20]研究的成果只是對一種特殊情況給出了多項式時間最優(yōu)算法,但對于一般情況并沒有給出什么結果,本文將繼續(xù)研究Wang等[20]的排序模型,對最大完工時間極小化問題的一般情況將給出兩個下界,從而提出分支定界精確算法。同時為了克服分支定界算法效率差的特性,提出了一個快速的啟發(fā)式算法。

1 提出描述

假設有n個工件分別屬于m個組,每一組Gi(1≤i≤m)中包含ni個工件{Ji1,Ji2,…,Jini},它們要在一臺機器上進行加工,并假設第i組第j個工件(即工件Jij)的準備時間為rij(rij>0)。若工件Jij的開工時間為t,則其加工時間為

pij=αijt

(1)

其中αij是工件Jij的惡化率,此模型稱為簡單線性惡化函數(shù)。我們假設同組工件必須放在一起連續(xù)加工,每組都有一個獨立的常數(shù)安裝時間Si>0。令Cij表示工件Jij的完工時間,Cmax=max{Cij|i=1,2,…,m;j=1,2,…,ni}表示所有工件的最大完工時間。我們的目標是確定同組內工件的排列順序和各組之間的排列順序,使所有工件的最大完工時間最小(也就是機器的利用率最高),利用三參數(shù)表示法,這個排序問題可表示為1|rij,pij=αijt,Si,GT|Cmax,其中,1表示單機,GT表示成組技術(Group technology)。

2 啟發(fā)式算法(上界)

引理1(Wang等[20]):

對于問題1|rij,pij=αijt,Si,GT|Cmax,如果各組之間的排列順序已經(jīng)給定,則在最優(yōu)排序中把同組內的工件按照準備時間rij從小到大排序,即隊組Gi,滿足

ri(1)≤ri(2)≤…≤ri(ni),i=1,2,…,m,j=1,2,…,ni

(2)

引理2(Wang等[20]):

由引理1和引理2,我們可以給出如下的啟發(fā)式算法,并作為分支定界法的上界。

啟發(fā)式算法(HA)

(1)各組內的工件順序按照準備時間從小到大排序ri(1)≤ri(2)≤…≤ri(ni),i=1,2,…,m。

(3)組間排序

①組間按照Si從小到大排序。

(4)選擇①至④目標函數(shù)值最小的排序為解。

3 下界

分支定界法的有效性受它下界的影響是很大的,下面我們將給出確定下界的方法。設前k組為已經(jīng)確定的排序,未排序的工件組有m-k組。已經(jīng)排序的部分稱之為序列PS,未排序的部分稱之為序列US,π是一個通過US追加PS獲得的完整的序列;即π=(PS,US)。

根據(jù)成組惡化模型,在序列π中第(k+1)組最后工件的完工時間為

(3)

類似地,在序列π中第(k+2)組最后工件的完工時間為

αk+2(l))

αk+2(l))

同理可得:在序列π中第m組工件的完工時間滿足

(4)

因此,序列π的最大完工時間滿足條件

(5)

引理3:對于表達式α1α2α3…αm-1αm+α2α3…αm-1αm+…+αm-1αm+αm,若要其取得最小值,則需將αi按非增的順序進行排列,即α1≥α2≥α3≥…≥αm。反之,將αi按非減的順序進行排列,則可以得到該表達式的最大值。

證明:用相鄰交換法很容易證明。

同理可推廣得到:若滿足α1≥α2≥α3≥…≥αm且S=min{S1,S2,S3…Sm}可得到表達式S1α1α2α3…αm+S2α2α3…αm+…+Smαm≥Sα1α2α3…αm+Sα2α3…αm+…+Sαm的最小值。根據(jù)引理3和公式(5)可得出第一個下界LB1:

(6)

根據(jù)式(3),在序列π中第(k+1)組最后工件的完工時間為

(7)

同理可得:在序列π中第m組工件的完工時間滿足

(8)

因此,根據(jù)公式(7)和(8)可得出第二個下界LB2。

(9)

為了得到更好的下界,我們取LB1和LB2的最大值,即

LB=max{LB1,LB2}

(10)

接下來我們舉個例子來幫助更好地理解分支定界法及下界。

解:啟發(fā)式算法(HA):

(1)組內工件排序按照rij從小到大排序得

G1:[J12→J11],G2:[J23→J22→J21],G3:[J31→J33→J32];G4:[J42→J41]

(3)組間排序

①組間按照Si從小到大排序得G1→G2→G3→G4,Cmax=3 939。

(4)選擇①至④目標函數(shù)值最小的排序為解,即G2→G3→G4→G1,Cmax=968(上界)。

則根據(jù)上文提到的計算下界的方法我們可以得到分支過程,如圖1所示。

圖1中內的數(shù)字代表計算出的下界的值,如果定義組G0為第零層的話,那么第一層最左側組G1旁邊的數(shù)字3 918就代表組G1固定的下界,計算過程如下:

由于組G1固定,那么根據(jù)公式(6)及公式(9)給出的計算下界方法得:

圖1 分支定界法過程

α(l))

=16×18×4×3+2×18×4×3+2×4×3+2×3=3 918

因為LB=max{LB1,LB2},所以LB=3 918,即G1固定的下界為3 918。其余下界的計算過程類似,在此不再一一列出。從圖1可以看出,最優(yōu)排序為G2→G1→G3→G4,最優(yōu)值為Cmax=939。

4 結論

本文研究了工件具有惡化效應和準備時間的單機成組排序問題,其中組和組之間有一個獨立的安裝(調整)時間。目的是求組內工件和組間工件的加工順序,并使最大完工時間(時間表長)最小,本文結合下界和上界給出了一個分支定界算法,從而能求出該問題的一個最優(yōu)排序,并給出相應的例子來說明分支定界算法(包括上界和下界)的計算過程。本文只是研究單機簡單線性惡化函數(shù)情況下的成組排序問題,可以將其延伸到平行機或流水作業(yè)等多機排序問題;加權完工時間和等復雜的目標函數(shù);或者考慮更一般的惡化函數(shù)的情況。

[1] 劉鵬,周曉曄,衣娜.帶有減少線性惡化效應的雙代理調度問題[J].系統(tǒng)工程學報,2011,26(3):387-392.

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

[3] MOSHEIOV G.V-Shaped policies to schedule deteriorating jobs [J].Operations Research,1991,39:979-991.

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

[5] JI M,CHENG T.C.E.Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan [J].European Journal of Operational Research,2010,202(1):90-98.

[6] NG CT,WANG J-B,CHENG T C E,et al.Flowshop scheduling of deteriorating jobs on dominating machines [J].Computers & Industrial Engineering.2011,61(3):647-654.

[7] SUN L-H,SUN L-Y,WANG M-Z,et al.Flow shop makespan minimization scheduling with deteriorating jobs under dominating machines [J].International Journal of Production Economics,2012,138(1):195-200.

[8] PEI J,PARDALOS PM,LIU X,et al.Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan [J].European Journal of Operational Research,2015,244(1):13-25.

[9] GAWIEJNOWICZ S.Time-dependent scheduling [M].Berlin Springer,2008.

[10]POTTS CN,VAN WASSENHOVE LN.Integrating scheduling with batching and lot-sizing:a review of algorithms and complexity [J].Journal of Operational Research Society 1992,43(5):395-406.

[11]WEBSTER S,BAKER KR.Scheduling groups of jobs on a single machine [J].Operations Research,1995,43(4):692-703.

[12]唐國春,張峰,羅守成,等.現(xiàn)代排序論[M].上海:上?？茖W普及出版社,2003.

[13]NEUFELD JS,GUPTA JND,BUSCHER U.A comprehensive review of flowshop group scheduling literature [J].Computers and Operations Research,2016,70(C):56-74.

[14]Wu CC,SHIAU YR,LEE WC.Single-machine group scheduling problems with deterioration consideration [J].Computers and Operations Research,2008,35(5):1652-1659.

[15]WANG J-B,LIN L,SHAN F.Single machine group scheduling problems with deteriorating jobs [J].International Journal of Advanced Manufacturing Technology 2008,39(7-8):808-812.

[16]WU CC,LEE WC.Single-machine group-scheduling problems with deteriorating setup times and job-processing times [J].International Journal of Production Economics,2008,115(1):128-133.

[17]WANG J-B,GAO W-J,Wang L-Y,et al.Single machine group scheduling with general linear deterioration to minimize the makespan [J].International Journal of Advanced Manufacturing Technology 2009,43(1-2):146-150.

[18]WEI C-M,WANG J-B.Single machine quadratic penalty function scheduling with deteriorating jobs and group technology [J].Applied Mathematical Modelling,2010,34(11):3642-3647.

[19]LEE W-C,LU Z-S.Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs [J].Applied Mathematics and Computation,2012,218(17):8750-8757.

[20]WANG J-B,HUANG X,WU Y-B,et al.Group scheduling with independent setup times,ready times,and deteriorating job processing times [J].International Journal of Advanced Manufacturing Technology 2012,60(5-8):643-649.

[21]XU Y-T,ZHANG Y,HUANG X.Single-machine ready times scheduling with group technology and proportional linear deterioration [J].Applied Mathematical Modelling 2014,38(1):384-391.

(責任編輯：劉劃 英文審校：劉勇進)

Researchonsingle-machinegroupschedulingwithindependentsetuptimesanddeteriorationeffect

WANG Ji-bo,ZHAO Bo-lai

(College of Science,Shenyang Aerospace University,Shenyang 110136,China)

This paper considers a single-machine group scheduling problem with deterioration effect and ready times,where the processing time of a job within each group is a simple linear deterioration effect,ready time of a job within each group is an independent constant,and the setup times of groups are independent constants.Our objective is to determine the schedule of jobs within each group and the schedule of groups to minimize the make-span.A branch-and-bound algorithm incorporating with a lower bound and a heuristic algorithm(i.e.,an upper bound) are proposed to find the optimal solution for the problem.

scheduling;single-machine;deterioration effect;ready time;branch-and-bound algorithm

2017-05-31

國家自然科學基金項目(項目編號：71471120)，沈陽航空航天大學大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(項目編號：X1611405)

王吉波(1975-),男,遼寧沈陽人,教授,博士后,主要研究方向：生產(chǎn)計劃與排序,E-mail:wangjibo75@163.com。

2095-1248(2017)04-0082-06

O223;C934

： A

10.3969/j.issn.2095-1248.2017.04.011