崔苗苗

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

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

崔苗苗

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

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

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

0 引言

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

1 單機(jī)問題

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

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

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

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

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

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

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

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

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

完工時(shí)間為：

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

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

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

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

由式（4）可得t2后第l個(gè)工件的完工時(shí)間為：

則第l+1個(gè)工件的加工時(shí)間為

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

2 結(jié)語

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