方 卓, 羅成新

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

帶有退化效應(yīng)的多個(gè)交貨期窗口單機(jī)排序問(wèn)題

方 卓, 羅成新

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

討論帶有退化效應(yīng)的多個(gè)交貨期窗口的單機(jī)排序問(wèn)題。其目標(biāo)函數(shù)有2種:第1種是帶有提前、延誤、交貨期的開(kāi)始位置、交貨期的大小及最大完工時(shí)間的總費(fèi)用;第2種是帶有提前、延誤、交貨期的開(kāi)始位置、交貨期的大小和所有工件完工時(shí)間之和的總費(fèi)用。目標(biāo)是找到多個(gè)交貨期窗口的最優(yōu)位置、交貨期的大小、屬于每個(gè)交貨期窗口的工件集合和工件的最優(yōu)排序,使目標(biāo)函數(shù)值最小。將該問(wèn)題轉(zhuǎn)化為指派問(wèn)題,并證明其多項(xiàng)式時(shí)間可解。

單機(jī); 退化效應(yīng); 多個(gè)交貨期窗口; 提前; 延誤; 最大完工時(shí)間; 完工時(shí)間之和

0 引 言

近年來(lái)有關(guān)交貨期窗口的問(wèn)題越來(lái)越受關(guān)注。交貨期窗口是指:如果工件在交貨期窗口之前完工則產(chǎn)生提前的費(fèi)用,在窗口之后完工則產(chǎn)生延誤的費(fèi)用,在窗口之內(nèi)完工則不會(huì)有任何費(fèi)用。Liman[1]等分析了帶有待定的公共交貨期的單機(jī)排序問(wèn)題。Mor等[2]研究了帶有維修活動(dòng)的交貨期單機(jī)排序問(wèn)題,并且每個(gè)工件都有一個(gè)大小相同的交貨期,目標(biāo)函數(shù)是包括提前、延誤、交貨期的開(kāi)始時(shí)間和交貨期大小的總費(fèi)用。Wang等[3]討論了帶有學(xué)習(xí)和退化效應(yīng)的單機(jī)排序問(wèn)題,目標(biāo)函數(shù)包括提前、延誤和工期的總費(fèi)用。Cheng[4,5]等研究了帶有退化效應(yīng)的工期指派問(wèn)題,目標(biāo)是確定最優(yōu)工期及最優(yōu)的排序使目標(biāo)函數(shù)值最小。文獻(xiàn)[6]研究了帶有退化效應(yīng)與維修活動(dòng)的工期指派問(wèn)題。文獻(xiàn)[7-12]討論了帶有提前、延誤的工期指派問(wèn)題。

本文討論了2種帶有退化效應(yīng)的多個(gè)交貨期窗口的單機(jī)排序問(wèn)題。給出了最優(yōu)解的性質(zhì),將2種問(wèn)題轉(zhuǎn)化為指派問(wèn)題,并證明其多項(xiàng)式時(shí)間可解。

給定m個(gè)交貨期窗口(1≤m≤n)。di(≥0)和wi(≥di)分別表示第i個(gè)交貨期窗口的開(kāi)始時(shí)間和結(jié)束時(shí)間,i=1,2,…,m。Di=wi-di表示第i個(gè)交貨期窗口的大小。如果m=1,則所有工件有一個(gè)共同的交貨期窗口,如果m=n,每個(gè)工件都有一個(gè)交貨期窗口。 定義Ii為第i個(gè)交貨期窗口的工件的集合,當(dāng)Jj∈Ii時(shí),工件Jj的交貨期窗口為[di,wi],i=1,2,…,m。目標(biāo)是求最優(yōu)的交貨期窗口的開(kāi)始時(shí)間d={d1,…,dm}、交貨期窗口大小D={D1,D2,…Dm}、屬于每個(gè)交貨期窗口工件的集合I={I1,I2,…Im}和最優(yōu)的工件排序,使以下兩種目標(biāo)函數(shù)值最小。

