方 卓, 羅成新

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

帶有退化效應的多個交貨期窗口單機排序問題

方 卓, 羅成新

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

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

單機; 退化效應; 多個交貨期窗口; 提前; 延誤; 最大完工時間; 完工時間之和

0 引 言

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

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

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

問題1 帶有提前、延誤、交貨期開始時間、交貨期大小及最大完工時間,目標函數(shù)為

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

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

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

2 最優(yōu)算法

引理1 問題(1)中目標函數(shù)可化簡為

其中

證明 當m=1時,I={J[1],…,J[n]}

整理可得

其中

同理可得:m=2時,

整理可得

其中

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

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

算法1

步驟2 通過式(4)計算λjr。

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

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

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

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

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

引理2 對于給定的m個交貨期窗口,分配給每個交貨期窗口的工件數(shù)是確定的。則問題(2)的目標函數(shù)可化簡為

其中

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

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

算法2

步驟2 通過(6)式計算φjr。

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

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

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

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

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

3 結(jié) 論

本文討論了2種帶有退化效應的多個交貨期窗口的單機排序問題。目標是找到多個交貨期窗口最優(yōu)的位置、交貨期大小、屬于每個交貨期窗口的工件集合和工件的最優(yōu)排序,使目標函數(shù)值最小。本文將問題轉(zhuǎn)化為指派問題,給出了最優(yōu)算法,并證明了在多項式時間內(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。

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

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

: 羅成新(1958-),男,遼寧新賓人,沈陽師范大學教授,博士,碩士研究生導師。

1673-5862(2014)04-0471-05

O223

: A

10.3969/ j.issn.1673-5862.2014.04.004