線性退化且有獨(dú)立安裝時間的單機(jī)系列批排序

陳鳳梅, 羅成新

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

?

線性退化且有獨(dú)立安裝時間的單機(jī)系列批排序

陳鳳梅, 羅成新

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

討論了任務(wù)帶有基本加工時間和線性退化且每個批都有獨(dú)立安裝時間的單機(jī)系列批排序問題。每個任務(wù)的基本加工時間都不相同,但是它們都有相同的退化率。任務(wù)實(shí)際的加工時間可以描述成關(guān)于其基加本工時間與開始時間的一次線性函數(shù),即Pi=bi+at,這里bi和a分別為任務(wù)Ji的基本加工時間和退化率,t則為任務(wù)Ji的開始時間。目標(biāo)是確定批的個數(shù)及批內(nèi)的任務(wù)排序,從而極小化最大完工時間。首先,所有的任務(wù)在加工之前先被劃分成一系列的批;然后,在單機(jī)上分批加工,每批在被加工之前都有一個獨(dú)立的常數(shù)安裝時間s;最后,在R-FBLDR算法的基礎(chǔ)上進(jìn)行了修改,得到了極小化最大完工時間的最優(yōu)算法,該算法的時間復(fù)雜性為O(nlogn),其中n為任務(wù)個數(shù)。

系列批; 排序; 安裝時間; 基本加工時間; 單機(jī); 線性退化

0 引 言

分批排序作為一類應(yīng)用背景十分廣泛的排序問題興起于上世紀(jì)90年代初,分批生產(chǎn)作為一個重要的生產(chǎn)方式存在于許多排序問題中,批的類型主要分為平行批和系列批。近年來,任務(wù)具有退化的平行批排序問題受到關(guān)注,已有一些論文進(jìn)行研究,包括Li等(2011)[1]和Miao等(2012)[2]。許多關(guān)于任務(wù)退化及系列批的生產(chǎn)方案出現(xiàn)在制造業(yè)領(lǐng)域,隨著制造業(yè)的飛速發(fā)展,如何有效地利用組合優(yōu)化工具,提出好的算法,縮短生產(chǎn)時間,提高生產(chǎn)效率無疑具有重要意義。

在傳統(tǒng)的排序問題中,通常假設(shè)任務(wù)的加工時間是固定的數(shù)(參見Baker (1974)[3]),然而由于生產(chǎn)環(huán)境等因素的影響,一個任務(wù)的加工時間可能由于退化效應(yīng)、學(xué)習(xí)效應(yīng)、資源分配等因素而發(fā)生變化。Browne等(1990)[4]首先引進(jìn)了帶有退化效應(yīng)的排序問題。已有許多關(guān)于系列批或退化任務(wù)的文章發(fā)表,與其比較相似的關(guān)于任務(wù)帶有退化的成組排序問題最近也受到關(guān)注,包括Wu等(2008)[5]、Zhang等(2010)[6]、Huang等(2011)[7]、Yang(2011)[8]。但目前還沒有太多關(guān)于系列批和退化任務(wù)這兩方面相結(jié)合的研究。然而,同時包括系列批和退化任務(wù)的情況在許多現(xiàn)實(shí)生產(chǎn)環(huán)境里不可避免。因此,本文研究關(guān)于系列批與線性退化相結(jié)合的排序模型。

1 問題描述

設(shè)有n個獨(dú)立的任務(wù)組成的集合{J1,J2,…,Jn}需要加工,所有任務(wù)在t=0時均已到達(dá)。在這些任務(wù)被加工之前首先要被劃分成一系列的批,然后在一臺機(jī)器上加工。在系列批里要求在相同批里的任務(wù)是連續(xù)加工的,且同一批里任務(wù)的完工時間被定義為這個批里最后一個任務(wù)的完工時間,每個批里的任務(wù)個數(shù)不能超過這個批的容量,即nk≤q,q表示任意批能容納的最多任務(wù)的個數(shù),任意一個批Bk被加工之前都有一個獨(dú)立的安裝時間s,因此批Bk中任務(wù)Ji的完工時間為,其中S(Bk)為Bk的開始時間。任務(wù)Ji的實(shí)際加工時間Pi是關(guān)于其開始時間t與基本加工時間bi的一次線性函數(shù),即

Pi=bi+at,i=1,2,…,n

2 最小化最大完工時間

2.1 預(yù)備引理

(1)

證明 用數(shù)學(xué)歸納法。當(dāng)m=1時,

滿足等式(1)。

假設(shè)m=l時,等式(1)成立,即

那么當(dāng)m=l+1時,有

證明 假設(shè)φ*是一個最優(yōu)排序,其中批Bk中2個相鄰任務(wù)Jp,Jq滿足bp>bq,而φ是另外一個任務(wù)排序。這2個任務(wù)排序的區(qū)別是交換Bk中2個相鄰的任務(wù)Jp,Jq,即

則Bk在排序φ*與φ下的完工時間分別為

