複雜窗時排序問題及算法研究

內容簡介

生產調度是根據企業生產系統的生產目標和環境狀態，在儘可能滿足約束條件（如交貨期、工藝要求和路線、資源現狀）的前提下，按照工藝規程和計畫，通過下達生產計畫及調度指令對系統內的可用資源進行實時任務分配，以達到縮短產品的製造周期、減少在制品、降低庫存、提高生產資源的利用率及提高製造系統生產率等目的。

影響生產調度問題的因素很多，正常情況下有產品的投產期、交貨期（完成期）、生產能力、加工順序、加工設備和原料的可用性、批量大小、加工路徑、成本限制等，這些都是所謂的約束條件。有些約束條件是必須要滿足的，如交貨期、生產能力等，而有些達到一定的滿意度即可，如生產成本等。

為了避免儲存及隱藏的額外運轉帶來的高費用，例如，由於等待、傳遞、額外勞動力、重加工及訂單改變等引起的效益損失，生產商不僅考慮延誤帶來的懲罰還必須顧及提前完工付出的費用，這就是準時排序問題。它限定工件的交貨期：如果工件在交貨期之前完工，會出現儲存費和保管費之類；而在交貨期之後完成，固然要科以罰款，則會產生延誤賠償甚至失去合作機會等損失。而準時排序的目的就是要小化這些費用之和，所以，在“準時”概念中，儘可能使得工件的完工時間接近其交貨期或者提前和延誤的工件個數儘量少。因此，提前和延誤應該儘可能地避免，這也使得以前討論的傳統性能函式無效。既然目標函式是關於工件完工時間的非正則函式，問題的研究相對比較困難。

現實中，供應商和客戶在簽訂供應契約時，通常會指定一個交貨時間區間，如果工件在這個時間區間內完成則被認為是準時的，不會招致任何處罰。它是將交貨期合理地設定成一個時間段，而不再是單個時間點，這種排序稱為窗時排序。我們把這個時間區間稱為工件的交貨期視窗，該視窗的左端為早交貨期（或稱“交貨期視窗的位置”）、右端為晚交貨期。如果工件在窗時交貨期前完成，則必須被庫存，這種情況視為一個提前處罰。另外，如果工件在交貨期視窗後完成，根據契約中的規定，它將導致延遲懲罰。顯然，如果交貨期視窗較大則可以增加供應商生產和輸送的靈活性。然而，設定大型的交貨期視窗和延遲工件完成時間都會降低供應商的競爭力和客戶服務水平。所以交貨期視窗的設定也經常成為問題的目標之一。

本書探討的內容都是對經典排序的突破，研究現代排序與準時、窗時排序的結合套用，目的是為了在新型排序環境下，使某個衡量函式大或者小，如提前時間、延誤時間、提前或延誤的工件個數及交貨期視窗的確定等。

圖書目錄

第1章緒論 /

11排序問題的背景及描述 /

12現代排序 /

13算法中的幾個重要概念 /

14準時排序及相關結果 /

15窗時排序及相關結果 /

16符號表示 /

17本書的貢獻與組織結構 /

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

21引言 /

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

複雜窗時排序問題及算法研究

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條