具有截?cái)嗫刂茀?shù)學(xué)習(xí)效應(yīng)及退化效應(yīng)加工時(shí)間依賴(lài)于資源的單機(jī)排序問(wèn)題

翟雯瑾，羅成新

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

具有截?cái)嗫刂茀?shù)學(xué)習(xí)效應(yīng)及退化效應(yīng)加工時(shí)間依賴(lài)于資源的單機(jī)排序問(wèn)題

翟雯瑾，羅成新

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

討論具有截?cái)嗫刂茀?shù)學(xué)習(xí)效應(yīng)和退化效應(yīng)且工件的加工時(shí)間依賴(lài)于資源分配的單機(jī)排序問(wèn)題。在凸資源消費(fèi)函數(shù)條件下研究問(wèn)題，每個(gè)任務(wù)有一個(gè)松弛工期窗口，任務(wù)的實(shí)際加工時(shí)間依賴(lài)于截?cái)嗫刂茀?shù)、工件的開(kāi)始加工時(shí)間。分別考慮了在工件的提前懲罰、延誤懲罰等費(fèi)用受限的前提下，最小化資源費(fèi)用；資源消耗總費(fèi)受限的前提下，使帶有提前、延誤、交貨期開(kāi)始時(shí)間、交貨期大小、最大完工時(shí)間及總完工時(shí)間加權(quán)和最小的單機(jī)排序問(wèn)題。將問(wèn)題轉(zhuǎn)化為指派問(wèn)題，證明了該問(wèn)題是在多項(xiàng)式時(shí)間內(nèi)可解的，并分別給出了兩個(gè)多項(xiàng)式時(shí)間的最優(yōu)算法，并給出了一個(gè)算例。

排序；資源分配；截?cái)嗫刂茀?shù)；退化效應(yīng)；指派問(wèn)題

經(jīng)典排序中，任務(wù)的加工時(shí)間是固定的常數(shù)，但在實(shí)際生產(chǎn)中，任務(wù)等待或機(jī)器等原因都會(huì)引起任務(wù)加工時(shí)間的增長(zhǎng)，即任務(wù)的實(shí)際加工時(shí)間與該任務(wù)的開(kāi)始加工時(shí)間有關(guān)。然而考慮到學(xué)習(xí)效應(yīng)、退化效應(yīng)、資源分配等情況，任務(wù)的加工時(shí)間不再是固定不變的。通常情況下，給任務(wù)分配一定額度資源，任務(wù)的加工時(shí)間變小。文獻(xiàn)[2]討論了帶有學(xué)習(xí)和退化效應(yīng)的單機(jī)排序問(wèn)題，目標(biāo)函數(shù)包括提前、延誤和工期的總費(fèi)用。由于實(shí)際生產(chǎn)活動(dòng)中的需要，帶有資源分配的問(wèn)題逐漸引起關(guān)注，文獻(xiàn)[3-5]研究了關(guān)于資源分配的單機(jī)排序問(wèn)題。文獻(xiàn)[6]在工件的加工時(shí)間與學(xué)習(xí)指數(shù)相關(guān)的凸函數(shù)下，研究了工件提前、延遲的工期指派問(wèn)題。文獻(xiàn)[8-13]討論了帶有提前、延誤的工期指派問(wèn)題。文獻(xiàn)[14]研究了具有截?cái)嗫刂茀?shù)學(xué)習(xí)效應(yīng)和退化效應(yīng)且工件的加工時(shí)間依賴(lài)于資源分配的單機(jī)排序問(wèn)題，并求得最大加工時(shí)間與總完工時(shí)間最小值時(shí)的最優(yōu)算法，本文與文獻(xiàn)[14]的差別在于目標(biāo)函數(shù)不同。文獻(xiàn)[15]研究了具有維護(hù)活動(dòng)及公共工期的加工時(shí)間依賴(lài)資源的單機(jī)排序問(wèn)題。

