王吉波,汪 佳,牛玉萍

(1.沈陽航空航天大學(xué) 經(jīng)濟(jì)與管理學(xué)院,沈陽 110136; 2.西安交通大學(xué) 機(jī)械制造系統(tǒng)工程國家重點(diǎn)實(shí)驗(yàn)室,西安 710053；3.沈陽航空航天大學(xué) 理學(xué)院,沈陽 110136)

具有學(xué)習(xí)效應(yīng)的單機(jī)可控加工時(shí)間排序問題研究

王吉波1,2,3,汪 佳1,牛玉萍1

(1.沈陽航空航天大學(xué) 經(jīng)濟(jì)與管理學(xué)院,沈陽 110136; 2.西安交通大學(xué) 機(jī)械制造系統(tǒng)工程國家重點(diǎn)實(shí)驗(yàn)室,西安 710053；3.沈陽航空航天大學(xué) 理學(xué)院,沈陽 110136)

在經(jīng)典排序問題中，工件的加工時(shí)間往往是一個(gè)常數(shù)，但在現(xiàn)代生產(chǎn)過程中，工件的加工時(shí)間受許多因素的影響。因此，研究工件具有學(xué)習(xí)效應(yīng)的單機(jī)可控加工時(shí)間排序問題，其中工件的加工時(shí)間是其所在位置的函數(shù)，且與加工時(shí)間的控制變量有關(guān)。目標(biāo)是求出最優(yōu)的加工時(shí)間控制變量和最優(yōu)的排序使得目標(biāo)函數(shù)最小，目標(biāo)函數(shù)包括極小化時(shí)間表長與控制費(fèi)用的和、極小化總完工時(shí)間與控制費(fèi)用的和、極小化總完工時(shí)間偏差和與控制費(fèi)用和。證明他們都能轉(zhuǎn)化為指派問題，從而多項(xiàng)式時(shí)間可解。并給出數(shù)值例子來說明問題是如何求解的。

學(xué)習(xí)效應(yīng)；單機(jī)；排序；指派問題；控制變量

在經(jīng)典的排序問題中，工件的加工時(shí)間通常是一個(gè)常數(shù)，但實(shí)際上在許多情況下工件的加工時(shí)間會(huì)隨著學(xué)習(xí)效應(yīng)、惡化效應(yīng)或資源的分配等因素發(fā)生變化(Pinedo[1]，周偉剛等[2]，王吉波等[3]，王吉波等[4])。

帶有學(xué)習(xí)效應(yīng)的排序問題目前越來越受到人們的關(guān)注。學(xué)習(xí)效應(yīng)產(chǎn)生的背景是，機(jī)器或人長時(shí)間加工相同或類似的工件時(shí)，他們的熟練程度會(huì)有所增加，導(dǎo)致后面加工的工件的加工時(shí)間會(huì)變小(Biskup[5])。關(guān)于學(xué)習(xí)效應(yīng)的排序問題可以參考最新的綜述論文Biskup[6]。Biskup[5]首次在排序中考慮學(xué)習(xí)效應(yīng)因素，并假設(shè)工件的加工時(shí)間是其所在位置的函數(shù)，證明了在單機(jī)中極小化總加工時(shí)間和具有共同工期的極小化總完工時(shí)間是多項(xiàng)式可解的。Wang[7]考慮了工件具有學(xué)習(xí)效應(yīng)的單機(jī)排序問題，其中假設(shè)工件的加工時(shí)間是其所在位置之前所有工件實(shí)際加工時(shí)間的函數(shù)，他們證明了極小化最大完工時(shí)間問題，總完工時(shí)間問題都是多項(xiàng)式可解的。Wang和Wang[8]研究了工件具有指數(shù)學(xué)習(xí)效應(yīng)的流水作業(yè)排序問題，其中假設(shè)工件的加工時(shí)間是其所在位置的指數(shù)函數(shù)。對(duì)一些正則目標(biāo)函數(shù)，他們給出了一些近似算法，并給出了最壞情況界。王吉波和劉璐[9]研究了工件具有學(xué)習(xí)效應(yīng)和準(zhǔn)備時(shí)間的單機(jī)排序問題，其中學(xué)習(xí)效應(yīng)指的是任務(wù)的實(shí)際加工時(shí)間是該任務(wù)之前排好任務(wù)對(duì)數(shù)加工時(shí)間的遞減函數(shù)。對(duì)目標(biāo)函數(shù)為最小化總完工時(shí)間問題，他們提出了分支定界法和一個(gè)啟發(fā)式算法。Wang等[10]研究了工件具有截?cái)鄬W(xué)習(xí)效應(yīng)的單機(jī)排序問題，其中工件的加工時(shí)間是其所在位置和給定控制參數(shù)的函數(shù)。對(duì)一些正則和非正則目標(biāo)函數(shù)，他們給出了多項(xiàng)式時(shí)間最優(yōu)算法。Wang等[11]研究了工件具有截?cái)鄬W(xué)習(xí)效應(yīng)的流水作業(yè)排序問題。對(duì)一些正則目標(biāo)函數(shù)，他們給出了一些近似算法，并給出了最壞情況界，同時(shí)用數(shù)值模擬的方法說明了這些算法的好壞。

