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

王 方，趙傳立

（沈陽(yáng)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽(yáng) 110034）

帶有可控加工時(shí)間的排序問題［1－10］，自1980年以來備受關(guān)注，并取得了許多研究成果。本文將學(xué)習(xí)效應(yīng)與可控加工時(shí)間相結(jié)合，拓展了文獻(xiàn)［7］的主要結(jié)果。問題可描述如下。

設(shè)有n個(gè)相互獨(dú)立的工件的集合，記為｛J1，J2，…，Jn｝，工件在0時(shí)都已到達(dá)，且加工過程中中斷不被允許。工件J［j］的正常加工時(shí)間為P［j］，需要確定工件的加工順序、劃分、工期和資源分配量，極小化一個(gè)包含加權(quán)總誤工數(shù)、工期分派、最大完工時(shí)間，和總資源消耗的費(fèi)用函數(shù)。即目標(biāo)函數(shù)為以下形式：

其中，Cj是工件Jj的完工時(shí)間是最大完工時(shí)間。Uj是工件Jj的延誤指示變量，即當(dāng)Cj＞dj時(shí)，置Uj＝1；否則，置Uj＝0，dj≥0是工件Jj的工期。αj是工件Jj的延誤費(fèi)用，非負(fù)參數(shù)α和β分別表示工期的單位費(fèi)用和最大完工時(shí)間的費(fèi)用。uj是分配到工件Jj上的資源量，vj是分配到工件Jj上的資源量的單位費(fèi)用。

研究帶有以下兩種工期分派方法的問題。

1）CON型：共同工期分派方法。這里所有工件都分派一個(gè)共同工期，即dj＝d，j＝1，2，…，n

2）SLK型：松弛工期分派方法。這里所有工件都有一個(gè)相同的松弛時(shí)間，即dj＝pj＋slk，這里slk≥0是一個(gè)確定的變量。

文獻(xiàn)［11］考慮了一種機(jī)器具有學(xué)習(xí)效應(yīng)的模型，當(dāng)工件Jj排在序列的第r個(gè)位置時(shí)，其實(shí)際加工時(shí)間為pj＝，aj≤0是一個(gè)與工件相關(guān)的學(xué)習(xí)指標(biāo)。本文中工件Jj的實(shí)際加工時(shí)間為：

I線性資源消耗函數(shù)：

凸資源消耗函數(shù)：

式中，k是一個(gè)正的常數(shù)。

1 預(yù)備結(jié)論

容易驗(yàn)證，帶有CON型和SLK型工期分派方法的加工時(shí)間為常量的排序問題中的某些結(jié)論，仍然可以推廣到可控加工時(shí)間的情形。并且?guī)в蠸LK型的問題與CON型類似，因此以下本文均以CON型為例討論。

在CON型工期分派方法下，工件可以劃分為2個(gè)相鄰的集合：

1）集合E。這里所有工件的加工時(shí)間總和定義為工期d的值，且這里的工件都在它的工期前完工，故稱E為提前工件集合。

2）集合T。這里所有工件都在它的工期后完工，故稱T為延誤工件集合。

引理1 在CON型工期分派方法下，存在一個(gè)最優(yōu)排序，任意兩個(gè)工件的加工過程之間都沒有空閑時(shí)間，且第一個(gè)工件的開始時(shí)間為零。

文中帶有［j］的下標(biāo)均表示工件排在第j個(gè)位置。

引理2 存在一個(gè)最優(yōu)排序，在CON型工期分派方法下，集合E排在集合T前。

2 線性資源消耗函數(shù)的解

在CON型工期分派方法下，當(dāng)資源分配與工件所排位置確定后，工件的加工時(shí)間被固定，就簡(jiǎn)化為找最優(yōu)劃分τ＊和工期d，極小化這個(gè)問題已被文獻(xiàn)［12］解決，并在O（n）時(shí)間內(nèi)給出以下算法。

算法1：

步驟2 集合E排在T之前，并且每個(gè)集合內(nèi)部的次序無關(guān)。

步驟3 最優(yōu)工期為集合E的完工時(shí)間，即

由算法1可知，最優(yōu)工期和工件的劃分是由加工時(shí)間決定的。然而，當(dāng)加工時(shí)間由式（2）和式（3）確定時(shí)，意味著最優(yōu)工期和工件的劃分還將與工件所排位置和分配的資源有關(guān)。

由于對(duì)任意一種給定的劃分、排序和資源分配，相應(yīng)的最優(yōu)工期就可以確定，因此，以下這個(gè)問題旨在確定最優(yōu)的劃分、排序和資源分配。

對(duì)任意一個(gè)給定的劃分和排序，目標(biāo)函數(shù)式（1）可變形為：

假定｜E｜＝l，｜T｜＝n－l.則上式又可變形為：

當(dāng)加工時(shí)間為一個(gè)線性資源消耗函數(shù)式（2）時(shí)，目標(biāo)函數(shù)式（4）變?yōu)椋?/p>

