羅成新, 張 雪

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

?

可控準(zhǔn)備時間和加工時間的系列分批排序

羅成新, 張 雪

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

在許多實際生產(chǎn)環(huán)境中,工件的加工時間不是固定不變的,由于工人或機(jī)器的工作時間較長,其加工工件的效率降低,使得實際的加工時間加長,也就產(chǎn)生了所謂的退化效應(yīng)。為考察退化效應(yīng)對工件排序的影響,討論在退化效應(yīng)的條件下,研究工件帶有可控準(zhǔn)備時間和可控加工時間的單機(jī)系列批排序問題。在退化效應(yīng)的條件下,工件的加工時間為它的開始時間的遞增函數(shù);所有的工件從一開始就被劃分為連續(xù)的批次,并在單機(jī)上分批進(jìn)行加工;在每批工件加工前,都有一個依賴于開始時間的準(zhǔn)備時間。目標(biāo)是確定工件的排序,并將其劃分成批,從而最小化最大完工時間和最大延誤,并且給出最優(yōu)算法來求解最小化最大完工時間和最大延誤問題。

系列分批; 排序; 退化效應(yīng); 單機(jī); 準(zhǔn)備時間; 可控

0 引 言

在傳統(tǒng)的排序問題中,工件的加工時間為固定和獨立的常數(shù)值。然而,在許多生產(chǎn)環(huán)境中經(jīng)常會遇到工件的加工時間隨時間變化的情況。自從Gupta等[1]以及Browne等[2]提出具有退化效應(yīng)的排序問題以來,不斷出現(xiàn)關(guān)于附加的研究各種具有退化效應(yīng)的排序問題。批量生產(chǎn),作為一種重要的加工方式,存在于許多排序環(huán)境中。批次的類型包括平行批和系列批。近年來,具有退化效應(yīng)的平行分批排序問題已在一些文獻(xiàn)中進(jìn)行了研究,其中包括Qi等[3],Li等[4]和Miao等[5-6]。

一個類似本文研究的排序問題是具有退化效應(yīng)的成組排序問題,其特點是成組技術(shù)的假設(shè)。在同樣的生產(chǎn)要求下,工件提前分組。最近的研究已考慮具有退化效應(yīng)的成組排序,包括Wu[7],Wang等[8-9],Zhang等[10],Yang[11]以及Bai[12]等。

有關(guān)本文的系列批加工的排序問題,關(guān)鍵地方有下面3處:

1) 在系列分批排序問題中,一個批內(nèi)任意一個工件的完成時間等于該批的最后完工時間,即等于該批中最后一個工件的完工時間;

2) 系列分批加工問題考慮機(jī)器容量;

3) 系列分批排序問題,考慮工件分批和批順序2個方面。

本文在Pei等[13]研究的基礎(chǔ)上進(jìn)行拓展,研究帶有退化準(zhǔn)備時間和退化加工時間的單機(jī)系列批排序問題,給出最優(yōu)算法來求解最小化最大完工時間和最大延誤問題。

1 問題描述

2 主要結(jié)論

(1)

其中n0=0。

證明 用歸納法來證明引理。當(dāng)m=1時,

所以當(dāng)m=1時,等式(1)成立。

假設(shè)當(dāng)m=l時,等式(1)也成立,即

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

所以當(dāng)m=l+1時結(jié)論也正確。綜上,引理1成立。

證明 由引理1得到引理2。

證明 假定π*是最優(yōu)排序,π是另一個排序,π*和π的區(qū)別在于2個工件Ju和Jv互換,即π*=(W1,Bp,Bq,W2),π=(W1,(Bp{Ju})∪{Jv},(Bq{Jv})∪{Ju},W2),這里W1和W2表示部分排序。對于π*而言,Bq的完工時間是

在π中Bp,Bq的完工時間分別是

經(jīng)整理后得

假設(shè)au

