陳鳳梅, 羅成新

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

?

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

陳鳳梅, 羅成新

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

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

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

0 引 言

分批排序作為一類應(yīng)用背景十分廣泛的排序問(wèn)題興起于上世紀(jì)90年代初,分批生產(chǎn)作為一個(gè)重要的生產(chǎn)方式存在于許多排序問(wèn)題中,批的類型主要分為平行批和系列批。近年來(lái),任務(wù)具有退化的平行批排序問(wèn)題受到關(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)時(shí)間,提高生產(chǎn)效率無(wú)疑具有重要意義。

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

1 問(wèn)題描述

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

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

2 最小化最大完工時(shí)間

2.1 預(yù)備引理

(1)

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

滿足等式(1)。

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

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

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

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

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

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

而B(niǎo)u在排序φ中的完工時(shí)間為

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

Bv在排序φ下的完工時(shí)間為

從而得到排序φ的完工時(shí)間為

因?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)排序φ*中存在一個(gè)批Bp(1≤p

而新排序φ的最大完工時(shí)間為

由于

因此有Cmax(φ)

2.2 最優(yōu)算法

算法

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

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

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

定理 對(duì)于問(wè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)的最大完工時(shí)間。定理證畢。

3 結(jié) 論

本文考慮的是任務(wù)帶有基本加工時(shí)間和線性退化且每個(gè)批都有獨(dú)立安裝時(shí)間的單機(jī)系列批排序問(wèn)題,目標(biāo)是最小化最大完工時(shí)間,對(duì)該問(wèn)題給出了一個(gè)最優(yōu)算法,時(shí)間復(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(11171050)。

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

1673-5862(2016)02-0165-05

O223

A

10.3969/ j.issn.1673-5862.2016.02.008