唐國春，井彩霞

①上海第二工業(yè)大學經(jīng)濟管理學院，上海 201209；②天津工業(yè)大學管理學院，天津 300387

現(xiàn)代排序論應用*

唐國春①?，井彩霞②

①上海第二工業(yè)大學經(jīng)濟管理學院，上海 201209；②天津工業(yè)大學管理學院，天津 300387

排序是為加工若干個工件而對工件及其所需要的機器按時間進行分配和安排，在完成所有工件加工時使得某個(些)目標為最優(yōu)。在過去幾十年里，排序論的研究進展迅速。簡述排序論在中國的發(fā)展歷程，介紹現(xiàn)代排序論在三個代表性領域的應用：供應鏈排序、半導體生產(chǎn)中的排序和手術排程，并展望未來的發(fā)展。

排序；供應鏈；半導體/晶圓；手術

第二次世界大戰(zhàn)期間運籌學興起，首次把運作(operation)作為研究對象。其間，研究運作的時間安排促成了排序(scheduling)概念的建立和研究的開展。在20世紀中葉運籌學奠基時期，排序論的先驅工作已經(jīng)在離散優(yōu)化領域占有重要地位。此后，排序論始終保持蓬勃發(fā)展的勢態(tài)。

20世紀60年代越民義就注意到排序問題的重要性和在理論上的難度。1963年他編寫了國內(nèi)第一本排序論講義。70年代初他和韓繼業(yè)研究同順序流水作業(yè)排序問題[1]，開創(chuàng)了中國研究排序論的先河。在他們兩位的倡導和帶動下國內(nèi)排序論的理論研究和應用研究有了較大的發(fā)展。國內(nèi)自動化學科把“scheduling”譯為“調(diào)度”始于1983年[2]。調(diào)度有太寬泛的涵義，1978年《現(xiàn)代漢語詞典》對于“調(diào)度”的解釋是“管理并安排(工作、人力、車輛等)”[3]，是指對實際過程的具體操作?？紤]到在數(shù)學和運籌學中50年來使用的習慣，我們贊同把“scheduling”譯成“排序”。雖然“調(diào)度”不是數(shù)學上的術語[4]，我們也尊重自動化學科使用“調(diào)度”的譯法。所以，我們提倡用“排序”和“調(diào)度”作為“scheduling”的中文譯名。蘇步青院士曾為排序專業(yè)委員會(排序分會)題簽《排序通訊》和《排序論學報》，激勵大家學習和研究排序論[5]。國家自然科學基金委員會學科代碼G010302是排序、排隊論和存儲論[6]。

排序論開創(chuàng)者之一Baker指出：“排序領域內(nèi)許多早期的工作是在制造業(yè)推動下發(fā)展起來的，所以在描述排序問題時會很自然地使用制造業(yè)的術語。雖然排序問題在許多非制造業(yè)的領域內(nèi)取得相當有意義的成果，但是制造業(yè)的術語仍然經(jīng)常在使用。因而，往往把資源(resource)稱為機器(machine)，把任務(task)稱為工件(job)。有時工件由幾個受先后次序約束的基本任務所組成，這種基本任務稱為工序(operations)。例如，把門診病人到醫(yī)療診所看病的排序問題也描述成為‘工件’在‘機器’上‘加工’的過程”[7]。排序論中的“機器”和“工件”已經(jīng)不是機器制造業(yè)中的“車床”和“車床加工的螺絲”，已經(jīng)從“車床”和“螺絲”等具體事物中抽象出來，是抽象的代表性概念。排序論中的“工件”可以是任務、非圓齒輪、計算機終端、患者、降落的飛機等，“機器”可以是完成任務所需要的人財物資源、數(shù)控機床、計算機中央處理器(CPU)、醫(yī)生、機場跑道等。例如：計算機科學中并行計算機的出現(xiàn)，促進排序論中對平行機(parallel machine)排序的深入研究；反過來，排序論中的平行機可以應用到計算機科學的并行計算中去，平行機排序的成果在一定程度上推動并行計算和并行計算機的發(fā)展[8]。Baker指出：“排序是為完成一些任務而對所需資源按時間進行分配?！薄芭判蛞龀鰶Q策，要回答兩個問題：①哪些資源要分配以完成每項任務；②何時完成每項任務?！盵7]Pinedo在著名的《Scheduling: Theory，Algorithms，and Systems》一書中提出幾乎相同的看法，“排序是按時間把稀缺資源分配給要完成的任務[9]。因而，按時間分配工件（任務）和機器（資源）是排序很本質的特征。