對(duì)于SLK型工期分派方法，帶有固定加工時(shí)間的相關(guān)結(jié)論文獻(xiàn)［8］中已做了詳細(xì)分析。

引理3 在CON型工期分派方法下，對(duì)于任意給定的劃分和工件序列，最優(yōu)資源分配作為劃分和工件序列的一個(gè)函數(shù)，可以這樣得到：

證明 對(duì)式（5）關(guān)于u［j］求導(dǎo)得證。

由以上分析可知，對(duì)于任意給定的劃分和排序，最優(yōu)資源分配都可以由引理3求出，那么，這個(gè)問題就簡(jiǎn)化為求一個(gè)最優(yōu)劃分和最優(yōu)序列的排序問題。

然而，對(duì)于任意一個(gè)給定的劃分，最優(yōu)排序可以通過在O（n3）時(shí)間內(nèi)解一個(gè)指派問題得到，分析如下：

根據(jù)前面在CON型工期分派方法下假定的劃分，對(duì)于目標(biāo)函數(shù)（5）式，當(dāng)l給定時(shí)，令

其中，cij（l）依目標(biāo)函數(shù)式（5）中Wj的不同而不同。

定義xij為一個(gè)0－1變量，當(dāng)工件Ji排到第j個(gè)位置時(shí)，xij＝1；否則，xij＝0。對(duì)于目標(biāo)函數(shù)式（5），指派問題可表示如下：

引理4 對(duì)于目標(biāo)函數(shù)式（1），任意給定一種劃分τ，在CON型工期分派方法下，當(dāng)加工時(shí)間由式（2）確定時(shí)，相關(guān)最優(yōu)排序可以通過解一個(gè)指派問題在O（n3）時(shí)間內(nèi)得到。

根據(jù)以上的分析，對(duì)于任意一個(gè)給定的劃分，都可以通過解指派問題找到最優(yōu)排序。因此，這個(gè)問題又進(jìn)一步簡(jiǎn)化為找最優(yōu)劃分τ＊的問題。

因?yàn)閘的值有n種可能的取法，所以為了找最優(yōu)的劃分，只有取遍所有l(wèi)可能值并解相應(yīng)的l值對(duì)應(yīng)的指派問題，才能得到這個(gè)問題的最優(yōu)解。這個(gè)問題的最優(yōu)解總結(jié)為算法2。

算法2 求解帶有CON型工期分派方法的線性資源消耗函數(shù)最優(yōu)解的算法。

初始 置Z＊＝∞，l＝0。

步驟1 當(dāng)l≤n時(shí)：

步驟1.1 通過式（7）計(jì)算cij（l）的值；

步驟1.2 解指派問題P1（l）：，確定工件的最優(yōu)排序π＊＝［1］，［2］，…，［n］和極小化費(fèi)用Z（l）；

步驟1.3 如果Z（l）＜Z＊，那么，置Z＊＝Z（l），l＊＝l，π＊（l＊）＝π＊（l）；

步驟1.4l＝l＋1。

步驟2 當(dāng)l＝l＊，π＊（l）＝π＊（l＊）時(shí)，通過引理3計(jì)算最優(yōu)資源分配u＊（l），通過式（2）計(jì)算最優(yōu)加工時(shí)間

定理1 算法2在O（n4）時(shí)間內(nèi)解決了在CON型工期分派方法下，這個(gè)問題的目標(biāo)函數(shù)為一個(gè)線性資源消耗函數(shù)時(shí)的最優(yōu)解。

3 凸資源消耗函數(shù)的解

當(dāng)加工時(shí)間為一個(gè)凸資源消耗函數(shù)式（3）時(shí)，代入式（4），則目標(biāo)函數(shù)變?yōu)橐韵滦问剑?/p>

由目標(biāo)函數(shù)式（8）可以看出，在CON型工期分派方法下，任意給定一種劃分和排序，當(dāng)加工時(shí)間為一個(gè)凸資源消耗函數(shù)時(shí)，這個(gè)問題變?yōu)橐粋€(gè)關(guān)于資源分配的凸函數(shù)。因此，最優(yōu)資源分配可描述如下：

引理5 最優(yōu)資源分配u＊（π，l），作為劃分和工件序列的一個(gè)函數(shù)，是：

CON型：

把引理5中的最優(yōu)資源分配分別代入目標(biāo)函數(shù)式（8），得到

由于對(duì)于任意給定的劃分和排序，最優(yōu)資源分配都可以通過引理5得到。因此，這個(gè)問題又簡(jiǎn)化為找最優(yōu)劃分和排序的問題。

此時(shí)，任意給定的一種劃分，最優(yōu)排序仍然可以通過解指派問題，在O（n3）時(shí)間內(nèi)得到。分析如下：

根據(jù)前面在CON型工期分派方法下假定的劃分，對(duì)于目標(biāo)函數(shù)式（7），當(dāng)l給定時(shí)，令

