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

唐國春，井彩霞

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

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

唐國春①?，井彩霞②

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

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

排序；供應(yīng)鏈；半導(dǎo)體/晶圓；手術(shù)

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

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

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

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

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

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

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

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

1 供應(yīng)鏈排序

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

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

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

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

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

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

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

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

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

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

(1) 可重入排序

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

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

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

(2) 多功能機(jī)排序問題

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

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

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

圖1 可重入加工示意圖

圖2 多功能機(jī)排序中工件與機(jī)器的對應(yīng)關(guān)系

(3) 同時(shí)加工排序

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

圖3 烤箱示意圖

3 手術(shù)排程

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

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

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

4 展望

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

(2013年12月18日收稿)■

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

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

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

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

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

[6] 國家自然科學(xué)基金委員會. 國家自然科學(xué)基金申請代碼[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(xué)普及出版社, 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] 唐國春. 供應(yīng)鏈排序的模型和方法[C]//袁亞湘, 等. 中國運(yùn)籌學(xué)會第八屆學(xué)術(shù)交流會論文集. 香港: 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]. 運(yùn)籌學(xué)學(xué)報(bào), 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] 井彩霞, 錢省三, 唐國春. 雙目標(biāo)函數(shù)下需要安裝時(shí)間的平行多功能機(jī)排序問題[J]. 計(jì)算機(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

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

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