工件何時就緒，何時開始加工，何時中斷加工(preempt)，何時更換工件，何時再繼續(xù)加工原工件；機器何時就緒，何時進行加工，何時空閑(idle)，何時更換機器等等，這些都是按時間進行分配和安排。單純的分配問題，是單純地把工件分配給機器以便進行加工，是一個數(shù)學規(guī)劃問題。單純的次序安排問題是sequencing問題。從最優(yōu)化的角度我們給排序如下的定義：排序是為加工若干個工件，而對工件及其所需要的機器按時間進行分配和安排，在完成所有工件加工時使得某個(些)目標為最優(yōu)。

因此，在數(shù)學、運籌與管理、自動化、工業(yè)工程的范疇里，“排序”默認的涵義是“scheduling”，而且是指“機器排序(machine scheduling)”?！癝equencing”譯成“安排次序”，是一種特殊的“scheduling”，是只要確定工件的次序就完全確定加工的時間表(schedule)問題，因此，排序論學科的定位是機器排序的理論和應用。除了機器排序之外，還有項目排序(project scheduling)和數(shù)據(jù)排序(sorting)。項目排序包括CPM(關鍵路線法)和PERT(計劃評審技術)。數(shù)據(jù)排序又稱為整序，是更為特殊的一類sequencing問題，僅僅是一些“元素”(即“工件”)按照某種要求重新安排次序的問題，并不涉及到“機器”的因素，例如冒泡排序和快速排序等。此外，“timetabling”也是“安排時間表”，是指安排課程表，安排(火車或飛機)時刻表等。與作為最優(yōu)化問題的scheduling不同，timetabling主要解決的是“存在性”問題，是判別和設計是否存在符合某些要求的時間表[8]。

如果按數(shù)學分為理論數(shù)學和應用數(shù)學，那么排序論可以分為排序的理論部分和排序的應用部分。排序的理論部分又可分為經(jīng)典排序(classical scheduling)和現(xiàn)代排序(modern scheduling)。Brucker和Knust在《Complexity Results of Scheduling Problems》[10]中使用classical和extended兩個詞來區(qū)別經(jīng)典的和非經(jīng)典的兩類排序問題。他們也用新型排序來表示非經(jīng)典的排序問題，這也就是Potts等稱為Enhanced(擴展的)排序問題[11]。因此，現(xiàn)代排序就是非經(jīng)典的、推廣的、擴展的，也就是新型的排序[8]，是排序論學科發(fā)展史上第五個十年的研究主題[11]。

現(xiàn)代排序是相對經(jīng)典排序而言，其特征是突破經(jīng)典排序的基本假設。根據(jù)1993年Lawler等的觀點，經(jīng)典排序有4個基本假設[12]：①單資源。機器是加工工件所需要的一種資源。一臺機器在任何時刻最多只能加工一個工件；一個工件在任何時刻至多在一臺機器上加工。作為這個基本假設的突破，有成組批量排序、同時加工排序(又稱為分批排序)、不同時開工排序和資源受限排序等。②確定性。決定排序問題的一個實例的所有(輸入)參數(shù)都是事先知道的和完全確定的。作為這個基本假設的突破，有可控排序、隨機排序、模糊排序和在線排序等。③可運算性。我們是在可以運算和計算的程度上研究排序問題，而不去顧及諸如如何確定工件的交貨期，如何購置機器和配備設備等技術上可能發(fā)生的問題。如果考慮實際應用中有關的情況和因素，就是應用排序問題。④單目標和正則性。排序的目的是使衡量排法好壞的一個一維目標函數(shù)的函數(shù)值為最小，而且這個目標函數(shù)是工件完工時間的非降函數(shù)。這就是所謂正則目標。多目標排序、準時排序和窗時排序等是這個假設的突破。

