排序與調度的理論、模型和算法（簡體書）

本書是編者在廣泛收集國內外相關文獻和資料的基礎上，結合自己的研究成果編寫而成，旨在為相關專業的高年級大學生、研究生和科研工作者提供系統、深入的排序與調度理論和算法方面的基礎知識.

萬國華，上海交通大學特聘教授、博士生導師，安泰經濟與管理學院副院長。在香港科技大學取得博士學位，並在香港科技大學、澳門大學和美國紐約大學從事科研和教學工作，2011年獲“國家杰出青年科學基金”。主持完成10余項國家及省部級研究項目，出版英文學術著作一部，研究成果發表於Operations Research等國際權威學術刊物。現任Production and Operations Management的高級編輯，中國管理科學與工程學會常務理事和上海市運籌學會副理事長。

本書是排序與調度領域的入門書，《排序與調度叢書》為“十三五”國家重點圖書規劃項目，2017年國家出版基金資助

排序與調度問題的目標是按時間合理地安排稀缺資源，有效地完成給定的任務。排序與調度問題有著廣泛、深刻的應用背景，在製造業和服務業中均起著重要作用，是各類組織提高運營效率、降低成本乃至取得競爭優勢的重要手段和有力工具。
雖然排序與調度論的重要性並不亞於排隊論和庫存論，但它卻是運籌學的一個年輕分支。排序與調度數學模型的出現和分析幾乎比電話系統的排隊分析(Erlang，1909)和庫存論中的經濟批量模型(Harris，1913)晚了四五十年。1954年Johnson發表在Naval Research Logistics上的論文討論了兩臺機器上的流水作業問題，建立了問題的數學模型並給出了模型的求解算法。1956年Jackson把該模型擴展到異序作業情形，Smith研究了多個單機排序問題的模型和求解算法。這些研究工作揭開了排序與調度問題研究的序幕，從此，排序與調度問題的研究得到飛速發展和廣泛應用，取得了重大的經濟效益和社會效益。自20世紀70年代以來，我國也有不少學者研究了排序與調度問題。其中，越民義、韓繼業、唐國春、林詒勛和陳榮秋等學者在此領域做出了突出貢獻。目前，我國從事排序與調度問題研究的人員數量增長迅速，但除了學術刊物上的論文和若干介紹文章之外，排序與調度方面的教材和專著還不夠多。隨著排序與調度問題研究的飛速發展，新問題、新模型和新方法不斷涌現，同時，對排序與調度問題有興趣的研究人員也越來越多，因此亟須全面、系統地介紹排序與調度的理論、模型和算法的書籍。
本書的編寫主要取材於Pinedo(2016)、Baz·ewicz等(2001)、Parker(1995)、Baker和Trietsch(2009)等的教材和專著及學術刊物上的相關文獻，並結合了編者的教學和研究實踐。全書共分8章： 第1章介紹排序與調度問題的定義、功能和作用，並給出製造和服務業中若干排序與調度問題的實例； 第2章討論排序與調度問題的表示及分類，以及分析和求解排序與調度問題的一般方法； 第3~8章介紹單臺機器排序與調度問題及其高階模型、多臺平行機排序與調度問題、流水作業、異序作業和自由作業排序與調度問題。
本書在每章後有一個小結與討論，內容主要是本章小結及重要參考文獻，並對相關問題的研究歷史作簡要的介紹。章後附有大量的參考文獻，在提供排序與調度問題基礎知識的同時，也有利於初學者了解排序與調度問題的歷史和發展，以激發學習和研究的興趣。
本書的編寫得益於唐國春先生的極力推動，並得到了“排序與調度叢書”編輯委員會各位同仁的鼎力支持，清華大學出版社汪操編輯在本書的出版過程中提供了有力的支持和幫助。沒有他們的支持與幫助，很難想象編者可以完成本書的編寫。編者在本書的寫作過程中與Pinedo教授有多次交流，受益匪淺，他的名著Scheduling： Theory, Algorithms and Systems是本書寫作的主要參考書。越民義、韓繼業和唐國春三位先生在百忙中撥冗審閱了本書，李德彪博士幫助整理了參考文獻。在此，編者對上述各位表示衷心的感謝！
本書的寫作得到國家自然科學基金(項目號：71125003和71421002)的資助，特此鳴謝。
由於編者學術水平以及寫作時間的限制，書中一定存在不少缺點和不當之處，敬請讀者和同仁批評指正，以便在再版時修訂。

萬國華上海交通大學2018年12月

第1章引論

1．1排序與調度： 定義、功能和作用

1．1．1排序與調度問題的定義

