具有學習效應且加工時間可控的單機排序問題

王 方，趙傳立

（沈陽師范大學 數學與系統科學學院，沈陽 110034）

帶有可控加工時間的排序問題［1－10］，自1980年以來備受關注，并取得了許多研究成果。本文將學習效應與可控加工時間相結合，拓展了文獻［7］的主要結果。問題可描述如下。

設有n個相互獨立的工件的集合，記為｛J1，J2，…，Jn｝，工件在0時都已到達，且加工過程中中斷不被允許。工件J［j］的正常加工時間為P［j］，需要確定工件的加工順序、劃分、工期和資源分配量，極小化一個包含加權總誤工數、工期分派、最大完工時間，和總資源消耗的費用函數。即目標函數為以下形式：

其中，Cj是工件Jj的完工時間是最大完工時間。Uj是工件Jj的延誤指示變量，即當Cj＞dj時，置Uj＝1；否則，置Uj＝0，dj≥0是工件Jj的工期。αj是工件Jj的延誤費用，非負參數α和β分別表示工期的單位費用和最大完工時間的費用。uj是分配到工件Jj上的資源量，vj是分配到工件Jj上的資源量的單位費用。

研究帶有以下兩種工期分派方法的問題。

1）CON型：共同工期分派方法。這里所有工件都分派一個共同工期，即dj＝d，j＝1，2，…，n

2）SLK型：松弛工期分派方法。這里所有工件都有一個相同的松弛時間，即dj＝pj＋slk，這里slk≥0是一個確定的變量。

文獻［11］考慮了一種機器具有學習效應的模型，當工件Jj排在序列的第r個位置時，其實際加工時間為pj＝，aj≤0是一個與工件相關的學習指標。本文中工件Jj的實際加工時間為：

I線性資源消耗函數：

凸資源消耗函數：

式中，k是一個正的常數。

1 預備結論

容易驗證，帶有CON型和SLK型工期分派方法的加工時間為常量的排序問題中的某些結論，仍然可以推廣到可控加工時間的情形。并且帶有SLK型的問題與CON型類似，因此以下本文均以CON型為例討論。

在CON型工期分派方法下，工件可以劃分為2個相鄰的集合：

1）集合E。這里所有工件的加工時間總和定義為工期d的值，且這里的工件都在它的工期前完工，故稱E為提前工件集合。

2）集合T。這里所有工件都在它的工期后完工，故稱T為延誤工件集合。

引理1 在CON型工期分派方法下，存在一個最優排序，任意兩個工件的加工過程之間都沒有空閑時間，且第一個工件的開始時間為零。

文中帶有［j］的下標均表示工件排在第j個位置。

引理2 存在一個最優排序，在CON型工期分派方法下，集合E排在集合T前。

2 線性資源消耗函數的解

在CON型工期分派方法下，當資源分配與工件所排位置確定后，工件的加工時間被固定，就簡化為找最優劃分τ＊和工期d，極小化這個問題已被文獻［12］解決，并在O（n）時間內給出以下算法。

算法1：

步驟2 集合E排在T之前，并且每個集合內部的次序無關。

步驟3 最優工期為集合E的完工時間，即

由算法1可知，最優工期和工件的劃分是由加工時間決定的。然而，當加工時間由式（2）和式（3）確定時，意味著最優工期和工件的劃分還將與工件所排位置和分配的資源有關。

由于對任意一種給定的劃分、排序和資源分配，相應的最優工期就可以確定，因此，以下這個問題旨在確定最優的劃分、排序和資源分配。

對任意一個給定的劃分和排序，目標函數式（1）可變形為：

假定｜E｜＝l，｜T｜＝n－l.則上式又可變形為：

當加工時間為一個線性資源消耗函數式（2）時，目標函數式（4）變為：

對于SLK型工期分派方法，帶有固定加工時間的相關結論文獻［8］中已做了詳細分析。

引理3 在CON型工期分派方法下，對于任意給定的劃分和工件序列，最優資源分配作為劃分和工件序列的一個函數，可以這樣得到：

證明 對式（5）關于u［j］求導得證。

由以上分析可知，對于任意給定的劃分和排序，最優資源分配都可以由引理3求出，那么，這個問題就簡化為求一個最優劃分和最優序列的排序問題。

然而，對于任意一個給定的劃分，最優排序可以通過在O（n3）時間內解一個指派問題得到，分析如下：

根據前面在CON型工期分派方法下假定的劃分，對于目標函數（5）式，當l給定時，令

其中，cij（l）依目標函數式（5）中Wj的不同而不同。

定義xij為一個0－1變量，當工件Ji排到第j個位置時，xij＝1；否則，xij＝0。對于目標函數式（5），指派問題可表示如下：

引理4 對于目標函數式（1），任意給定一種劃分τ，在CON型工期分派方法下，當加工時間由式（2）確定時，相關最優排序可以通過解一個指派問題在O（n3）時間內得到。

根據以上的分析，對于任意一個給定的劃分，都可以通過解指派問題找到最優排序。因此，這個問題又進一步簡化為找最優劃分τ＊的問題。

因為l的值有n種可能的取法，所以為了找最優的劃分，只有取遍所有l可能值并解相應的l值對應的指派問題，才能得到這個問題的最優解。這個問題的最優解總結為算法2。

算法2 求解帶有CON型工期分派方法的線性資源消耗函數最優解的算法。

初始 置Z＊＝∞，l＝0。

步驟1 當l≤n時：