此外，對(duì)于加工時(shí)間可控的排序問題也被廣泛的研究(Shabtay和Steiner[12]，Shabtay和Kaspi[13]，Wang和Wang[14])。關(guān)于加工時(shí)間可控的排序問題可以參考最新的綜述論文Shabtay和Steiner[12]。最近的論文Wang和Wang[14]討論了工件加工時(shí)間可控單機(jī)排序問題，其中工件的加工時(shí)間是所用資源的凸函數(shù)。他們對(duì)總加權(quán)流時(shí)間約束條件下極小化總資源費(fèi)用的排序問題給出了分支定界算法和啟發(fā)式算法。Wei等[15]討論了工件加工時(shí)間與開工時(shí)間和所用資源都有關(guān)系的單機(jī)可控排序問題，其中工件加工時(shí)間是所用資源的線性遞減函數(shù)。他們證明了兩種多目標(biāo)費(fèi)用問題都能多項(xiàng)式時(shí)間解決，并給出了多項(xiàng)式時(shí)間算法。Wang和Wang[16]討論了工件加工時(shí)間與開工時(shí)間和所用資源都有關(guān)系的單機(jī)可控排序問題，其中工件加工時(shí)間是所用資源的遞減凸函數(shù)。他們證明了兩種多目標(biāo)費(fèi)用問題都是多項(xiàng)式時(shí)間可解的。Wang等[17]討論了工件加工時(shí)間與開工時(shí)間和所用資源都有關(guān)系(包括線性函數(shù)關(guān)系和凸函數(shù)關(guān)系)的單機(jī)成組排序問題。在每組的工件數(shù)相同情況下，他們證明了最大完工時(shí)間與所用資源的費(fèi)用和問題可以多項(xiàng)式時(shí)間解決。

在另一方面一些文獻(xiàn)研究了同時(shí)具有學(xué)習(xí)效應(yīng)和資源分配的排序問題。Wang等[18]研究了加工時(shí)間依賴于學(xué)習(xí)效應(yīng)和資源的單機(jī)排序問題。對(duì)兩類目標(biāo)函數(shù)，他們提出了多項(xiàng)式時(shí)間算法來求出最優(yōu)排序和最優(yōu)資源分配。此外，范雁鵬和趙傳立[19]，王方和趙傳立[20]研究了工件的實(shí)際加工時(shí)間具有學(xué)習(xí)效應(yīng)與資源約束的單機(jī)排序問題，對(duì)一些與工期有關(guān)的非正則目標(biāo)函數(shù)，他們給出了多項(xiàng)式時(shí)間算法。Lu等[21]研究了加工時(shí)間依賴于學(xué)習(xí)效應(yīng)和資源的單機(jī)排序問題。對(duì)幾類和工期有關(guān)的問題，他們提出了多項(xiàng)式時(shí)間算法來求出最優(yōu)排序和最優(yōu)資源分配。

本文從另外的角度研究工件加工時(shí)間具有學(xué)習(xí)效應(yīng)的單機(jī)可控排序問題，該問題可將學(xué)習(xí)效應(yīng)排序與加工時(shí)間可控的排序兩類研究連接到一起。對(duì)三個(gè)不同的目標(biāo)函數(shù)，即極小化時(shí)間表長和控制費(fèi)用，極小化總完工時(shí)間和控制費(fèi)用，極小化總完工時(shí)間偏差和和控制費(fèi)用問題，我們證明這些問題都能夠多項(xiàng)式時(shí)間求解。文章剩余部分安排如下：第二部分對(duì)問題進(jìn)行描述，第三部分討論了對(duì)于給定的排序找到最優(yōu)的加工時(shí)間控制變量，第四部分通過將其轉(zhuǎn)化為指派問題找到最優(yōu)的排序，最后給出結(jié)論。

