復雜窗時(shí)排序問(wèn)題及算法研究簡(jiǎn)介，目錄書(shū)摘

 生產(chǎn)調度是根據企業(yè)生產(chǎn)系統的生產(chǎn)目標和環(huán)境狀態(tài)，在盡可能滿(mǎn)足約束條件（如交貨期、工藝要求和路線(xiàn)、資源現狀）的前提下，按照工藝規程和計劃，通過(guò)下達生產(chǎn)計劃及調度指令對系統內的可用資源進(jìn)行實(shí)時(shí)任務(wù)分配，以達到縮短產(chǎn)品的制造周期、減少在制品、降低庫存、提高生產(chǎn)資源的利用率及提高制造系統生產(chǎn)率等目的。
影響生產(chǎn)調度問(wèn)題的因素很多，正常情況下有產(chǎn)品的投產(chǎn)期、交貨期（完成期）、生產(chǎn)能力、加工順序、加工設備和原料的可用性、批量大小、加工路徑、成本限制等，這些都是所謂的約束條件。有些約束條件是必須要滿(mǎn)足的，如交貨期、生產(chǎn)能力等，而有些達到一定的滿(mǎn)意度即可，如生產(chǎn)成本等。
為了避免儲存及隱藏的額外運轉帶來(lái)的高費用，例如，由于等待、傳遞、額外勞動(dòng)力、重加工及訂單改變等引起的效益損失，生產(chǎn)商不僅考慮延誤帶來(lái)的懲罰還必須顧及提前完工付出的費用，這就是準時(shí)排序問(wèn)題。它限定工件的交貨期：如果工件在交貨期之前完工，會(huì )出現儲存費和保管費之類(lèi)；而在交貨期之后完成，固然要科以罰款，則會(huì )產(chǎn)生延誤賠償甚至失去合作機會(huì )等損失。而準時(shí)排序的目的就是要小化這些費用之和，所以，在“準時(shí)”概念中，盡可能使得工件的完工時(shí)間接近其交貨期或者提前和延誤的工件個(gè)數盡量少。因此，提前和延誤應該盡可能地避免，這也使得以前討論的傳統性能函數無(wú)效。既然目標函數是關(guān)于工件完工時(shí)間的非正則函數，問(wèn)題的研究相對比較困難。
現實(shí)中，供應商和客戶(hù)在簽訂供應合同時(shí)，通常會(huì )指定一個(gè)交貨時(shí)間區間，如果工件在這個(gè)時(shí)間區間內完成則被認為是準時(shí)的，不會(huì )招致任何處罰。它是將交貨期合理地設置成一個(gè)時(shí)間段，而不再是單個(gè)時(shí)間點(diǎn)，這種排序稱(chēng)為窗時(shí)排序。我們把這個(gè)時(shí)間區間稱(chēng)為工件的交貨期窗口，該窗口的左端為早交貨期（或稱(chēng)“交貨期窗口的位置”）、右端為晚交貨期。如果工件在窗時(shí)交貨期前完成，則必須被庫存，這種情況視為一個(gè)提前處罰。另外，如果工件在交貨期窗口后完成，根據合同中的規定，它將導致延遲懲罰。顯然，如果交貨期窗口較大則可以增加供應商生產(chǎn)和輸送的靈活性。然而，設置大型的交貨期窗口和延遲工件完成時(shí)間都會(huì )降低供應商的競爭力和客戶(hù)服務(wù)水平。所以交貨期窗口的設置也經(jīng)常成為問(wèn)題的目標之一。
本書(shū)探討的內容都是對經(jīng)典排序的突破，研究現代排序與準時(shí)、窗時(shí)排序的結合應用，目的是為了在新型排序環(huán)境下，使某個(gè)衡量函數大或者小，如提前時(shí)間、延誤時(shí)間、提前或延誤的工件個(gè)數及交貨期窗口的確定等。
粗略來(lái)講，有兩類(lèi)相關(guān)的懲罰函數。一類(lèi)目標函數中，提前和延誤懲罰依賴(lài)于工件是否提前或延誤，而不是提前或延誤了多長(cháng)時(shí)間。這類(lèi)問(wèn)題關(guān)注的是提前和延誤的賦權工件數。另一類(lèi)是提前時(shí)間和延誤時(shí)間所帶來(lái)的懲罰，即與完工時(shí)間距離交貨期窗口的時(shí)間差成正比。此類(lèi)目標函數既普遍又具備很強的競爭力。另外，交貨期窗口的位置和大小也具有一定的決策意義，被很多生產(chǎn)商作為衡量有效性的一個(gè)重要指標。例如，決定訂單數量及耗費資源計劃等，所以它們往往作為決策變量，需要與工件的優(yōu)序列一起確定。本書(shū)探討復雜生產(chǎn)環(huán)境下窗時(shí)排序問(wèn)題的一些特點(diǎn)和解決方法，總結如下。
①就交貨期窗口的位置和大小是給定還是待定的幾種情況進(jìn)行了討論，針對目標函數是關(guān)于提前、延誤的工件個(gè)數或者時(shí)間，以及它們的綜合目標函數展開(kāi)研究，充分利用了工件位置的累計權重，并提出相應的有效算法。
②討論了工件有公共交貨期窗口的同時(shí)加工排序問(wèn)題，工件的尺寸大小相同，在交貨期窗口給定或其位置待定情況下，以小化總的提前和延誤懲罰；并且如果交貨期窗口是待定參數時(shí)，總費用包含該決策費用。針對兩種目標函數分別研究；尤其當批的容量有限時(shí)，乃是經(jīng)典排序的推廣。在尋找它們的優(yōu)算法時(shí)，“位置權”已不再有效。
在以前關(guān)于同時(shí)加工排序問(wèn)題的研究中，只有幾篇文獻涉及交貨期的存在性，以小化總延誤或大延誤。本書(shū)把窗時(shí)排序推廣到了多個(gè)工件可以被同時(shí)加工的情況，目標是要把工件分成多個(gè)批、再排列批的次序使得總費用低。在提出優(yōu)性質(zhì)和參數分析的基礎上，給出了批容量無(wú)界時(shí)的一些有效算法。研究有界的同時(shí)加工排序問(wèn)題。當提前和延誤懲罰系數是任意整數且窗口位置待定時(shí)，把3-劃分的一個(gè)實(shí)例轉化到該問(wèn)題，從而證明了它是強NP-完備的。進(jìn)而提出幾個(gè)優(yōu)性質(zhì)，但優(yōu)排序已不再滿(mǎn)足SPT-批序，問(wèn)題更加難于研究。
③現實(shí)生產(chǎn)中有以下情形：具有相似特征的一些工件需要相同的生產(chǎn)場(chǎng)景和設備，所有工件被分成多個(gè)組，于是從加工一個(gè)組的工件轉化到加工另一個(gè)組的工件時(shí)需要執行安裝任務(wù)。正是由于安裝任務(wù)的介入使得問(wèn)題更加困難。討論當交貨期窗口給定時(shí)以小化賦權提前時(shí)間和延誤時(shí)間總和的問(wèn)題，問(wèn)題的復雜性未知。本書(shū)探討了小化提前和延誤的工件個(gè)數，其中交貨期窗口的位置待定或者位置和大小均待定。
④批調度問(wèn)題中每個(gè)工件有其特定的尺寸大小，即差異工件，同一批中工件的總尺寸不能超過(guò)批的容量限制，因此，包含在每一批中的工件個(gè)數可能不同。研究加工時(shí)間、尺寸等參數對費用的影響及優(yōu)調度所具有的結構特點(diǎn)，并提出了啟發(fā)式算法，該算法充分利用了參數信息并簡(jiǎn)便易行。
本書(shū)通過(guò)對上述研究?jì)热莺蛣?chuàng )新點(diǎn)的討論，深入分析各種生產(chǎn)環(huán)境因素對總費用的影響，建立綜合性的目標函數表達式，分析參數特點(diǎn)及優(yōu)解的結構化性質(zhì)，得出相應的算法并分析其復雜性。

第1章緒論 /

11排序問(wèn)題的背景及描述 /

12現代排序 /

13算法中的幾個(gè)重要概念 /

14準時(shí)排序及相關(guān)結果 /

15窗時(shí)排序及相關(guān)結果 /

16符號表示 /

17本書(shū)的貢獻與組織結構 /

第2章最小化提前/延誤的賦權工件個(gè)數 /

21引言 /

22交貨期窗口的位置待定 /

23交貨期窗口的大小待定 /

24交貨期窗口的位置和大小均待定 /

25給定的交貨期窗口 /

26推廣到多臺平行機 /

27結語(yǔ) /

第3章最小化提前和延誤時(shí)間懲罰 /

31引言 /

32交貨期窗口給定 /

33交貨期窗口的位置待定 /

34多個(gè)綜合目標 /

35推廣到多臺機器 /

36結語(yǔ) /

第4章有交貨期窗口的無(wú)界批處理 /

41批處理問(wèn)題 /

42相關(guān)研究結果 /

43給定的交貨期窗口 /

44交貨期窗口的位置待定 /

45結語(yǔ) /

第5章關(guān)于非準時(shí)工件數的有界批處理 /

51問(wèn)題描述 /

52最優(yōu)性質(zhì) /