劉 鵬，王 賽，王小麗

(沈陽工業(yè)大學(xué) 管理學(xué)院，沈陽 110870)

工件的加工時間與該工件在加工序列中的實(shí)際加工位置有關(guān)，這種現(xiàn)象被稱為“老化效應(yīng)”或“學(xué)習(xí)效應(yīng)”。老化效應(yīng)即工件的實(shí)際加工時間與工件的實(shí)際加工位置呈遞增的變化趨勢，而學(xué)習(xí)效應(yīng)則與之相反，工件的實(shí)際加工時間與工件的實(shí)際加工位置呈遞減的變化趨勢。在現(xiàn)實(shí)加工過程中，往往存在一個代理不能單獨(dú)完成一個項目，而需要兩個代理合作才能完成的情況。每個代理都有一臺機(jī)器可用于加工這個項目里的所有工件，需要找到這批工件的一個合理的劃分，以找到這兩個代理加工工件總費(fèi)用節(jié)省的最大值。

一、文獻(xiàn)綜述

工件加工時間與位置相關(guān)的排序問題近年來越來越多地受到普遍關(guān)注。Bachman和Janiak[1]研究了一些單機(jī)排序問題，其中工件加工時間是與位置相關(guān)的遞增或遞減函數(shù)。Wang等[2]考慮了一些位置相關(guān)的加工時間單機(jī)排序問題。Liu等[3]研究了帶有位置相關(guān)加工時間的雙代理單機(jī)排序問題。Rudek[4]分析了帶有位置相關(guān)加工時間的兩機(jī)流水車間調(diào)度問題的計算復(fù)雜性。Mosheiov等[5]研究了帶有位置相關(guān)加工時間的單機(jī)及時調(diào)度問題。Huang和Wang[6]考慮了帶有時間和位置相關(guān)的加工時間的單機(jī)成組調(diào)度問題。Liu[7]研究了帶有位置相關(guān)的加工時間的共同工期窗口指派的成組調(diào)度問題。Agnetis和Mosheiov[8]研究了帶有位置相關(guān)的加工時間和工件可拒絕的成比例流水車間調(diào)度問題。王杜娟等[9]研究了惡化效應(yīng)下加工時間可控的新工件到達(dá)干擾管理問題。李永林等[10]研究了考慮學(xué)習(xí)效應(yīng)的多目標(biāo)流水車間調(diào)度問題。周意元等[11]研究了具有學(xué)習(xí)效應(yīng)的排序?qū)Σ?。余英和程明寶[12]研究了具有學(xué)習(xí)和退化效應(yīng)的單機(jī)干擾管理問題。Liu等[13]研究了帶有學(xué)習(xí)效應(yīng)和遲后的雙代理排序問題的分支定界算法。劉春來和王建軍[14]研究了具有學(xué)習(xí)和退化效應(yīng)的單機(jī)干擾管理問題。

關(guān)于排序博弈問題的研究，唐國春等[15]對排序博弈進(jìn)行了綜述，給出了排序博弈的分類進(jìn)展和展望。金霽等[16]研究了加工工件都相同的情況下，由最小的最大完工時間作為加工成本的兩人合作博弈問題。顧燕紅等[17]研究工件加工時間是開工時間線性函數(shù)的情況下，以最小的最大流程時間作為加工成本的兩人合作博弈問題。Gu等[18]研究了以最小化最大延誤作為加工成本的兩人合作博弈問題。Liu等[19]以最小化加權(quán)誤工任務(wù)數(shù)作為加工成本的兩人合作博弈問題。Liu和Wang[20]研究了帶有可變加工時間和共同工期的以最小化最大延誤作為加工成本的博弈問題。本文的創(chuàng)新之處在于將工件加工時間與工件加工位置相關(guān)的情況引入雙代理排序博弈問題中。

二、問題描述

假設(shè)有一批待加工的工件集S={S1，S2，…，Sn}，由兩個代理T={1，2}共同合作完成加工。每個代理都擁有一臺機(jī)器可用于加工工件，兩個代理合作加工這n個工件。假設(shè)兩個代理存在一個給定的初始加工順序δ0∶M→{1，2}，每個工件在加工過程中不能中斷并且只能被加工一次，所有工件在“0”時刻可以開始加工。工件Sj的加工時間pj是關(guān)于工件加工位置r的函數(shù)，本文研究加工時間具有老化效應(yīng)或?qū)W習(xí)效應(yīng)的兩個排序模型，分別如式(1)、(2)所示：

pj=P0+ar

(1)

pj=P0-ar

(2)

式中：P0代表工件的正常加工時間，a>0表示模型(1)中的老化效率和模型(2)中的學(xué)習(xí)效率；j=1，2，…，n；r=1，2，…，n。因為工件的加工時間必須大于零，所以在模型(2)中學(xué)習(xí)效率a