1 問題描述

2 具有學(xué)習(xí)效應(yīng)的最優(yōu)加工時(shí)間控制變量的求解

f(δ,π)=Cmax+Fcpt

(1)

其中[j]表示工件排在第j個(gè)位置。從以上等式我們可得到：對(duì)于給定的排序，1-θ[j]可以看作是加工時(shí)間控制變量的權(quán)，若1-θ[j]是負(fù)值，則δ[j]取最大值，若1-θ[j]是正值，則δ[j]取最小值，若1-θ[j]為零，則δ[j]取任意值，即δ[j]可表示為

(2)

(3)

正如問題1|LE，CPT|Cmax+Fcpt中所得到的結(jié)論一樣，同樣的，對(duì)于給定的排序，我們將(n-j+1)-θ[j]看作是加工時(shí)間控制變量的權(quán)，若(n-j+1)-θ[j]是負(fù)值，則δ[j]取最大值，若(n-j+1)-θ[j]取正值，則δ[j]取最小值，若(n-j+1)-θ[j]為零，則δ[j]取任意值，即

(4)

(5)

(6)

由以上分析，我們得到如下定理。

定理1 對(duì)于給定的排序π=(J[1],J[2],…,J[n]，最優(yōu)的加工時(shí)間控制變量δ=(δ[1],δ[2],…,δ[n])的取得可以描述如下：如果加工時(shí)間控制變量的權(quán)是負(fù)值，則δ[j]取最大值，如果加工時(shí)間控制變量的權(quán)是正值，則δ[j]取最小值，如果加工時(shí)間控制變量的權(quán)是零，則δ[j]取任意值。即對(duì)于問題1|LE,CPT|Cmax+Fcpt，最優(yōu)加工時(shí)間控制變量可由(2)得到；對(duì)于問題1|LE,CPT|TC+Fcpt，最優(yōu)加工時(shí)間控制變量可由(4)得到；對(duì)于問題1|LE,CPT|TADC+Fcpt，最優(yōu)加工時(shí)間控制變量可由式(6)得到。

證明 對(duì)于問題1|LE,CPT|Cmax+Fcpt，由(1)，對(duì)δ[j]求導(dǎo)得到t[j]jα(1-θ[j])，因此，當(dāng)1-θ[j]<0，則δ[j]取最大值，若1-θ[j]>0，則δ[j]取最小值，若1-θ[j]=0，則δ[j]取任意值，即δ[j]可表示為：

3 最優(yōu)排序的求解

對(duì)于問題1|LE,CPT|Cmax+Fcpt來說，我們需要找到最優(yōu)的排序是使目標(biāo)函數(shù)Cmax+Fcpt極小化，通過等式(1)，我們可以將其轉(zhuǎn)化為指派問題求解最優(yōu)的排序，令

(7)

(8)

則最優(yōu)排序可轉(zhuǎn)化為下面的指派問題求解：

(9)

xjr=0或1,j,r=1,2,3,…,n

其中第一個(gè)限制條件表示每個(gè)工件只能安排在一個(gè)位置上，第二個(gè)限制條件表示一個(gè)位置只能加工一個(gè)工件，第三個(gè)限制條件表示xjr為0-1變量，通過解此指派問題，我們即可求得問題1|LE,CPT|Cmax+Fcpt的最優(yōu)排序。

同理,對(duì)于問題1|LE,CPT|TC+Fcpt，由式(3)，我們可以令

(10)

對(duì)于問題1|LE,CPT|TADC+Fcpt，由式(5)，我們可以令

(11)

然后通過求解指派問題(9)，得到相應(yīng)問題的最優(yōu)排序。顯然指派問題的時(shí)間復(fù)雜度為O(n3)。

清塘即清除池塘野雜魚類，敵害生物，為苗種提供一個(gè)安全，舒適的環(huán)境。整塘就是將池水排干，清除池底和池邊雜草。必須先整塘，曝曬數(shù)日后，再用藥物清塘。選擇的清塘藥物一般為生石灰和茶麩，先用生石灰每畝80～100kg，要求加水融化后不待冷即向池中均勻潑灑；然后加注新水40～50cm；三日后用茶麩每畝30kg用水浸泡三四個(gè)小時(shí)后向池中均勻潑灑。

由以上分析我們可以給出問題1|LE,CPT|Cmax+Fcpt，1|LE,CPT|TC+Fcpt和1|LE,CPT|TADC+Fcpt的最優(yōu)算法如下：

算法1

步驟1)：對(duì)于問題1|LE,CPT|Cmax+Fcpt，由公式(7)，計(jì)算λjr；對(duì)于問題1|LE,CPT|TC+Fcpt，由公式(10)，計(jì)算λjr；對(duì)于問題1|LE,CPT|TADC+Fcpt，由公式(11)，計(jì)算λjr。