因此，上述10種經(jīng)過推廣的排序(可控排序、成組批量排序、在線排序、同時加工排序、準時排序和窗時排序、不同時開工排序、資源受限排序、隨機排序、模糊排序、多目標排序等)就構成現(xiàn)代排序的主要內(nèi)容[8]。當然，這10種排序不可能包括層出不窮、不斷涌現(xiàn)的新型排序，沒有涉及到的新型排序有工件加工時間隨加工次序變動的排序和多臺機器同時加工工件的排序等。

1 供應鏈排序

供應鏈是圍繞核心企業(yè)，通過對信息流、物流、資金流等的控制，從采購原材料，到中間產(chǎn)品(或者中間服務)、最終產(chǎn)品(或者最終服務)，最后由銷售網(wǎng)絡把產(chǎn)品(或者服務)送到客戶，是供應商、制造商、分銷商、零售商，直到客戶形成的網(wǎng)鏈結構。這類網(wǎng)鏈結構的設計、協(xié)調(diào)、優(yōu)化是供應鏈管理的主要任務。供應鏈排序是集成研究供應鏈管理中生產(chǎn)(或者服務)的排序、分批和發(fā)送，是排序論在供應鏈管理中的應用[13]。

供應鏈排序前端的供應商問題是研究供應商如何安排生產(chǎn)和如何把工件分批并發(fā)送給制造商，使生產(chǎn)排序費用和發(fā)送費用的總費用為最小。供應鏈排序后端的制造商問題是研究制造商如何安排生產(chǎn)和如何把工件分批并發(fā)送給客戶，使生產(chǎn)排序費用和發(fā)送費用的總費用為最小。把供應鏈排序前端和后端一起研究的問題稱為聯(lián)合問題[13]。

樹形供應鏈是指在供應鏈中只有一個供應商，這個供應商要為多個制造商加工和發(fā)送工件(貨物)。供應商對工件進行加工時，需要一定的生產(chǎn)排序費用；在安排發(fā)送貨物時，又需要一定的發(fā)送費用。我們的目標是使排序費用和發(fā)送費用的總和(簡稱為總費用)為最小。我們假定每發(fā)送一批貨物的費用只與發(fā)送給哪個制造商有關，而與發(fā)送了多少貨物無關，也就是說，對于同一個制造商來說，供應商每次發(fā)送的費用是一個常數(shù)。但是，每次最多能夠發(fā)送的貨物數(shù)量有一個上限，我們稱之為發(fā)送能力。因此，為減少發(fā)送費用，需要把發(fā)送給同一個制造商的貨物分成若干批，然后按批進行發(fā)送。由于是成批發(fā)送，所以這批中每個工件的完工時間應該是它所在的批中所有工件都加工完成的時刻，也就是等于這批中最后一個工件的完工時間。這個完工時間稱為是這個批的完工時間。一般來講，存在具有以下性質的最優(yōu)排序：

(1) 供應商加工任何兩個工件之間沒有空閑；

(2) 每一批的發(fā)送都發(fā)生在這批工件中的某一個工件的完工時間；

(3) 從供應商發(fā)送一批工件給制造商時，這批工件在供應商處是接連加工的。

這就可以縮小搜索的范圍。

其他還有多供應商供應鏈排序、多運輸方式供應鏈排序等等，可以參考專門的論文。例如，在供應鏈排序中，工件加工后分批發(fā)送給下游客戶的運輸方式有多種，供應商不僅需要確定工件加工順序和分批方式，還要確定運輸方式，使加工和運輸總費用最少。這就是多運輸方式供應鏈排序[13]。

2 半導體生產(chǎn)中的排序問題

晶圓是硅半導體集成電路制作所用的硅晶片。晶圓的生產(chǎn)中有三類特殊的排序問題：工件可重入排序、多功能機排序和同時加工排序。

(1) 可重入排序

可重入(Re-entrance)是晶圓生產(chǎn)最典型的特點(圖1)。每個晶圓都由具有相似工藝的不同層組成，因此，晶圓會多次重復訪問相同的機器以完成不同層的加工。正是由于這種重入的特性，半導體生產(chǎn)系統(tǒng)被稱為是不同于傳統(tǒng)的流水作業(yè)(flow shop)和異序作業(yè)(job shop)的“第三類生產(chǎn)方式”[14]。