兩個代理的加工成本定義為各自的完工時間，確定這批工件的一個劃分，把工件分配給兩臺機(jī)器加工。比較代理在不同加工順序的加工費(fèi)用與初始順序加工費(fèi)用之間的差值，即代理加工工件費(fèi)用的節(jié)省值，目的是找到這兩個代理加工總費(fèi)用節(jié)省的最大值。

三、具有老化效應(yīng)的雙代理排序博弈

用ti來表示工件i的完工時間。工件i的完工時間等于工件i的開始加工時間ti-1與工件i的加工時間pi之和，即ti=pi+ti-1。

假設(shè)給定代理加工工件集S的初始加工順序為δ0，代理加工工件集合S所需的總費(fèi)用即為代理加工各個工件的加工費(fèi)用之和，可用C(δ0，S)來表示。則有

(3)

若工件集合的最優(yōu)加工順序為δ*，則最優(yōu)加工順序下的加工成本為C(δ*，S)，從而這兩個代理加工該批工件的最大化費(fèi)用節(jié)省可表示為

v(S)=C(δ0，S)-C(δ*，S)

(4)

工件i的等待時間可以表示為

(5)

從而工件i的完工時間為

(6)

上式可簡化為

(7)

工件集S的最大化費(fèi)用節(jié)省v(S)的具體求解過程如下：

C(δ0，S)-C(δ*，S)

(8)

兩個代理合作加工工件集合S的總費(fèi)用可表示為

(9)

代理加工這批工件的最大化費(fèi)用節(jié)省為

v(S)=C(δ0，S)-C(δ*，S)=

(10)

因為代理加工工件集S的初始加工順序是給定的，所以可以假設(shè)工件劃分為由代理1加工的工件集T1和由代理2加工的工件集T2，并且滿足T1∩T2=?，T1∪T2=S，則加工這批工件的最大化費(fèi)用節(jié)省可以表示為

C(δ0，T1)-C(δ*，T1)+C(δ0，T2)-C(δ*，T2)=

v(T1)+v(T2)

(11)

圖1 初始加工排序結(jié)果

圖2 最優(yōu)加工排序結(jié)果

由此可知，跟初始工件加工順序相比，最優(yōu)加工順序下的工件加工成本費(fèi)用節(jié)省了12個單位，兩個代理加工工件的總成本下降了8.7%。

四、具有學(xué)習(xí)效應(yīng)的雙代理排序博弈

用ti來表示工件i的完工時間。工件i的完工時間等于工件i的開始加工時間ti-1與工件i的加工時間pi之和，即ti=pi+ti-1。假設(shè)給定代理加工工件集S的初始加工順序為δ0，代理在初始加工順序下加工工件集合S所需的總費(fèi)用可表示為

(12)

如果用δ*代表工件集S的最優(yōu)排序，則最優(yōu)加工順序下代理的加工成本就為C(δ*，S)，從而代理加工這批工件的最大化費(fèi)用節(jié)省可表示為

v(S)=C(δ0，S)-C(δ*，S)

(13)

工件i的等待時間可以表示為

(14)

從而工件i的完工時間為

(15)

工件i的完工時間可簡化為

(16)

兩個代理合作加工工件集合S的總費(fèi)用可以表示為

(17)

代理加工工件集S的最大化費(fèi)用節(jié)省v(S)的具體求解過程可以表示如下：

C(δ0，S)-C(δ*，S)

(18)

則這兩個代理加工工件集合S的總費(fèi)用為

(19)

加工這批工件的最大化費(fèi)用節(jié)省為

v(S)=C(δ0，S)-C(δ*，S)=

(20)

因為給定代理加工工件集S的初始加工順序，所以可以假設(shè)工件劃分為由代理1加工的工件集T1和由代理2加工的工件集T2，并且滿足T1∩T2=?，T1∪T2=S，則代理加工這批工件的最大化費(fèi)用節(jié)省可以表示為

C(δ0，T1)-C(δ*，T1)+C(δ0，T2)-C(δ*，T2)=

v(T1)+v(T2)

(21)

圖3 初始加工排序結(jié)果

圖4 最優(yōu)加工排序結(jié)果

由此可知，跟初始工件加工順序相比，最優(yōu)加工順序下的工件加工成本費(fèi)用節(jié)省了36個單位，兩個代理加工工件的總成本下降了14.63%。

五、結(jié) 論

本文將老化效應(yīng)和學(xué)習(xí)效應(yīng)引入雙代理排序博弈問題，以完工時間作為加工費(fèi)用，研究了工件加工時間隨著加工序列中工件加工位置的改變而呈現(xiàn)出遞增或遞減的情況，并以算例具體說明。未來可進(jìn)一步深入研究的方向包括：考慮其他的目標(biāo)函數(shù)，如最小化最大延遲、加權(quán)總完工時間、加權(quán)總延誤等；考慮三個及以上的代理調(diào)度問題。