步驟2)：解決指派問題(9)，得到相應(yīng)問題的最優(yōu)排序。

步驟3)：由定理1，對(duì)于問題1|LE,CPT|Cmax+Fcpt，最優(yōu)加工時(shí)間控制變量可由(2)得到；對(duì)于問題1|LE,CPT|TC+Fcpt，最優(yōu)加工時(shí)間控制變量可由(4)得到；對(duì)于問題1|LE,CPT|TADC+Fcpt，最優(yōu)加工時(shí)間控制變量可由(6)得到。

顯然，算法1的時(shí)間復(fù)雜度為O(n3)(主要步驟由指派問題決定)。因此我們有

定理2 算法1能夠求得問題1|LE,CPT|Cmax+Fcpt，1|LE,CPT|TC+Fcpt和1|LE,CPT|TADC+Fcpt，的最優(yōu)排序和最優(yōu)加工時(shí)間控制變量，時(shí)間復(fù)雜度為O(n3)。

我們給出下面的例子來說明算法1是如何實(shí)現(xiàn)的(我們只考慮問題1|LE,CPT|Cmax+Fcpt)。

例1 對(duì)于問題1|LE,CPT|Cmax+Fcpt,n=4,α=-0.5,t1=1,t2=2,t3=3,t4=4,θ1=1,θ2=2,θ3=0.5,θ4=3,Δ1=0.5,Δ2=1/3,Δ3=1/4,Δ4=1/5

1-θ1=0δt=[1/2,1]1-θ2=-1δ2=11-θ3=0.5δ3=1/41-θ4=-2δ4=1λ11=1λ21=2λ31=1.875λ41=4λ12=1λ22=2λ32=1.875λ42=4λ13=0.58λ23=1.15λ33=1.08λ43=2.31λ14=0.5λ24=1λ34=0.94λ44=2

通過指派問題求得x11=x23=x32=x44=1，所以最優(yōu)的排序?yàn)閇J1,J3,J2,J4]，最優(yōu)的加工時(shí)間控制變量為δ1=[1/2,1]，δ2=1，δ3=1/4，δ4=1，極小化的目標(biāo)函數(shù)為f(δ,π)=Cmax+Fcpt=5.48。

4 結(jié)論

本文主要研究了工件具有學(xué)習(xí)效應(yīng)的單機(jī)可控加工時(shí)間排序問題，在此主要討論了三個(gè)不同的目標(biāo)函數(shù)，即極小化最大完工時(shí)間與控制費(fèi)用和，極小化總完工時(shí)間與控制費(fèi)用和，極小化總完工時(shí)間偏差和與控制費(fèi)用和，通過將其轉(zhuǎn)化為指派問題，從而證明這些問題多項(xiàng)式時(shí)間可解，即能夠以多項(xiàng)式時(shí)間求得問題的最優(yōu)的加工時(shí)間控制變量和最優(yōu)排序。在未來的研究中我們希望將其推廣到平行機(jī)或流水作業(yè)排序中，或目標(biāo)函數(shù)可以考慮更多的因素，比如準(zhǔn)時(shí)制排序問題等。

[1]Pinedo M.Scheduling:Theory,Algorithms,and Systems[M].Upper Saddle River,NJ:Prentice-Hall,2002.