問(wèn)題1 帶有提前、延誤、交貨期開(kāi)始時(shí)間、交貨期大小及最大完工時(shí)間,目標(biāo)函數(shù)為

問(wèn)題2 帶有提前、延誤、交貨期的開(kāi)始時(shí)間、交貨期的大小及所有工件完工時(shí)間之和,目標(biāo)函數(shù)為

1 最優(yōu)解性質(zhì)

性質(zhì)1[13]存在最優(yōu)排序滿足工件的開(kāi)始加工時(shí)間從零時(shí)刻開(kāi)始,且相鄰工件之間沒(méi)有空閑。

2 最優(yōu)算法

引理1 問(wèn)題(1)中目標(biāo)函數(shù)可化簡(jiǎn)為

其中

證明 當(dāng)m=1時(shí),I={J[1],…,J[n]}

整理可得

其中

同理可得:m=2時(shí),

整理可得

其中

由此可以找出規(guī)律,即得到式(3)、式(4)。證畢。

基于上面的分析,給出一個(gè)最優(yōu)算法。

算法1

步驟2 通過(guò)式(4)計(jì)算λjr。

步驟3 通過(guò)解指派問(wèn)題(5)確定工件的最優(yōu)排序。

步驟4 計(jì)算最優(yōu)排序的工件的實(shí)際加工時(shí)間。

步驟5 根據(jù)性質(zhì)3計(jì)算最優(yōu)交貨期窗口的位置及交貨期的大小。

定理1 對(duì)于給定的常數(shù)m,如果分配給每個(gè)交貨期窗口的工件數(shù)是確定的,則根據(jù)算法1可求出問(wèn)題(1)的最優(yōu)解,且算法1的復(fù)雜性為O(n3)。

證明 算法1的最優(yōu)性可由以上討論所決定。步驟1、2、4和5皆能在線性時(shí)間內(nèi)執(zhí)行,步驟3轉(zhuǎn)化為指派問(wèn)題,所以需要O(n3)時(shí)間求解,因此算法復(fù)雜性為O(n3)。證畢。

引理2 對(duì)于給定的m個(gè)交貨期窗口,分配給每個(gè)交貨期窗口的工件數(shù)是確定的。則問(wèn)題(2)的目標(biāo)函數(shù)可化簡(jiǎn)為

其中

證明 與引理1類似。證畢。

基于上面的分析,給出一個(gè)最優(yōu)算法。

算法2

步驟2 通過(guò)(6)式計(jì)算φjr。

步驟3 通過(guò)解指派問(wèn)題(7)確定工件的最優(yōu)排序。

步驟4 計(jì)算最優(yōu)排序的工件的實(shí)際加工時(shí)間。

步驟5 根據(jù)性質(zhì)3計(jì)算最優(yōu)交貨期窗口的位置及交貨期的大小。

定理2 對(duì)于給定的常數(shù)m,如果分配給每個(gè)交貨期窗口的工件數(shù)是確定的,則根據(jù)算法2可求出問(wèn)題(2)的最優(yōu)解。且算法2的復(fù)雜性為O(n3)。

證明 算法2的最優(yōu)性可由以上討論所決定。步驟1、2、4和5皆能在線性的時(shí)間內(nèi)執(zhí)行,步驟3為指派問(wèn)題,所以需要O(n3)時(shí)間內(nèi)求解,因此問(wèn)題(2)算法的復(fù)雜性為O(n3)。證畢。

3 結(jié) 論

本文討論了2種帶有退化效應(yīng)的多個(gè)交貨期窗口的單機(jī)排序問(wèn)題。目標(biāo)是找到多個(gè)交貨期窗口最優(yōu)的位置、交貨期大小、屬于每個(gè)交貨期窗口的工件集合和工件的最優(yōu)排序,使目標(biāo)函數(shù)值最小。本文將問(wèn)題轉(zhuǎn)化為指派問(wèn)題,給出了最優(yōu)算法,并證明了在多項(xiàng)式時(shí)間內(nèi)可解。

