線性退化且有獨立安裝時間的單機系列批排序

陳鳳梅, 羅成新

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

?

線性退化且有獨立安裝時間的單機系列批排序

陳鳳梅, 羅成新

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

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

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

0 引 言

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

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

1 問題描述

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

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

2 最小化最大完工時間

2.1 預備引理

(1)

證明 用數學歸納法。當m=1時,

滿足等式(1)。

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

那么當m=l+1時,有

證明 假設φ*是一個最優排序,其中批Bk中2個相鄰任務Jp,Jq滿足bp>bq,而φ是另外一個任務排序。這2個任務排序的區別是交換Bk中2個相鄰的任務Jp,Jq,即

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

證明 假設φ*是一個最優排序,交換Bu里的最后一個任務bp與Bv里的最后一個任務bp+1,得到一個新的排序φ,即

于是,有最優排序φ*的完工時間是

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

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

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

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

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

證明 假設在最優排序φ*中存在一個批Bp(1≤p

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

由于

因此有Cmax(φ)

2.2 最優算法

算法

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

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

第3步 按這些批自然生成的順序進行加工。

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

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

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

3 結 論

本文考慮的是任務帶有基本加工時間和線性退化且每個批都有獨立安裝時間的單機系列批排序問題,目標是最小化最大完工時間,對該問題給出了一個最優算法,時間復雜性是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。

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

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

1673-5862(2016)02-0165-05

O223

A

10.3969/ j.issn.1673-5862.2016.02.008