1．1．2排序與調度問題在製造/服務業中的地位與功能

1．2排序與調度： 典型問題舉例

1．2．1工廠的產品裝配問題

1．2．2集裝箱碼頭吊車調度問題

1．2．3醫院護士排班問題

1．2．4計算機系統中的進程調度問題

1．3小結與討論

參考文獻

第2章排序與調度問題： 定義、分類和求解

2．1排序與調度問題： 定義和記號

2．2排序與調度問題： 解的定義及類型

2．3排序與調度問題： 計算複雜性層次

2．4排序與調度問題的分析和求解

2．5小結與討論

參考文獻

第3章單機排序與調度： 基本模型

3．1(加權)總完工時間問題

3．1．1問題1‖∑wjCj

3．1．2問題1|rj|∑wjCj

3．1．3問題1|d～j|∑wjCj

3．2延遲問題和延誤問題

3．3總延誤問題

3．4（加權）總延誤問題

3．5(加權)延誤工件總數問題

3．6小結與討論

參考文獻

第4章單機排序與調度： 高階模型

4．1工件存在約束關係的問題

4．1．1工件之間約束關係的有向圖

4．1．2(加權)總完工時間問題

4．1．3問題1|prec|hmax

4．1．4問題1|prec|∑gj(Cj)

4．2非正則目標函數問題

4．2．1問題1|dj=d|∑(Ej Tj)

4．2．2問題1‖∑(w1jEj w2jTj)

4．3存在設置時間的問題

4．3．1問題1|sjk|Cmax

4．3．2問題1|fmls，sgh|∑wjCj

4．3．3問題1|fmls，sgh|Lmax

4．3．4問題1|fmls，sgh|∑Uj

4．4小結與討論

參考文獻

第5章平行機排序與調度

5．1時間表長度問題

5．1．1問題Pm‖Cmax及問題Pm|prec|Cmax

5．1．2問題Pm|prmp|Cmax

5．1．3問題Pm|prec|Cmax

5．1．4問題Pm|prmp，prec|Cmax

5．1．5問題P∞|prec|Cmax

5．2（加權）總完工時間問題

5．2．1問題Pm‖∑Cj

5．2．2問題Pm|prec|∑Cj

5．3目標函數與交貨期相關的問題

5．4小結與討論

參考文獻

第6章流水作業排序與調度

6．1流水作業： 無限緩衝區

6．2流水作業： 有限緩衝區

6．3柔性流水作業

6．4小結與討論

參考文獻

第7章異序作業排序與調度

7．1異序作業排序與調度問題

7．2問題的析取圖表示

7．3分支定界法

7.4移動瓶頸法

7．5小結與討論

參考文獻

第8章自由作業排序與調度

8.1時間表長度問題

8.1.1不可中斷情形： 問題Om‖Cmax

8.1.2可中斷情形： 問題Om|prmp|Cmax

8.2延遲問題

8.2.1不可中斷情形： 問題Om‖Lmax

8.2.2可中斷情形： 問題Om|prmp|Lmax

8.3其他自由作業問題

8．4小結與討論

參考文獻

索引

附錄A英漢排序與調度詞匯

第1章引論
排序與調度是一類在製造業和服務業中均起到重要作用的決策過程。排序與調度問題廣泛存在於采購和生產、運輸和配送、數據處理和通信，以及各類服務系統中。作為企業中的一項重要職能，排序與調度利用數學模型或啟發式方法，為需要完成的一系列任務按時間分派有限的資源，使得企業可以好地完成這些任務。
簡單地說，排序與調度理論(theory of scheduling)是一門研究如何地為一系列任務(tasks)按時間分派資源(resources)的學科。這裡，資源可以是工廠中的機器、機場中的跑道、工程項目中的工人，或者計算系統中的處理器； 任務則是工廠中需要加工的工序(operations)、機場跑道上飛機的起飛和著陸、工程項目中的任務，以及計算系統中需要執行的程序。每一個任務可能有它的優先級別、就緒時間和交貨期； 排序與調度的目標是優化與時間相關的一個函數，例如： 小化完成全部任務的時間，或是小化超過交貨期的任務數量。
一般的排序與調度問題，盡管數學描述簡單易懂，但求解卻極其困難。這些問題內在的組合爆炸性質使得尋求問題的適當解(解或近似解)成為一個非常艱巨的任務。事實上，現在已有形式化的證據推測許多排序與調度問題在某種意義下是難解的，並且很可能真的就是難以求解的。然而，盡管這一事實令人沮喪，但這並不意味著研究這些問題沒有價值。事實上，這些問題的重要性沒有因為它們是難解的而變化，只是研究者需要改變研究該類問題的策略，可能需要在求解過程中略微減少對求解問題的期望。
無論如何，排序與調度理論與運籌學的其他分支一樣，在過去的五十年中得到了飛速發展，其模型和算法豐富多彩、蔚為大觀。本書的目的不僅是反映這種豐富多彩，也希望能夠培養讀者欣賞其中的美妙與智能。
1．1排序與調度： 定義、功能和作用
1．1．1排序與調度問題的定義