對于多重入的單臺機器排序問題，可以利用工件的重入特性和具有平行鏈約束之間的關系，分別給出在總帶權完工時間和最大費用函數(shù)兩個目標函數(shù)下的多項式時間最優(yōu)算法[15]。其他流水作業(yè)[16]、異序作業(yè)[17]等更為復雜機器的多重入可以參考有關的論文。

除了半導體生產(chǎn)外，在信號處理、印刷電路板[18]以及橋梁建造[19]等等許多領域也會發(fā)生加工“可重入”情況。

(2) 多功能機排序問題

半導體晶圓種類繁多，工序復雜。有些工序要求在指定的機臺上加工，而不是所有機臺都能加工。另一方面，同一臺機器上加工不同種類的晶圓，需要一個安裝時間。這個安裝時間是更換模具(光罩)的時間，也可能是調(diào)整加工條件(如溫度、氣體密度等)所需的時間。這就是需要安裝時間的多功能機(multi-purpose machine)排序[20]。

多功能機排序問題中工件組與機器之間的對應關系見圖2，其中左邊表示有7個工件組，右邊表示有5臺平行機器。如果工件組和機器之間有向量連接，則表示該工件組中的工件可以在相應的機器上加工，否則這臺機器不能加工該組工件。同組的工件在機器上接連加工時不需要安裝時間；不同組的工件接連加工時需要一個安裝時間。同組中的工件不一定要接連加工，并且每臺機器在加工第一個工件前，也需要安裝時間。我們要尋找加工方案，使最后完工的工件盡可能提前。

多功能機排序在實際應用中還要考慮機器安裝的次數(shù)。在半導體晶圓生產(chǎn)車間中更換光罩或調(diào)整加工條件都需要人為地去操作，而且安裝上新的光罩以后還需要有一個適應的過程，也就是說新光罩下最初的幾批晶圓有可能是不達標的，所以有時寧可犧牲完工時間，也不愿意頻繁地調(diào)整機器。這就是兩個目標的多功能機排序問題，其中一個目標是使最后完工的工件盡可能提前，另一個目標是使安裝次數(shù)為最少[21]。

圖1 可重入加工示意圖

圖2 多功能機排序中工件與機器的對應關系

(3) 同時加工排序

同時加工排序又稱為分批排序，產(chǎn)生于20世紀90年代大規(guī)模的現(xiàn)代化生產(chǎn)流水作業(yè)線，并很快被應用到航空工業(yè)、鋼鐵鑄造、冶金、電鍍甚至制鞋業(yè)等許多領域。半導體晶圓生產(chǎn)是分批排序應用最廣泛的領域。分批排序主要有三種模型：批加工時間為該批中最大工件加工時間的并行批(parallel batch)，批加工時間為該批中工件加工時間之和的串行批(serial batch)及批加工時間為常數(shù)的模型。常見的也是默認的分批模型是并行批排序模型。并行批排序模型源于晶圓測試，是把晶圓放入烤箱烘烤(圖3，不同的形狀代表不同種類的晶圓)，每個晶圓都有一個最短的烘烤時間，經(jīng)受住最短烘烤時間烘烤的晶圓才是合格產(chǎn)品。這里最短烘烤時間是指相應的晶圓多烘烤一些時間是允許的?？鞠溆幸粋€固定的容量B，并假設每種晶圓的體積為1，至多有B個晶圓可以作為一批放在烤箱內(nèi)同時烘烤，烘烤過程不允許中斷。每種晶圓的最短烘烤時間可能不同，為了保證質量，同一烤箱內(nèi)晶圓的實際烘烤時間是所有最短烘烤時間中最長的。相對其他測試過程，烘烤的用時很長(大約是120 min，其他過程大約5 min)，從而成為晶圓生產(chǎn)流程的瓶頸。隨著半導體工業(yè)的飛速發(fā)展，競爭不斷加劇，如何有效地利用組合優(yōu)化工具，提出分批排序問題的好算法，以縮短產(chǎn)品的生產(chǎn)流程，提高生產(chǎn)效率，無疑具有重大意義。

圖3 烤箱示意圖

3 手術排程

醫(yī)院中使用設備最昂貴、動用人力資源最廣泛、涉及資金最多的是手術室及其手術的管理和安排，通常稱為手術排程(圖4)。手術室往往是醫(yī)療總流程的瓶頸，許多患者必須等待手術完成后才能繼續(xù)進行下一步的診療。如何高效地利用手術資源，是醫(yī)院節(jié)約成本，提高工作效率，為患者提供滿意服務的關鍵。

