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

羅成新, 張 雪

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

?

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

羅成新, 張 雪

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

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

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

0 引 言

在傳統(tǒng)的排序問題中,工件的加工時(shí)間為固定和獨(dú)立的常數(shù)值。然而,在許多生產(chǎn)環(huán)境中經(jīng)常會(huì)遇到工件的加工時(shí)間隨時(shí)間變化的情況。自從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]。

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

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

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

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

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

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

1 問題描述

2 主要結(jié)論

(1)

其中n0=0。

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

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

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

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

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

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

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

在π中Bp,Bq的完工時(shí)間分別是

經(jīng)整理后得

假設(shè)au

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

其中

所以

又因?yàn)?/p>

所以有

顯然Cmax(π)

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

算法

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

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

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

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

證明 因?yàn)橛?/p>

3 結(jié) 語

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

[ 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。

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

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

1673-5862(2016)02-0160-05

O223

A

10.3969/ j.issn.1673-5862.2016.02.007