“排序與調度領域內許多早期的工作是在製造業推動下發展起來的，所以在描述排序與調度問題時很自然會使用製造業的術語。”(Baker，1974)雖然排序與調度問題在許多非製造領域中取得了相當多有意義的成果，但是製造業的術語仍然經常在使用。因此，往往把資源(resource)稱為機器(machine)，把需要處理的任務(task)稱為工件(job)。有時工件是由幾個存在先後次序約束而又相互聯繫著的基本任務(elementary task)所組成，這種基本任務稱為工序(operation)。
因此，在排序與調度論中，工件是被加工的物件，是需要完成的任務； 機器是對工件進行加工的主體，是完成任務所需要的資源； 排序與調度是在一定的約束條件下對工件和機器按時間進行分配並安排次序，使得某一個或幾個與時間相關的目標達到。
1．1．2排序與調度問題在製造/服務業中的地位與功能
在一個製造企業或服務組織中，排序與調度功能起著重要的作用。但這一功能不是獨立的，而是與其他功能相互聯繫的。它們之間的關係隨實際情況的變化可能大不相同，並且在現代信息技術條件下，通常是通過計算機管理信息系統相聯繫的。
(1) 製造中的排序與調度
對於一個一般的製造系統，排序與調度在其中的作用可描述如下。進入製造系統的訂單可描述為帶有交貨期的工件，這些工件在一定的約束條件下，由製造系統中的機器進行加工。在這一過程中，因為機器忙，有些工件的加工將被延遲； 或由於高優先級工件的到達，它們必須立即加工，因此有些工件的加工將被中斷。其他不可預期的事件，例如機器的損壞、工件加工時間的延長等，也必須考慮，否則這些事件將對排序與調度的結果產生重大影響。編制一個良好的排序與調度計劃(稱為時間表)有助於提升製造的效率和強化對工序的控制。
除了製造現場的影響外，組織中的其他部分，特別是生產計劃功能，直接影響排序與調度決策。生產計劃功能負責整個製造過程的中長期計劃，其目標是基於庫存水平、需求預測和資源狀況，優化整個製造中的產品組合和長期的資源分配。在一個製造系統中，排序與調度功能通常與製造資源計劃(manufacturing resource planning，MRP)系統相連接。在MRP系統中，每一個產品都有一個物料清單(bill of materials，BOM)，MRP系統記錄每一個部件的庫存情況。進一步，MRP系統使用批量(lotsizing)和成批(batching)的方法，決定購買每一部件的時間。但是，MRP系統通常沒有詳細的排序與調度功能，特別是當製造環境比較複雜的時候。詳細的排序與調度功能通常由高階計劃和調度(advanced planning and scheduling，APS)系統提供，而MRP系統中產品生產的數據是進行APS系統中排序與調度功能實現的基礎。圖1.1描述了一個典型製造系統中的排序與調度功能(Pinedo，2016)。

圖1.1製造系統中的排序與調度功能

(2) 服務中的排序與調度
服務系統的多樣性使得難以描述一個服務組織及其排序與調度系統。與製造系統相比，服務組織中的排序與調度功能面臨許多不同的問題，例如資源的儲備、人力資源的分配。服務系統中的排序與調度問題的求解方法與製造系統截然不同，但也必須與服務組織中的其他決策功能相聯繫。通常，這種聯繫也是基於一個強大的信息系統，但服務組織中並沒有一個與製造環境中的ERP類似的系統。服務系統中的排序與調度功能通常需要與需求預測和收益管理相聯繫．圖1.2描述了一個典型服務系統中的排序與調度功能。

圖1.2服務系統中的排序與調度功能

1．2排序與調度： 典型問題舉例
為了讓讀者對排序與調度問題有一個感性認識，並說明排序與調度論應用的廣泛性和深刻性，以下將描述一些排序與調度問題的實例。
1．2．1工廠的產品裝配問題
一個自行車製造商需要把多個零件裝配成一輛自行車。該公司有三個小組從事裝配工作。公司的工業工程部通過分析發現一輛自行車的裝配可以分為10個不同的工序，包括框架的準備、前輪/後輪的安裝和調節、鏈條安裝和踏