我們把手術患者看成是待加工的工件，把執(zhí)刀醫(yī)師、麻醉師、護士和手術設備等四種資源看成是實施手術同時需要的機器，那么一臺手術就是需要多臺機器同時進行加工的工件。如果把醫(yī)院中多間手術室看成多臺平行機，那么手術排程就是多臺機器同時加工工件的平行機排序問題。基于理論分析，按照排序論中的算法，把執(zhí)刀醫(yī)師及其承擔的手術分配到手術室，使得最遲結束的手術盡可能地提前，使所有的手術盡早做完，也就是使所有手術室開放的時間盡可能短。由于安排分配到手術室中手術的次序是不會改變這個手術室的開放時間的，我們還按照排序論中的算法，使得醫(yī)院和患者為手術付出的總的“代價”為最小，從而提高手術相關資源的利用率。我們在排序論理論分析基礎上提出算法和估計誤差，用層次分析法、零和博弈和仿真技術得到反映四種資源重要性的資源權數(shù)，配合上海市第一人民醫(yī)院研發(fā)計算機手術排程系統(tǒng)，并應用于實際，取得良好的經(jīng)濟和社會效益[22]。這在國內(nèi)外是首創(chuàng)的。國際上絕大多數(shù)是建立執(zhí)刀醫(yī)師或(和)護士安排的數(shù)學規(guī)劃(包括混合整數(shù)規(guī)劃或者目標規(guī)劃)的數(shù)學模型，個別有建立排序論模型，但是求解還是轉化為數(shù)學規(guī)劃，算法復雜，計算量大。我們這個手術排程項目獲得2012年中國運籌學會第五屆運籌學應用二等獎、2013年中國醫(yī)院科技創(chuàng)新獎二等獎、2013年上海醫(yī)學科技獎二等獎和2014年中華醫(yī)學科技獎衛(wèi)生管理獎。我們還在進一步改進手術排程的算法，在考慮到同一執(zhí)刀醫(yī)師的手術要接連安排，使得手術室開放的時間盡可能短和提高手術相關資源的利用率等三個目標的基礎上，還要能夠滿足更多的要求，包括要考慮執(zhí)刀醫(yī)師的巡視病房和門診的安排，要考慮手術清潔(污染)程度、麻醉方式和患者特性等等。

圖4 醫(yī)院手術流程

4 展望

排序論學科發(fā)展已經(jīng)60年。經(jīng)過組合分析、分支定界、計算復雜性和分類、近似算法、現(xiàn)代排序等五個階段之后[11]，排序論與博弈論、行為科學交叉，供應鏈排序、半導體生產(chǎn)中的排序、手術排程等許多應用研究有較大的進展。正如Potts等指出：“排序論的進展是巨大的。這些進展得益于研究人員從不同的學科(例如：數(shù)學、運籌學、管理科學、計算機科學、工程學和經(jīng)濟學等)所做出的貢獻。排序論已經(jīng)成熟，有許多理論和方法可以處理問題；排序論也是豐富的(例如，有確定性或者隨機性的模型、精確的或者近似的解法、面向應用的或者基于理論的)。盡管排序論取得進展，但是在這個令人興奮并且值得研究的領域，許多挑戰(zhàn)仍然存在?！盵11]排序論的長足發(fā)展，尤其是具有廣闊應用前景的現(xiàn)代排序的豐碩成果，使排序論已經(jīng)成為發(fā)展最迅速、研究最活躍、成果最豐碩、前景最誘人的學科領域之一。排序論作為組合優(yōu)化的一個分支，將繼續(xù)在運籌學的大花園里綻放出美麗的花朵。

(2013年12月18日收稿)■

[1] 越民義, 韓繼業(yè). n個零件在m臺機床上的加工順序問題(I)[J]. 中國科學, 1975, 5: 462-470.

[2] 周榮生. 漢英綜合科學技術詞匯[M]. 北京: 科學出版社, 1983.

[3] 中國社會科學院語言研究所詞典編輯室. 現(xiàn)代漢語詞典[M] . 上海:商務印書館, 1978.

[4] 唐國春. 關于Scheduling中文譯名的注記[J]. 系統(tǒng)管理學報, 2010, 19(6): 713-716.