其中，cij（l）依目標(biāo)函數(shù)（9）式中Wj的不同而不同。

定義xij為一個(gè)0－1變量，當(dāng)工件Ji排到第j個(gè)位置時(shí)，xij＝1；否則，xij＝0。對(duì)于目標(biāo)函數(shù)（9）式，指派問題的表示同前面P1（t）的形式，不妨記為P2（t）。

引理6 對(duì)于這個(gè)問題，任意給定一種劃分τ，在CON型工期分派方法下，當(dāng)加工時(shí)間由式（3）確定時(shí)，相關(guān)最優(yōu)排序可以通過解一個(gè)指派問題在O（n3）時(shí)間內(nèi)得到。

由以上的分析，有下面的結(jié)論

對(duì)于任意一個(gè)給定的劃分，都可以通過解指派問題找到最優(yōu)排序。因此，這個(gè)問題的最優(yōu)解又進(jìn)一步簡(jiǎn)化為找最優(yōu)劃分τ＊的問題。

同樣，因?yàn)閘的值有n種可能的取法，只有取遍的所有l(wèi)的可能值并解相應(yīng)的l值對(duì)應(yīng)的指派問題，才能得到這個(gè)問題的最優(yōu)解。因此，當(dāng)加工時(shí)間為一個(gè)凸資源消耗函數(shù)時(shí)，在CON型工期分派方法下，這個(gè)問題的最優(yōu)解總結(jié)為算法3。

算法3 求解帶有CON型工期分派方法的凸資源消耗函數(shù)最優(yōu)解的算法。

初始 置Z＊＝∞，l＝0。

步驟1 當(dāng)l≤n時(shí)：

步驟1.1 通過式（10）計(jì)算cij（l）的值；

步驟1.2 解指派問題P2（l），確定工件的最優(yōu)排序π＊＝［1］，［2］，…，［n］和極小化費(fèi)用Z（l）；

步驟1.3 如果Z（l）＜Z＊，那么，置Z＊＝Z（l），l＊＝l，π＊（l＊）＝π＊（l）；

步驟1.4l＝l＋1。

步驟2 當(dāng)l＝l＊，π＊（l）＝π＊（l＊）時(shí)，通過引理5計(jì)算最優(yōu)資源分配u＊（l），通過式（3）計(jì)算最優(yōu)加工時(shí)間

定理2 算法3在O（n4）時(shí)間內(nèi)解決了在CON型工期分派方法下，這個(gè)問題的目標(biāo)函數(shù)為一個(gè)凸資源消耗函數(shù)時(shí)的最優(yōu)解。

4 結(jié) 語(yǔ)

現(xiàn)實(shí)生活中，學(xué)習(xí)效應(yīng)是普遍存在的，本文將學(xué)習(xí)效應(yīng)與可控加工時(shí)間相結(jié)合，使得問題更具有廣泛應(yīng)用性和實(shí)際意義。這個(gè)問題在多機(jī)環(huán)境下或者加工時(shí)間為其他資源消耗函數(shù)的情形有待進(jìn)一步研究。

［1］LEYVAND Y，SHABTAY D，STEINER G A.A unified approach for scheduling with conwex resource consumption functions using positional penalties［J］.Eur J Oper Res，2010，206（2）：301－312.

［2］SU L H，LIEN C Y.Scheduling parallel machines with resource dependent processing times［J］.Int J Prod Econ，2009，117（2）：256－266.

［3］SHABTAY D，STEINER G.A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates［J］.J Sched，2011，14（5）：455－469.

［4］SHABTAY D，STEINER G.A survey of scheduling with controllable processing times［J］.Disc Appl Math，2007，155（13）：1643－1666.

［5］PANWALKAR S S，SMITH M L，SEIDMANN A.Common due date assignment to minimize total penalty for the one machine scheduling problem［J］.Oper Res，1982，30（2）：391－399.

［6］CHENG T C E，OGAZ C，QI X D.Due－date assignment and single scheduling with compressible processing times［J］.Int J Prod Econ，1996，43（1）：29－35.

［7］SHABTAY D，STEINER G.Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine［J］.Manuf Serv Oper Manage，2007，9（3）：332－350.

［8］BISKUP D.Single－machine scheduling with learning considerations［J］.Eur J Oper Res，1999，115（1）：173－178.

［9］BISKUP D.A state－of－the－art review on scheduling with learning effect［J］.Eur J Oper Res，2008，188（2）：315－329.

［10］WANG D，WANG M Z，WANG Jibo.Single－machine scheduling with learning effect and resource－dependent processing times［J］.Comput indust Eng，2010，59（3）：458－462.

［11］MOSHEIOV G，SIDNE J B.Scheduling with general job－dependent learning curves［J］.Eur J Oper Res，2003，147（3）：665－670.

［12］KAHLBACHER H G，CHENG T C E.Parallel machine scheduling to minimize costs for earliness and number of tardy jobs［J］.Disc Appl Math，1993，47（2）：139－164.