在大多數(shù)排序模型中，往往以最小化所需費(fèi)用為首要目標(biāo)。但在實(shí)際生產(chǎn)過(guò)程中，有時(shí)即便使得總費(fèi)用最小，也不能滿足生產(chǎn)者對(duì)費(fèi)用的預(yù)估最小值。因此生產(chǎn)者常常會(huì)事先給定預(yù)算以限制總費(fèi)用。文獻(xiàn)[1]與文獻(xiàn)[11]研究了多種工期下資源受限的單機(jī)排序問(wèn)題，并給出了在總費(fèi)用受限的前提下資源總數(shù)的最優(yōu)算法。

本文在上述兩篇文獻(xiàn)的基礎(chǔ)上，研究了兩個(gè)問(wèn)題。第一個(gè)問(wèn)題是在資源消耗總費(fèi)用受限的前提下，使帶有提前、延誤、交貨期開(kāi)始時(shí)間、交貨期大小、最大完工時(shí)間及總完工時(shí)間加權(quán)和最小單機(jī)排序問(wèn)題。第二個(gè)問(wèn)題是在帶有提前、延誤、交貨期開(kāi)始時(shí)間、交貨期大小、最大完工時(shí)間及總完工時(shí)間加權(quán)和受限的前提下，求得總資源消耗費(fèi)用最小的單機(jī)排序問(wèn)題。在兩個(gè)問(wèn)題中，工件的實(shí)際加工時(shí)間是關(guān)于位置與資源的具有截?cái)鄥?shù)學(xué)習(xí)效應(yīng)與退化效應(yīng)的線性函數(shù)與凸函數(shù)，通過(guò)將問(wèn)題轉(zhuǎn)化為指派問(wèn)題得到了多項(xiàng)式時(shí)間的最優(yōu)算法。

1 問(wèn)題描述

考慮如下的問(wèn)題：n個(gè)獨(dú)立且在零時(shí)刻到達(dá)的工件N={J1,J2,…,Jn}，需要在一臺(tái)機(jī)器上加工，在同一時(shí)刻機(jī)器最多只能加工一個(gè)工件，工件必須連續(xù)加工不允許中斷。在本文中，考慮兩種資源分配，分別為退化效應(yīng)與具有截?cái)嗫刂茀?shù)的學(xué)習(xí)效應(yīng)模型。在許多資源分配的問(wèn)題中，普遍采用線性資源消耗函數(shù)與凸資源消耗函數(shù)。本文里凸資源消耗函數(shù)模型中工件的實(shí)際處理時(shí)間表達(dá)式為

其中α>0,β>0,γ>0,δ1≥0,δ2≥0,μ≥0為給定常數(shù)。

其中α,β,γ,δ1,δ2,μ意義同上，Gj(>0)為資源分配的單位費(fèi)用。使用文獻(xiàn)[7]三參數(shù)表示法可將上述問(wèn)題分別表示為

(1)

(2)

2 問(wèn)題的最優(yōu)解

2.1 重要結(jié)論

引理1 對(duì)于任意給定的排序π=(J[1],J[2],…,J[n])，存在最優(yōu)的q1和q2，分別是第k個(gè)和第l個(gè)工件的完工時(shí)間(l≥k)，即

證明詳細(xì)證明見(jiàn)參考文獻(xiàn)[1]。

引理2 引理1中的k,l由以下兩式確定：q1=C[k]，k=[n(δ1-γ)/α]，q2=C[l]，l=[n(β-δ2)/β]。其中[x]表示不超過(guò)x的最大整數(shù)。

證明詳細(xì)證明與參考文獻(xiàn)[1]中證明類(lèi)似。證畢。

引理3 給定排序π=(J[1],J[2],…,J[n])，問(wèn)題(1)與問(wèn)題(2)中工件J[k](k=1,2,…,n)的實(shí)際加工時(shí)間為

(3)

證明 詳細(xì)證明與參考文獻(xiàn)[14]中證明類(lèi)似。證畢。

由此可以得出

(4)

其中

(5)

Ω1=ω1+cω2+c(1+c)ω3+…+c(1+c)n-2ωn

Ω2=ω2+cω3+c(1+c)ω4+…+c(1+c)n-3ωn

Ω3=ω3+cω4+c(1+c)ω5+…+c(1+c)n-4ωn

