帶有學(xué)習(xí)與惡化效應(yīng)的機(jī)器受限的總完工時間問題

崔苗苗

（撫順市四方高級中學(xué)，遼寧撫順，112122）

帶有學(xué)習(xí)與惡化效應(yīng)的機(jī)器受限的總完工時間問題

崔苗苗

（撫順市四方高級中學(xué)，遼寧撫順，112122）

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

排序；學(xué)習(xí)效應(yīng)；惡化效應(yīng)；機(jī)器可用性限制；算法復(fù)雜性；動態(tài)規(guī)劃

0 引言

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

1 單機(jī)問題

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

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

根據(jù)上面引理，對于學(xué)習(xí)和惡化效應(yīng)的機(jī)器可用性限制的單機(jī)排序問題，可以得到下面的結(jié)論。

證明 用反證法。由于機(jī)器在[t1, t2]時間區(qū)間內(nèi)不能加工工件，那么工件只能排在t1時刻前或t2時刻后。設(shè)某最優(yōu)排序違反了按基本加工時間ai非減排列規(guī)則。

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

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

（3）式說明交換后目標(biāo)函數(shù)值比交換前小，這與π是最優(yōu)排序矛盾。

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

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

完工時間為：

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

由以上分析可得動態(tài)規(guī)劃算法如下：

動態(tài)規(guī)劃算法1（DP1）：

下面分析DP1的算法復(fù)雜性。

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

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

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

2 結(jié)語

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

[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].運(yùn)籌學(xué)學(xué)報，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