帶有學習與惡化效應的機器受限的總完工時間問題

崔苗苗

（撫順市四方高級中學，遼寧撫順，112122）

帶有學習與惡化效應的機器受限的總完工時間問題

崔苗苗

（撫順市四方高級中學，遼寧撫順，112122）

本文研究一種帶有學習和惡化效應，并且機器具有可用性限制的單機排序問題。在這種模型中，工件的加工時間與所排位置及開始加工時間有關，以及機器在加工過程中，由于發生故障或進行維護與保養等原因產生的可用性限制。本文討論的目標函數為極小化總完工時間的單機問題，對于機器在任意時間段維修的情況，分別給出了動態規劃算法，分析了算法復雜性。

排序；學習效應；惡化效應；機器可用性限制；算法復雜性；動態規劃

0 引言

本文考慮學習和惡化效應模型 pi[r]=（ai+bt）ra，并結合機器具有可用性限制的情況，研究極小化總完工時間的單機問題。問題描述如下：設有n 個工件J1,J2,…,Jn，工件Ji的基本加工時間為 ai，工件在t1前t時刻開始加工時，排在第r個位置的實際加工時間為 pi[r]=（ai+bt）ra，工件在t2后t時刻開始加工時，排在在t2后第k個位置的實際加工時間為 pi[k]=（ai+bt）ka，其中α≤0是學習因子，b＞0為工件的惡化率，工件加工過程中不允許中斷。給定一個排序π，工件Ji的完工時間記為Ci。對于單機且機器在 [t1, t2] （t1＜t2）區間內不能加工工件的極小化總完工時間問題，用三參數表示法記為1nr?a, pir=(ai+bt) rα∑Ci；

1 單機問題

Adiri 等[12]證明了是NP-難的。顯然，問題也是NP難的，并且對于學習與惡化效應模型的單機極小化總完工時間的排序問題有如下結論：

引理1[6]對于問題工件按ai非減排列（shortest processing time first, SPT rule）可以得到最優排序。

根據上面引理，對于學習和惡化效應的機器可用性限制的單機排序問題，可以得到下面的結論。

證明 用反證法。由于機器在[t1, t2]時間區間內不能加工工件，那么工件只能排在t1時刻前或t2時刻后。設某最優排序違反了按基本加工時間ai非減排列規則。

（i）首先證明排在t1前的工件是按基本加工時間非減排列（SPT規則）的。

不失一般性，不妨設在排序π中排在t 1前第r 和第r+1個位置的兩相鄰工件表示t1時刻前第ir個工件排在第r 個位置加工時的實際加工時間，C[r]表示它的完工時間，則第一個工件Ji1排在第一個位置加工的實際加工時間為：

（3）式說明交換后目標函數值比交換前小，這與π是最優排序矛盾。

（ii）下面證明排在t2后的工件也是按ai非減排列（SPT規則）的。

假設t2后第一個開始加工的工件為，其開始加工時間為，定義表示在π中第個工件排在后第l個位置加工時的實際加工時間，表示它的完工時間，則排在后第一個位置加工的加工時間為：

完工時間為：

于是，工件J1…Ji的總完工時間分以下兩種情況：

由以上分析可得動態規劃算法如下：

動態規劃算法1（DP1）：

下面分析DP1的算法復雜性。

由式（4）可得t2后第l個工件的完工時間為：

則第l+1個工件的加工時間為

對于機器在零時刻進行維修的情況，可以有下面推論。

2 結語

現實生活中，人們總是希望機器在加工過程中，能夠提高工件的加工效率，縮短加工時間，但事實上在提高工人加工效率的同時，也存在機器的惡化現象，并且機器在加工過程中會出現故障或進行維護與保養等現象，導致機器在某段時間內不能加工工件。因此，本文將學習和惡化現象與機器具有可用性限制結合起來，研究了極小化總完工時間的單機問題，并給出了動態規劃求解算法，使得問題具有廣泛的應用價值和實際意義。但對于具有其它學習和惡化效應的函數問題以及機器具有可用性限制的流水作業排序問題，還有待進一步研究。

[1]Wu Chin-Chia, Hsu Peng-Hsiang , Chen Juei-Chao et al. Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times[J]. Computers & Operations Research, 2011 ,38（7）: 1025–1034.

[2]Biskup D. Single machine scheduling with learning considerations[J]. European Journal of Operational Research, 1999,115（1）: 173-178.

[3]Liu Jing, Sun Shijie, He Longmin. Some single machine scheduling problems with learning effect under consistent condition[J].運籌學學報，2003（7）：21-28.

Machine - constrained total completion time with learning and worsening effects

Cui MiaoMiao
（Sifang Senior High School of Fushun City, FuShun LiaoNing，112122）

This paper investigates a single machine scheduling problem with learning and worsening effects and machine availability constraints. In this model, the machining time of the workpiece is related to the position and starting time of machining, as well as the usability limitations of the machine during processing due to failure or maintenance and maintenance. The objective function discussed in this paper is a single machine problem which minimizes the total completion time. For the maintenance of the machine at any time, the dynamic programming algorithm is given and the complexity of the algorithm is analyzed.

ranking; learning effect; worsening effect; machine availability limitation; algorithm complexity; dynamic programming