證明 假設(shè)φ*是一個最優(yōu)排序,交換Bu里的最后一個任務(wù)bp與Bv里的最后一個任務(wù)bp+1,得到一個新的排序φ,即

于是,有最優(yōu)排序φ*的完工時間是

而Bu在排序φ中的完工時間為

任務(wù)Jp在排序φ里的完工時間表示如下:

Bv在排序φ下的完工時間為

從而得到排序φ的完工時間為

因?yàn)?1+a)n-p-1-(1+a)n-p<0,假設(shè)bp>bp+1,很容易看出C(φ*)>C(φ),與假設(shè)矛盾,因此bp≤bp+1,引理3得證。

證明 假設(shè)在最優(yōu)排序φ*中存在一個批Bp(1≤p

而新排序φ的最大完工時間為

由于

因此有Cmax(φ)

2.2 最優(yōu)算法

算法

第1步 把所有的任務(wù)按基本加工時間bi不減的順序標(biāo)號,即b1≤b2≤…≤bn,從而得到一個任務(wù)列表;

第2步 如果在一個任務(wù)列表里的任務(wù)個數(shù)超過其最大容量q,那么把前q個任務(wù)放在第1個批里,依次迭代,直到把所有的任務(wù)都劃分成批,然后把把剩下的不足q個任務(wù)放在一個批里;

第3步 按這些批自然生成的順序進(jìn)行加工。

定理 對于問題1|s-batch,Pi=bi+at,q

其中「n/q?表示n/q上取整數(shù),即「n/q?=[n/q]+1。

證明 基于引理2,3,4,可知算法1能夠產(chǎn)生最優(yōu)解,由式(1)能夠得到上面最優(yōu)的最大完工時間。定理證畢。

3 結(jié) 論

本文考慮的是任務(wù)帶有基本加工時間和線性退化且每個批都有獨(dú)立安裝時間的單機(jī)系列批排序問題,目標(biāo)是最小化最大完工時間,對該問題給出了一個最優(yōu)算法,時間復(fù)雜性是O(nlogn)。

[ 1 ]LISS,NGCT,CHENGTCE,etal.Parallel-batchschedulingofdeterioratingjobswithreleasedatestominimizethemakespan[J].EurJOperRes, 2011,210(3):482-488.

[ 2 ]MIAO C X, ZHANG Y Z, WU C L. Scheduling of deteriorating jobs with release dates to minimize the maxi-mumlateness[J]. Theor Comput Sci, 2012,462:80-87.

[ 3 ]BAKER K R. Introduction to sequencing and scheduling[M]. New York: Cambridge University Press, 1974.

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

[ 5 ]WU C C, SHIAU Y R, LEE W C. Single-machine group scheduling problems with deterioration consideration[J]. Comput Oper Res, 2008,35(5):1652-1659.

[ 6 ]ZHANG X G, YAN G L. Single-machine group scheduling problems with deteriorated and learning effect[J]. Appl Math Comput, 2010,216(4):1259-1266.

[ 7 ]HUANG X, WANG M Z, WANG J B. Single-machine group scheduling with both learning effects and deteri-orating jobs[J]. Comput Ind Eng, 2011,60(4):750-754.

[ 8 ]YANG S J. Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine[J]. App Math Model, 2011,35(8):4008-4016.

[ 9 ]GRAHAM R L, LAWLER E L, LENSTRA J K, et al. Optimization and approximation in deterministic seque-ncing and scheduling a survey[J]. Ann Discret Math, 1979,5:287-326.

[10]PEI J, LIU X B, PARDALOS P M, et al. Single machine serial-batching scheduling with independent setup time and deteriorating job processing times[J]. Optim Lett, 2015,9(1):91-104.

Single machine serial-batching scheduling with independent setup time and linear deteriorating jobs

CHENFengmei,LUOChengxin

(School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, China)

This paper considers the scheduling problems of a single serial-batching machine with independent setup time and linear deteriorating job processing time. Jobs have different basic processing times, but they have the same deterioration rate. The actual processing time ofJiis indicated as a linear function of its starting time and basic processing time, that is,Pi=bi+at, wherebiandaare the basic processing time and deterioration rate ofJi, the parametertis the starting time of jobJi. The objective is to determine the number of batches and the optimal sequence in batches, so as to minimize the makespan. Firstly, all the jobs are first partitioned into serial batches and then processed on a single serial-batching machine. Before each batch is processed, an independent constant setup time is required. Secondly, an optimal algorithm is presented to solve the problem of minimizing the makespan with modifying the Algorithm R-FBLDR, the time complicity of the algorithm isO(nlogn), wherenis the number of jobs to be scheduled.

serial-batching; scheduling; setup time; basic processing time; single machine; linear deteriorating

2015-06-02。

國家自然科學(xué)基金資助項目(11171050)。

陳鳳梅(1988-),女,湖南吉首人,沈陽師范大學(xué)碩士研究生; 通信作者: 羅成新(1958-),男,遼寧新賓人,沈陽師范大學(xué)教授,博士。

1673-5862(2016)02-0165-05

O223

A

10.3969/ j.issn.1673-5862.2016.02.008