[2]周偉剛,馮倩倩,高成修.加工時(shí)間可控和惡化的單機(jī)最大完工時(shí)間排序[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2012,35(4):617-625.

[3]王吉波,王建軍,何平.具有共同松弛時(shí)間的惡化型工件排序問題研究[J].大連理工大學(xué)學(xué)報(bào),2012,52:932-936.

[4]王吉波,劉璐,許揚(yáng)濤,等.具有惡化工件的不同工期指派問題研究[J].沈陽航空航天大學(xué)學(xué)報(bào),2013,30(5):83-87.

[5]Biskup D.A state-of-the-art review on scheduling with learning effects[J].European Journal of Operational Research,2008,188:315-329.

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

[7]Wang J-B.Single machine scheduling with a sum of actual processing time based learning effect[J].Journal of the Operational Research Society,2010,61:172-177.

[8]Wang J-B,Wang M-Z.Worst case analysis for flow shop scheduling problems with an exponential learning effect[J].Journal of the Operational Research Society,2012,63:130-137.

[9]王吉波,劉璐.帶準(zhǔn)備時(shí)間的任務(wù)單機(jī)學(xué)習(xí)效應(yīng)排序問題[J].大連理工大學(xué)學(xué)報(bào),2013,53(6):930-936.

[10]Wang X-R,Jin J,Wang J-B,Ji P.Single machine scheduling with truncated job-dependent learning effect[J].Optimization Letters,2014,8:669-677.

[11]Wang X-Y,Zhou Z,Zhang X,Ji P,Wang J-B.Several flow shop scheduling problems with truncated position-based learning effect[J].Computers & Operations Research,2013,40:2906-2929.

[12]Shabtay D,Steiner G.A survey of scheduling with controllable processing times[J].Discrete Applied Mathematics,2007,155:1643-1666.

[13]Shabtay D,Kaspi M.Minimizing the total weighted flow time in a single machine with controllable processing times[J].Computers & Operations Research,2004,31:2279-2289.

[14]Wang J-B,Wang M-Z.Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time[J].Computers & Operations Research,2012,39:492-497.

[15]Wei C-M,Wang J-B,Ji P.Single-machine scheduling with time-and-resource-dependent processing times[J]Applied Mathematical Modelling,2012,36:792-798.

[16]Wang X-R,Wang J-J.Single-machine scheduling with convex resource dependent processing times and deteriorating jobs[J].Applied Mathematical Modelling,2013,37:2388-2393.

[17]Wang D,Huo Y,Ji P.Single-machine group scheduling with deteriorating jobs and allotted resource[J].Optimization Letters,2014,8:591-605.

[18]Wang D,Wang M-Z,Wang J-B.Single machine scheduling with learning effect and resource dependent processing times[J].Computer & Industrial Engineering,2010,59:458-462.

[19]范雁鵬,趙傳立.帶有交貨期和加工時(shí)間可控的單機(jī)排序問題[J].重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,30(3):5-8.

[20]王方,趙傳立.具有學(xué)習(xí)效應(yīng)且加工時(shí)間可控的單機(jī)排序問題[J].沈陽師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,31(4):471-475.

[21]Lu Y-Y,Li G,Wu Y-B,Ji P.Optimal due-date assignment problem with learning effect and resource-dependent processing times[J].Optimization Letters,2014,8:113-127.

[22]Kanet JJ.Minimizing variation of flow time in a single machine systems[J].Management Science,1981,27:1453-1459.

(責(zé)任編輯：趙金蘭 英文審校：劉敬鈺)

Asinglemachineschedulingwithlearningeffectandcontrollableprocessingtimes

WANG Ji-bo1,2,3,WANG Jia1,NIU Yu-ping1

(1.School of Economics and Management,Shenyang Aerospace University,Shenyang 110136,China;2.State Key Laboratory for Manufacturing Systems Engineering,Xi′an Jiaotong University,Xi′an 710053,China;3.School of Science,Shenyang Aerospace University,Shenyang 110136,China)

In classical scheduling,the processing time of a job is a constant,but in modern production process,the processing time of a job is affected by many factors.Hence,in this paper we study scheduling problems jobs with learning effect and controllable processing times,where the processing time of a job is the function of its position in a sequence and its controllable variable.Our target is to find the optimal sequence and controllable variables so as to minimize the following objective functions:a cost containing makespan and total controllable cost,a cost containing total completion time and total controllable cost,a cost containing total absolute differences in completion times and total controllable cost.We prove that the problem is modeled as an assignment problem,and thus can be solved in polynomial time.We also give a numerical example.

learning effect;single machine;scheduling;assignment problem;controllable variable

2014-07-11

國家自然科學(xué)基金項(xiàng)目(項(xiàng)目編號(hào)：11001181)； 機(jī)械制造系統(tǒng)工程國家重點(diǎn)實(shí)驗(yàn)室開放課題(項(xiàng)目編號(hào)：sklms201306)

王吉波(1975-),男,遼寧沈陽人，博士后,教授,大連理工大學(xué)博士生導(dǎo)師(兼職)，主要研究方向：生產(chǎn)計(jì)劃與排序，E-mail：wangjibo75@163.com。

2095-1248(2014)05-0082-05

O223；C934

A

10.3969/j.issn.2095-1248.2014.05.016