[5] 唐國春. 一萬米高空是晴天——教壇漫筆[M]. 珠海: 珠海出版社, 2011.

[6] 國家自然科學基金委員會. 國家自然科學基金申請代碼[EB/OL] [2014-7-20]. http://www.nsfc.gov.cn/nsfc/cen/xmzn/2014xmzn/17.

[7] BAKER K R. Introduction to Sequencing and Scheduling [M]. New York: John Wiley & Sons, 1974.

[8] 唐國春, 張峰, 羅守成, 等. 現(xiàn)代排序論[M]. 上海: 上?？茖W普及出版社, 2003.

[9] PINEDO M L. Scheduling: theory, algorithms, and systems [M]. 3rd Edition. New York: Springer, 2008.

[10] BRUCKER P, KNUST S. Complexity results for scheduling problems[EB/OL]. (2009-6-29)[2014-7-20]. http://www.informatik. uni-osnabrueck.de/knust/class.

[11] POTTS C N, STRUSEVICH V A. Fifty years of scheduling: a survey of milestones [J]. Journal of the Operational Research Society, 2009, 60: S41-S68.

[12] LAWLER E L, LENSTRA J K, RINNOOY KAN A H G, et al. Sequencing and scheduling: Algorithms and complexity [M]//GRAVES S C, et al. Handbooks in OR & MS(Volume 4). Amsterdam: Elsevier Science Publishers B V, 1993: 445-522.

[13] 唐國春. 供應鏈排序的模型和方法[C]//袁亞湘, 等. 中國運籌學會第八屆學術交流會論文集. 香港: Global-Link Informatics Limited, 2006: 495-502.

[14] KUMAR P R. Re-entrant lines [J]. Queuing Systems, 1993, 13: 87-110.

[15] 井彩霞, 錢省三, 唐國春. Single machine scheduling with re-entrance [J]. 運籌學學報, 2008, 12 (2): 84-87.

[16] 井彩霞, 黃婉珍, 唐國春. Minimizing total completion time for reentrant flow shop scheduling problems [J]. Theoretical Computer Science, 2011, 412(48): 6712-6719.

[17] CHEN J C, WU C C, CHEN C W, et al. Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm [J]. Expert Systems with Applications, 2012, 39(11): 10016-10021.

[18] WANG M Y, SETHI S P, VAN DE VELDE S L. Minimizing makespan in a class of reentrant shops [J]. Oper Res, 1997, 45: 702-712.

[19] YANG D L, KUO W H, CHERN M S. Multi-family scheduling in a two-machine re-entrant flow shop with setups [J]. European J Oper Res, 2008, 187(3): 1160-1170.

[20] BRUCKER P, SCHLIE R. Job-shop scheduling with multi-purpose machine [J]. Computing, 1990, 45: 369-375.

[21] 井彩霞, 錢省三, 唐國春. 雙目標函數(shù)下需要安裝時間的平行多功能機排序問題[J]. 計算機集成制造系統(tǒng), 2010, 16(4): 867-872.

[22] ZHONG L W, LUO S C, WU L D, et al. A two-stage approach for surgery scheduling[J]. Journal of Combinatorial Optimization, 2012, 27(3): 545-556. doi: 10.1007/s10878-012-9535-2.

Modern scheduling and its applications

TANG Guo-chun①, JING Cai-xia②
① School of Economics and Management, Shanghai Second Polytechnic University, Shanghai 201209, China; ② School of Management, Tianjin Polytechnic University, Tianjin 300387, China

Scheduling is the allocation of machines according to time in order to process the collection of jobs. It is a decision-making with the goals of optimizing one or more objectives. In the past decades, the study of scheduling has been advanced quickly. This article presentd a brief history and the recent developments of modern scheduling theory in China. Then, the applications in three focuses are prospected, namely supply chain, semiconductor manufacturing and surgical operation. A future perspective is provided at the end of the article.

scheduling, supply chain, semiconductor/wafer, surgical operation

(編輯：溫文)

10.3969/j.issn.0253-9608.2015.02.006

*國家自然科學基金資助項目(71371120)和天津市高等學校人文社會科學研究項目(20132144)資助

?通信作者，E-mail：gctang@sspu.edu.cn