證明 假定在最優(yōu)排序π*中存在批Bp(1≤p

其中

所以

又因為

所以有

顯然Cmax(π)

基于上述分析,給出如下算法:

算法

第1步 把工件按照退化率ai非增的順序排列,使得a1≥a2≥…≥an,得到工件列表。

第2步 在工件列表中,如果工件數(shù)大于u,就把前u個工件放在一個批中,然后以此規(guī)律迭代。否則,將剩余的工件放在一批。

第3步 在t0時刻按照他們生成的順序按照批次進(jìn)行加工。

證明 基于引理2,3,4,算法能夠產(chǎn)生最優(yōu)解。另外,最佳完工時間的結(jié)果可以按照(1)式得到。此外,算法的時間復(fù)雜度是O(nlogn)。證畢。

證明 因為有

3 結(jié) 語

本文研究了具有退化準(zhǔn)備時間和退化加工時間的單機(jī)系列批排序問題。工件的加工時間是一個線性函數(shù),并且每批工件被加工之前,都有一個依賴于開始時間的準(zhǔn)備時間。目標(biāo)是確定工件的排序,并將其劃分成批,從而最小化最大完工時間。最后本文給出一個最優(yōu)算法求解最小化最大完工時間問題和最大延誤問題。

[ 1 ]GUPTAJND,GUPTASK.Singlefacilityschedulingwithnonlinearprocessingtimes[J].ComputIndEng, 1988,14(4):387-393.

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

[ 3 ]QI Xianglai, ZHOU Shiguo, YUAN Jinjiang. Single machine parallel-batch scheduling with deteriorating jobs[J]. Theor Comput Sci, 2009,410(8):830-836.

[ 4 ]LI Shisheng, NG C T, YUAN Jingjiang, et al. Parallelbatch scheduling of deteriorating jobs with release dates to minimize the makespan[J]. Eur J Oper Res, 2011,210(3):482-488.

[ 5 ]MIAO Cuixia, ZHANG Yuzhong, CAO Zhigang. Bounded parallelbatch scheduling on single and multimachines for deteriorating jobs[J]. Inf Process Lett, 2011,111(16):798-803.

[ 6 ]MIAO Cuixia, ZHANG Yuzhong, WU Cuilian. Scheduling of deteriorating jobs with release dates to minimize the maximum lateness[J]. Theor Comput Sci, 2012,462:80-87.

[ 7 ]WU C C, LEE W C. Singlemachine group-scheduling problems with deteriorating setup times and job processing times[J]. Int J Prod Econ, 2008,115(1):128-133.

[ 8 ]WANG Jibo, LIN Lin, SHAN Feng. Singlemachine group scheduling problems with deteriorating jobs[J]. Int J Adv Manuf Technol, 2008,39(7):808-812.

[ 9 ]WANG Jibo, GAO Wenjun, WANG Liyan, et al. Single machine group scheduling with general linear deterioration to minimize the makespan[J]. Int J Adv Manuf Technol, 2009,43(1):146-150.

[10]ZHANG Xingong, YAN Guangle. Singlemachine group scheduling problems with deteriorated and learning effect[J]. Appl Math Comput, 2010,216(4):1259-1266.

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

[12]BAI Jing, LI Zhirong, HUANG Xue. Singlemachine group scheduling with general deterioration and learning effects[J]. Appl Math Model, 2012,36(3):1267-1274.

[13]PEI Jun, LIU Xinbao, FAN Wenjuan, et al. Single machine serial-batching scheduling with independent setup time and deteriorating job processing times[J]. Optim Lett, 2015,9(1):91-104.

[14]XUAN Hua, TANG Lixin. Scheduling a hybrid flowshop with batch production at the last stage[J]. Comput Oper Res, 2007,34(9):2718-2733.

Single machine serial-batching scheduling with controllable setup time and job processing times

LUOChengxin,ZHANGXue

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

In the actual production environment, we often encounter the situation that the job processing times vary with time. Because operator and machine work for a long time, the machine efficiency is lower, so the actual processing time becomes longer, which produces deterioration effects. In this paper, we study the single machine serial-batching scheduling problem, where both setup and job processing times are controllable by deteriorating effect. With the assumption of deteriorating jobs, the job processing times are described by an increasing function of their starting times. All the jobs are first partitioned into serial batches and then processed on a single serial-batching machine. Before each batch is processed, deteriorating setup time is required. The objective is to determine the optimal sequence of jobs, and partition the jobs in batches to minimize the makespan and the maximum lateness. We present an optimal algorithm to solve the problem of minimizing the makespan and the maximum lateness.

serial-batching; scheduling; deteriorating jobs; single machine; setup time; controllable

2015-04-27。

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

羅成新(1958-),男,遼寧新賓人,沈陽師范大學(xué)教授,博士。

1673-5862(2016)02-0160-05

O223

A

10.3969/ j.issn.1673-5862.2016.02.007