翟雯瑾，羅成新

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

具有截斷控制參數(shù)學習效應及退化效應加工時間依賴于資源的單機排序問題

翟雯瑾，羅成新

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

討論具有截斷控制參數(shù)學習效應和退化效應且工件的加工時間依賴于資源分配的單機排序問題。在凸資源消費函數(shù)條件下研究問題，每個任務有一個松弛工期窗口，任務的實際加工時間依賴于截斷控制參數(shù)、工件的開始加工時間。分別考慮了在工件的提前懲罰、延誤懲罰等費用受限的前提下，最小化資源費用；資源消耗總費受限的前提下，使帶有提前、延誤、交貨期開始時間、交貨期大小、最大完工時間及總完工時間加權和最小的單機排序問題。將問題轉化為指派問題，證明了該問題是在多項式時間內可解的，并分別給出了兩個多項式時間的最優(yōu)算法，并給出了一個算例。

排序；資源分配；截斷控制參數(shù)；退化效應；指派問題

經典排序中，任務的加工時間是固定的常數(shù)，但在實際生產中，任務等待或機器等原因都會引起任務加工時間的增長，即任務的實際加工時間與該任務的開始加工時間有關。然而考慮到學習效應、退化效應、資源分配等情況，任務的加工時間不再是固定不變的。通常情況下，給任務分配一定額度資源，任務的加工時間變小。文獻[2]討論了帶有學習和退化效應的單機排序問題，目標函數(shù)包括提前、延誤和工期的總費用。由于實際生產活動中的需要，帶有資源分配的問題逐漸引起關注，文獻[3-5]研究了關于資源分配的單機排序問題。文獻[6]在工件的加工時間與學習指數(shù)相關的凸函數(shù)下，研究了工件提前、延遲的工期指派問題。文獻[8-13]討論了帶有提前、延誤的工期指派問題。文獻[14]研究了具有截斷控制參數(shù)學習效應和退化效應且工件的加工時間依賴于資源分配的單機排序問題，并求得最大加工時間與總完工時間最小值時的最優(yōu)算法，本文與文獻[14]的差別在于目標函數(shù)不同。文獻[15]研究了具有維護活動及公共工期的加工時間依賴資源的單機排序問題。

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

本文在上述兩篇文獻的基礎上，研究了兩個問題。第一個問題是在資源消耗總費用受限的前提下，使帶有提前、延誤、交貨期開始時間、交貨期大小、最大完工時間及總完工時間加權和最小單機排序問題。第二個問題是在帶有提前、延誤、交貨期開始時間、交貨期大小、最大完工時間及總完工時間加權和受限的前提下，求得總資源消耗費用最小的單機排序問題。在兩個問題中，工件的實際加工時間是關于位置與資源的具有截斷參數(shù)學習效應與退化效應的線性函數(shù)與凸函數(shù)，通過將問題轉化為指派問題得到了多項式時間的最優(yōu)算法。

1 問題描述

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

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

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

(1)

(2)

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

2.1 重要結論

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

證明詳細證明見參考文獻[1]。

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

證明詳細證明與參考文獻[1]中證明類似。證畢。

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

(3)

證明 詳細證明與參考文獻[14]中證明類似。證畢。

由此可以得出

(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 問題(1)中給定工件的排序π=(J[1],J[2],…,J[n])可以得到最優(yōu)資源分配

(7)

證明 詳細證明與參考文獻[14]中證明類似。證畢。

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

Z1(π,u*)=U-l

(8)

其中Ωj由(6)決定。

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

(9)

則轉化為如下指派問題：

(10)

(11)

(12)

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

(13)

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

算法1

第一步 根據引理2，計算出k與l；

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

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

定理1 對于問題(1)可以通過求解指派問題在O(n3)時間內得到最優(yōu)解。

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

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

(14)

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

(15)

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

(16)

j=1,2,…,n

(17)

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

(18)

(19)

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

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

Z2(π,u*)=

(20)

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

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

(21)

考慮指派問題

(22)

(23)

(24)

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

(25)

算法2

第一步 根據引理2，計算出k與l；

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

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

定理2 對于問題(2)可以通過求解指派問題在O(n3)時間內求得最優(yōu)解。

證明證明過程與定理1證明過程類似。此處省略。證畢。

下面給出問題(1)與問題(2)各一個實例，說明算法的運算過程。

表1 例1的數(shù)據

表2 例1中vjr值

表3 例2中τjr值

3 結論

本文研究了具有截斷控制參數(shù)的單機排序問題。加工時間是關于資源的凸函數(shù)，分別給出目標函數(shù)求得最小值的最優(yōu)算法并證明問題是多項式時間內可解的。在工件的提前懲罰、延誤懲罰等總費用和受限的前提下，最小化資源費用的單機排序問題，確定最優(yōu)資源分配，通過將問題轉化為指派問題，證明問題在多項式時間內是可解，并給出了多項式時間算法。

[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]隋楠，羅成新.具有維護活動及公共工期的加工時間依賴資源的單機排序問題[J].沈陽航空航天大學學報，2016,33(6):90-96.

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

[17]王吉波,汪佳,牛玉萍.具有學習效應的單機可控加工時間排序問題研究[J].沈陽航空航天大學學報 2014,31(5):82-86.

[18]王吉波,郭苗苗，劉桓，等.具有依賴開工時間惡化工件的流水作業(yè)排序問題研究綜述[J].沈陽航空航天大學學報 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

遼寧省教育廳項目(項目編號：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

(責任編輯：劉劃 英文審校：劉勇進)