步驟1.1 通過式（7）計算cij（l）的值；

步驟1.2 解指派問題P1（l）：，確定工件的最優排序π＊＝［1］，［2］，…，［n］和極小化費用Z（l）；

步驟1.3 如果Z（l）＜Z＊，那么，置Z＊＝Z（l），l＊＝l，π＊（l＊）＝π＊（l）；

步驟1.4l＝l＋1。

步驟2 當l＝l＊，π＊（l）＝π＊（l＊）時，通過引理3計算最優資源分配u＊（l），通過式（2）計算最優加工時間

定理1 算法2在O（n4）時間內解決了在CON型工期分派方法下，這個問題的目標函數為一個線性資源消耗函數時的最優解。

3 凸資源消耗函數的解

當加工時間為一個凸資源消耗函數式（3）時，代入式（4），則目標函數變為以下形式：

由目標函數式（8）可以看出，在CON型工期分派方法下，任意給定一種劃分和排序，當加工時間為一個凸資源消耗函數時，這個問題變為一個關于資源分配的凸函數。因此，最優資源分配可描述如下：

引理5 最優資源分配u＊（π，l），作為劃分和工件序列的一個函數，是：

CON型：

把引理5中的最優資源分配分別代入目標函數式（8），得到

由于對于任意給定的劃分和排序，最優資源分配都可以通過引理5得到。因此，這個問題又簡化為找最優劃分和排序的問題。

此時，任意給定的一種劃分，最優排序仍然可以通過解指派問題，在O（n3）時間內得到。分析如下：

根據前面在CON型工期分派方法下假定的劃分，對于目標函數式（7），當l給定時，令

其中，cij（l）依目標函數（9）式中Wj的不同而不同。

定義xij為一個0－1變量，當工件Ji排到第j個位置時，xij＝1；否則，xij＝0。對于目標函數（9）式，指派問題的表示同前面P1（t）的形式，不妨記為P2（t）。

引理6 對于這個問題，任意給定一種劃分τ，在CON型工期分派方法下，當加工時間由式（3）確定時，相關最優排序可以通過解一個指派問題在O（n3）時間內得到。

由以上的分析，有下面的結論

對于任意一個給定的劃分，都可以通過解指派問題找到最優排序。因此，這個問題的最優解又進一步簡化為找最優劃分τ＊的問題。

同樣，因為l的值有n種可能的取法，只有取遍的所有l的可能值并解相應的l值對應的指派問題，才能得到這個問題的最優解。因此，當加工時間為一個凸資源消耗函數時，在CON型工期分派方法下，這個問題的最優解總結為算法3。

算法3 求解帶有CON型工期分派方法的凸資源消耗函數最優解的算法。

初始 置Z＊＝∞，l＝0。

步驟1 當l≤n時：

步驟1.1 通過式（10）計算cij（l）的值；

步驟1.2 解指派問題P2（l），確定工件的最優排序π＊＝［1］，［2］，…，［n］和極小化費用Z（l）；

步驟1.3 如果Z（l）＜Z＊，那么，置Z＊＝Z（l），l＊＝l，π＊（l＊）＝π＊（l）；

步驟1.4l＝l＋1。

步驟2 當l＝l＊，π＊（l）＝π＊（l＊）時，通過引理5計算最優資源分配u＊（l），通過式（3）計算最優加工時間

定理2 算法3在O（n4）時間內解決了在CON型工期分派方法下，這個問題的目標函數為一個凸資源消耗函數時的最優解。

4 結 語

現實生活中，學習效應是普遍存在的，本文將學習效應與可控加工時間相結合，使得問題更具有廣泛應用性和實際意義。這個問題在多機環境下或者加工時間為其他資源消耗函數的情形有待進一步研究。

［1］LEYVAND Y，SHABTAY D，STEINER G A.A unified approach for scheduling with conwex resource consumption functions using positional penalties［J］.Eur J Oper Res，2010，206（2）：301－312.

［2］SU L H，LIEN C Y.Scheduling parallel machines with resource dependent processing times［J］.Int J Prod Econ，2009，117（2）：256－266.

［3］SHABTAY D，STEINER G.A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates［J］.J Sched，2011，14（5）：455－469.

［4］SHABTAY D，STEINER G.A survey of scheduling with controllable processing times［J］.Disc Appl Math，2007，155（13）：1643－1666.

［5］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.

［6］CHENG T C E，OGAZ C，QI X D.Due－date assignment and single scheduling with compressible processing times［J］.Int J Prod Econ，1996，43（1）：29－35.

［7］SHABTAY D，STEINER G.Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine［J］.Manuf Serv Oper Manage，2007，9（3）：332－350.

［8］BISKUP D.Single－machine scheduling with learning considerations［J］.Eur J Oper Res，1999，115（1）：173－178.

［9］BISKUP D.A state－of－the－art review on scheduling with learning effect［J］.Eur J Oper Res，2008，188（2）：315－329.

［10］WANG D，WANG M Z，WANG Jibo.Single－machine scheduling with learning effect and resource－dependent processing times［J］.Comput indust Eng，2010，59（3）：458－462.

［11］MOSHEIOV G，SIDNE J B.Scheduling with general job－dependent learning curves［J］.Eur J Oper Res，2003，147（3）：665－670.

［12］KAHLBACHER H G，CHENG T C E.Parallel machine scheduling to minimize costs for earliness and number of tardy jobs［J］.Disc Appl Math，1993，47（2）：139－164.