劉 鵬，王 賽，王小麗

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

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

一、文獻綜述

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

關(guān)于排序博弈問題的研究，唐國春等[15]對排序博弈進行了綜述，給出了排序博弈的分類進展和展望。金霽等[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}共同合作完成加工。每個代理都擁有一臺機器可用于加工工件，兩個代理合作加工這n個工件。假設(shè)兩個代理存在一個給定的初始加工順序δ0∶M→{1，2}，每個工件在加工過程中不能中斷并且只能被加工一次，所有工件在“0”時刻可以開始加工。工件Sj的加工時間pj是關(guān)于工件加工位置r的函數(shù)，本文研究加工時間具有老化效應或?qū)W習效應的兩個排序模型，分別如式(1)、(2)所示：

pj=P0+ar

(1)

pj=P0-ar

(2)

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

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

三、具有老化效應的雙代理排序博弈

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

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

(3)

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

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

(4)

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

(5)

從而工件i的完工時間為

(6)

上式可簡化為

(7)

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

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

(8)

兩個代理合作加工工件集合S的總費用可表示為

(9)

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

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

(10)

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

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

v(T1)+v(T2)

(11)

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

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

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

四、具有學習效應的雙代理排序博弈

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

(12)

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

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

(13)

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

(14)

從而工件i的完工時間為

(15)

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

(16)

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

(17)

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

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

(18)

則這兩個代理加工工件集合S的總費用為

(19)

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

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

(20)

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

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

v(T1)+v(T2)

(21)

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

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

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

五、結(jié) 論

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