………………

Ωn-1=ωn-1+cωn

Ωn=ωn

(6)

2.2 最優(yōu)算法

引理4 問(wèn)題(1)中給定工件的排序π=(J[1],J[2],…,J[n])可以得到最優(yōu)資源分配

(7)

證明 詳細(xì)證明與參考文獻(xiàn)[14]中證明類(lèi)似。證畢。

將式(7)代入Z1(π,u*)，得到

Z1(π,u*)=U-l

(8)

其中Ωj由(6)決定。

為了求出式(13)最小值，考慮下述指派問(wèn)題。令

(9)

則轉(zhuǎn)化為如下指派問(wèn)題：

(10)

(11)

(12)

xjr=0或1j,r=1,2,…,n

(13)

因此，對(duì)于問(wèn)題(1)可以給出如下最優(yōu)算法。

算法1

第一步 根據(jù)引理2，計(jì)算出k與l；

第二步 根據(jù)式(9)計(jì)算出νjrj,r=1,2,…,n；

第三步 求解指派問(wèn)題(10)～(13)，得到最優(yōu)排序π*=(J[1],J[2],…,J[n])；

定理1 對(duì)于問(wèn)題(1)可以通過(guò)求解指派問(wèn)題在O(n3)時(shí)間內(nèi)得到最優(yōu)解。

證明上述分析保證了定理結(jié)論的正確性。算法1中的第一、四、五步可以在O(1)時(shí)間內(nèi)完成，第二、三步需要O(n3)時(shí)間內(nèi)完成，所以算法的時(shí)間復(fù)雜性為O(n3)。證畢。

引理5 問(wèn)題(2)對(duì)于給定的排序π=(J[1],J[2],…,J[n])可以得到最優(yōu)資源分配

(14)

證明 對(duì)于給定排序π=(J[1],J[2],…,J[n])，拉格朗日函數(shù)如下：

(15)

其中λ為拉格朗日乘子。對(duì)式(20)中的變量分別求偏導(dǎo),令其為零。得到最優(yōu)解的充分必要條件

(16)

j=1,2,…,n

(17)

由式(21)和式(22)得到

(18)

(19)

由式(23)和式(24)得到式(19)。證畢。

將式(19)代入Z2π,u*，得到

Z2(π,u*)=

(20)

其中Ωj由式(6)決定。

為了求出式(25)最小值，我們將問(wèn)題(2)化為指派問(wèn)題。令

(21)

考慮指派問(wèn)題

(22)

(23)

(24)

xjr=0 或 1j,r=1,2,…,n

(25)

算法2

第一步 根據(jù)引理2，計(jì)算出k與l；

第二步 根據(jù)式(21)計(jì)算出τjrj,r=1,2,…,n；

第三步 求解指派問(wèn)題(22)～(25)，得到最優(yōu)排序π*=(J[1],J[2],…,J[n])；

定理2 對(duì)于問(wèn)題(2)可以通過(guò)求解指派問(wèn)題在O(n3)時(shí)間內(nèi)求得最優(yōu)解。

證明證明過(guò)程與定理1證明過(guò)程類(lèi)似。此處省略。證畢。

下面給出問(wèn)題(1)與問(wèn)題(2)各一個(gè)實(shí)例，說(shuō)明算法的運(yùn)算過(guò)程。

表1 例1的數(shù)據(jù)

表2 例1中vjr值

表3 例2中τjr值

3 結(jié)論

本文研究了具有截?cái)嗫刂茀?shù)的單機(jī)排序問(wèn)題。加工時(shí)間是關(guān)于資源的凸函數(shù)，分別給出目標(biāo)函數(shù)求得最小值的最優(yōu)算法并證明問(wèn)題是多項(xiàng)式時(shí)間內(nèi)可解的。在工件的提前懲罰、延誤懲罰等總費(fèi)用和受限的前提下，最小化資源費(fèi)用的單機(jī)排序問(wèn)題，確定最優(yōu)資源分配，通過(guò)將問(wèn)題轉(zhuǎn)化為指派問(wèn)題，證明問(wèn)題在多項(xiàng)式時(shí)間內(nèi)是可解，并給出了多項(xiàng)式時(shí)間算法。

