具有截斷控制參數學習效應的單機排序問題

羅成新, 翟雯瑾

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

具有截斷控制參數學習效應的單機排序問題

羅成新, 翟雯瑾

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

討論具有截斷控制參數學習效應和退化效應且工件的加工時間依賴于資源分配的單機排序問題。分別在線性資源和凸資源消費函數條件下研究問題。每個任務有一個松弛工期窗口,任務的實際加工時間依賴于截斷控制參數、工件的開始加工時間和分配方案的資源數量。目標是求出任務的最優排序、每個任務的工期窗口位置、最優資源分配,使由任務總提前、延誤、工期窗口的開始時間、窗口大小、時間表長、總完工時間及資源總費用的加權和最小。將問題轉化為指派問題,證明了該問題是在多項式時間內可解的,并分別給出了2個多項式時間的最優算法。

排序; 資源分配; 截斷控制參數; 退化效應; 指派問題

0 引 言

近20年,由于現代運營管理等產業的引進,具有工期的排序問題陸續進入人們的視野。如果一個工件在它的工期之前完成加工,那么它需要承擔一部分的提前懲罰費用;相應的,如果一個工件在它的工期之后完成加工,那么它需要承擔一部分的延誤懲罰費用。Li[1]研究了工件的交貨期與工件位置相關的單機排序問題。

經典排序模型中,任務的加工時間通常都是固定的常數,然而考慮到學習效應、退化效應、資源分配等情況,任務的加工時間不再是固定不變的。Cheng[2-3]研究帶有退化效應的工期指派問題,目標是確定最優工期及最優的排序使目標函數值最小。由于實際生產需要,具有學習效應與退化效應問題越來越受重視。Yang[4]等研究了帶有退化效應與維修活動的工期指派問題。文獻[5-13]討論了帶有提前、延誤的工期指派問題。

Wang[13]等研究了具有截斷控制參數學習效應和退化效應且工件的加工時間依賴于資源分配的單機排序問題,并求得最大加工時間與總完工時間最小值時的最優算法。本文在文獻[13]的基礎上,研究工件實際加工時間的線性資源消耗函數與凸資源消耗函數下的帶有提前、延誤、交貨期開始時間、交貨期大小、最大完工時間、總完工時間及總資源分配的總費用的最小化問題。工件的實際加工時間是關于位置與資源的具有截斷參數學習效應與退化效應的線性函數與凸函數,通過將問題轉化為指派問題得到了多項式時間的最優算法。

1 問題描述

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

其中:pj為工件Jj的基本加工時間;工件Jj的學習指數為aj(aj≤0);工件Jj的截斷控制參數為bj(00)。

本文里凸資源消耗函數模型中工件的實際處理時間表達式如下:

其中:α>0,β>0,γ>0,δ1≥0,δ2≥0,μ≥0為給定常數;Gj(>0)為資源分配的單位費用。

使用三參數[7]表示法可將上述問題分別表示為

(1)

(2)

2 最優算法

因此引理結論成立。證畢。

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

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

證明 僅就問題(1)來證明引理,問題(2)可用相同方法證明。如果最優排序π不具有這個性質,即

1) 工件J[j](j=1,2,…,k+1) 提前的總費用為

2) 工件J[j](j=l+2,l+3,…,n)延遲的總費用為

3) 窗口開始時間總費用為

4) 窗口大小的總費用為

因此,總費用可以表示為Z=AΔ1+BΔ2+C,其中

顯然A,B與C都是不依賴Δ1與Δ2的常數。要使Z最小必須使

因此,對于任意給定的排序π,存在最優的q1和q2,分別是第k個和第l個工件的完工時間。證畢。

證明 給出一個適合于引理3的最優排序,考慮以下的費用:

1) 工件J[j](j=1,2,…,k)提前的總費用為

2) 工件J[j](j=l+2,l+3,…,n)延遲的總費用為

3) 窗口開始時間總費用為

4) 窗口大小的總費用為

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

(3)

證明 用數學歸納法,此處省略。證畢。

根據引理3、4與5,可以得出

(4)

其中

(5)

(6)

對于任意的排序π=(J[1],J[2],…,J[n]),由式(4)可以得出最優資源為

(7)

為了求出最優解,將問題(1)轉化為指派問題。對j,r=1,2,…,n令

(8)

(9)

(10)

(11)

(12)

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

算法1

第1步 根據引理4,計算出k與l;

第2步 根據(8)計算出λjr,j,r=1,2,…,n;

第3步 求解指派問題(9)-(12),得到最優排序π*=(J[1],J[2],…,J[n]);

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

證明 上述分析保證了定理結論的正確性。算法1中的第1、4、5步可以在O(1)時間內完成,第2、3步需要O(n3)時間內完成,所以算法的時間復雜性為O(n3)。證畢。

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

(13)

由此可以得出

(14)

引理7 問題(2)對于工件排序π=(J[1],J[2],…,J[n]),最優資源分配如下:

(15)

將式(15)代入式(14)得

(16)

為了求出最優解,將問題(2)化為指派問題。引入

(17)

則問題(2)轉化為如下指派問題:

(18)

(19)

(20)

(21)

因此,對于問題(2)可以給出如下最優算法。

算法2

第1步 根據引理4,計算出k與l;

第2步 根據(17)計算出?jr,j,r=1,2,…,n;

第3步 求解指派問題(18)～(21),得到最優排序π*=(J[1],J[2],…,J[n]);

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

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

3 結 論

本文研究了具有截斷控制參數的單機排序問題。加工時間是關于資源的線性函數與凸函數,目標是求帶有提前、延誤、交貨期開始時間、交貨期大小、最大完工時間、總完工時間及總資源分配的總費用的最小值。通過將問題轉化為指派問題,證明問題多項式時間內是可解,并給出了多項式時間最優算法。

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

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

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

[ 5 ]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:287-326.

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

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

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

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

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

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

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

[13]WANG Jibo,LIU M Q, YIN N,et al. Scheduling Jobs with Controllable Processing Time, Truncated Job-Dependent Learning and Deteriortion Effects[J]. Journal of Industrial and Management Optimization, 2017,13(2):1025-1039.

Single machine scheduling problem with the truncated control learning effect

LUOChengxin,ZHAIWenjin

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

In this paper, we study a single machine scheduling problem with truncated job-dependent learning effect and deterioration effects and processing time dependent on resource. Each job has a slack due-window. The actual processing time of a job is a linear function and a convex function of the resource amount allocated to it, respectively. The actual processing time of each job depends on a truncated control parameter, the starting time and the resource amount allocated to it. The objective is to find the optimal sequence of jobs, slack due-window and the optimal resource allocation scheme to minimize the weighted costs of earliness, tardiness, the starting of due-window, and the size of the due windows, makespan, the total completion times and the resource allocation. We show that the problem is polynomial solvable by transforming this it into an assignment problem. Two polynomial time optimal algorithms are presented, respectively.

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

2017-06-02。

國家自然科學基金資助項目(11171050); 遼寧省教育廳科學研究一般項目(L2014433)。

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

1673-5862(2017)03-0305-06

O223

A

10.3969/ j.issn.1673-5862.2017.03.009