[ 1 ]LIMAN S D, PANWALKAR S S, THONGMEE S. Common due window size and location determination in a single machine scheduling problem[J]. J Oper Res Soc, 1998,49(9):1007-1010.

[ 2 ]MOR B, MOSHEIOV G. Scheduling a maintenance activity and due-window assignment based on common flow allowance[J]. Int J Prod Econ, 2012,135(1):222-230.

[ 3 ]WANG Jibo , GUO Qian. A due-date assignment problem with learning effect and deteriorating jobs[J]. Appl Math Model, 2010,34(2):309-313.

[ 4 ]CHENG T C E, KANG Liying, Ng C T. Due-date assignment and single machine scheduling with deteriorating jobs[J]. J Oper Res Soc, 2004,55(2):198-203.

[ 5 ]CHENG T C E, KANG Liying, Ng C T. Single machine due-date scheduling of jobs with decreasing start-time dependent processing times[J]. Int T Oper Res, 2005,12(3):355-366.

[ 6 ]YANG S J, YANG D L, CHENG T C E. Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance[J]. Comput Oper Res, 2010,37(8):1510-1514.

[ 7 ]BAKER K R, SCUDDER G D. Sequencing with earliness and tardiness penalties: a review[J]. Oper Res, 1990,38(1):22-36.

[ 8 ]GORDON V S, TARASEVICH A A. A note: Common due date assignment for a single machine scheduling with the rate-modifying activity[J]. Comput Oper Res, 2009,36(2):325-328.

[ 9 ]BISKUP D, JAHNKE H. Common due date assignment for scheduling on a single machine with jointly reducible processing times[J]. Int J Prod Econ, 2001,69(3):317-322.

[10]SHABTAY D, STEINER G. The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times[J]. Ann Oper Res, 2008,159(1):25-40.

[11]KUO W H, YANG D L. A note on due-date assignment and single-machine scheduling with deteriorating jobs[J]. J Oper Res Soc, 2008,59(6):857-859.

[12]YANG S J, LEE H T, GUO J Y. Multiple common due dates assignment and scheduling problems with resource allocation and general position-dependent deterioration effect[J]. Int J Adv Manuf Tech, 2013,67(1/2/3/4):181-188.

[13]PANWALKAR S S, SMITH M L, SEIDMANN A. Common due date assignment to minimize total penalty for the one machine scheduling problem[J]. Oper Res, 1982,30(2):391-399.

[14]YANG D L, LAI C J, YANG S J. Scheduling problems with multiple due windows assignment and controllable processing times on a single machine[J]. Int J Prod Econ, 2014,150(4):96-103.

[15]GRAHAM R L, LAWLER E L, LENSTRA J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Ann Discrete Math, 1979,5(2):287-326.

Multipleduewindowsassignmentandschedulingproblemswithdeteriorationeffectonsinglemachine

FANGZhuo,LUOChengxin

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

This paper deals with the single machine multiple due windows assignment and scheduling problems with deterioration effect. We examine two models of the objective function.The first function is to minimize a total penalty function containing earliness, tardiness, due date windows and the makespan costs. The second function is to minimize a total penalty function containing earliness, tardiness, due date windows and total completion time costs. The objective is to determine the optimal due-windows location, due-windows size, the set of jobs assigned to each due window and the optimal sequence of jobs, thus to minimize the total costs. We formulate the problem as a assignment problem and show that the problem remains polynomial time solvable.

single machine; deteriorating effect; multiple due windows; earliness; tardiness; makespan; total completion time

2014-03-17。

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

方 卓(1989-),女,遼寧鐵嶺人,沈陽(yáng)師范大學(xué)碩士研究生;

: 羅成新(1958-),男,遼寧新賓人,沈陽(yáng)師范大學(xué)教授,博士,碩士研究生導(dǎo)師。

1673-5862(2014)04-0471-05

O223

: A

10.3969/ j.issn.1673-5862.2014.04.004