[1] LI GANG,LUO MEILING,ZHANG WENJIE,et al.Single-machine due-window assignment scheduling based on flow allowance,learning effect and resource allocation[J].International Journal of Production Research,2015,53(4):1228-1241.

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

[3] LU Y Y,LI G,WUB,et al.Optimal due-date assignment problem with learning effect and resource-dependent processing times[J].Optimization Letters,2014,8(1):113-127.

[4] WANG X Y,WANG J J.Single-machine due-date assignment problem with deteriorating jobs and resource-dependent processing times[J].International Journal of Advanced Manufacturing Technology,2013,67(1-4):255-260.

[5] WANG J B,WANG J J.Research on scheduling with job-dependent learning effect and convex resource-dependent processing times[J].International Journal of Production Research,2015,53(19):1-11.

[6] WANG JIBO,WANG JIANJUN.Research on scheduling with job-dependent learning effect and convex resource-dependent processing times[J].Int J Pro Res,2015,53(19):5826-5836.

[7] GRAHAM R L,LAWLER E L,LENSTRA J K,et al.Optimization and approximation in deterministic sequencing and scheduling:A survey[J].Annals of Discrete Mathematics,1979,5(1):287-326.

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

[9] 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.

[10]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.

[11]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.

[12]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.

[13]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].International Journal of Advanced Manufacturing Technology,2013,67(1-4):181-188.

[14]WANG J B,LIU M Q,YIN N,et al.Scheduling jobs with controllable processing time,truncated job-dependent learning and deteriorations effects[J].Journal of Industrial and Management Optimization 2017,13(2):1025-1039.

[15]隋楠，羅成新.具有維護(hù)活動(dòng)及公共工期的加工時(shí)間依賴(lài)資源的單機(jī)排序問(wèn)題[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào)，2016,33(6):90-96.

[16]王吉波，劉璐，許揚(yáng)濤，等.具有惡化工件的不同工期指派問(wèn)題研究[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào)，2013,30(5):83-87.

[17]王吉波,汪佳,牛玉萍.具有學(xué)習(xí)效應(yīng)的單機(jī)可控加工時(shí)間排序問(wèn)題研究[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào) 2014,31(5):82-86.

[18]王吉波,郭苗苗，劉桓，等.具有依賴(lài)開(kāi)工時(shí)間惡化工件的流水作業(yè)排序問(wèn)題研究綜述[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào) 2016,33(3):1-10.

Singlemachineschedulingproblemwithprocessingtimeofajobdependenttruncatedcontrollearningeffectanddeteriorationeffectandresource

ZHAI Wen-jin,LUO Cheng-xin

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

We study a single machine scheduling problem with truncated job-dependent learning effect and deterioration effects and processing time dependent on resource.The actual processing time of a job is a convex function of the resource amount allocated to it.Each job has a slack due-window.The actual processing time of each job depends on a truncated control parameter,the starting time and the resource amount allocated to it.Two single scheduling problems are studied.The first is to minimize total cost of early and tardy job,the start time,size of each due-window,makespan and total completion time,assume that total resource is limited by a given constant.The second is to minimize the total resource cost under the condition that a total objective value is limited by a given constant.We show that the problem is polynomial solvable by transforming this it into an assignment problem.Two polynomial time optimal algorithms are presented.An example is given to show the algorithm.

scheduling;resource allocation;truncated control parameter;deterioration effect;assignment problem

2017-07-04

遼寧省教育廳項(xiàng)目(項(xiàng)目編號(hào)：L2014433)

翟雯瑾(1993-),女,遼寧鞍山人,碩士研究生，主要研究方向：組合最優(yōu)化，E-mail:724482159@qq.com;羅成新(1958-),男,遼寧新賓人，教授,博士,主要研究方向：組合最優(yōu)化,E-mail:luochengxin@163.com。

2095-1248(2017)05-0086-06

Q221.7

A

10.3969/j.issn.2095-1248.2017.05.013

(責(zé)任編輯：劉劃 英文審校：劉勇進(jìn))