[發明專利]一種基于分布集魯棒并行機調度模型的生產調度方法

有效

• 申請號: 201710695985.8
• 申請日: 2017-08-15
• 公開（公告）號: CN107622338B
• 公開（公告）日: 2019-07-26
• 發明（設計）人: 宋士吉;常志琦
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/15
• 分類號: G06F17/15;G06F17/16;G06Q10/06
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 廖元秋

本發明體提出一種基于分布集魯棒并行機調度模型的生產調度方法，屬于生產調度及運籌學領域。該方法首先構建具有風險厭惡特性的分布集魯棒優化模型DR?PMSP?RA，根據模型的目標函數和約束條件，得到初始模型DR?PMSP?RA1的表達式；對DR?PMSP?RA模型的目標函數進行轉化，得到該目標函數的估計上界，并將初始模型轉化為估計模型DR?PMSP?RA2，該估計模型可分解為兩個獨立的子模型，對子模型分別求解，更優的子模型解即為整個模型的最優解，得到最優的生產調度方案。通過本方法建立的模型更加符合實際生產的情況，通過利用生產環境中更多的信息，可以在保證系統性能的情況下，降低決策的風險。

技術領域

本發明屬于生產調度及運籌學領域，特別涉及一種基于分布集魯棒并行機調度模型的生產調度方法，考慮在工件加工時間具有隨機不確定性的情況下，尋求風險最小的魯棒調度方案。

背景技術

制造業在我國國民經濟發展過程中居于非常重要的地位，其發展狀況直接影響我國的綜合實力。生產調度是制造系統重要的關鍵技術，旨在確保生產制造過程高效有序地進行。對生產過程設計合理的計劃與調度策略，可以有效縮短產品的生產周期，提高準時交單率，改善設備利用率并降低庫存。

在針對同型并行機問題的生產調度中，以往一般采用的是基于確定性模型的生產調度方法。在這種模型中，都假定工件的加工時間以及其他的參數是確定已知的。然而在現實加工過程中，由于機器或刀具條件、工人加工水平和加工環境等因素的影響，工件的加工時間往往存在著不確定性。在實際調度過程中忽略參數的不確定性，會導致模型求得的最優解并不可行。這使得在不確定環境下采用確定型模型得到的調度方案，在實際生產中難以達到決策者的事先預期。因此，針對具有不確定性的并行機調度問題的研究，逐漸引起了學者們的關注。

首先出現的針對調度問題中不確定性的研究，是隨機調度問題。在隨機調度模型中，不確定性參數被看作是一個分布已知的隨機變量，模型的優化目標往往是系統長期的性能期望。從80年代開始，學術界和工業界在不同的方向上展開了隨機調度問題的廣泛研究。總流經時間、最大拖期時間、加權總拖期時間以及總拖期工件個數等性能指標均已出現在隨機調度模型的優化目標中。雖然隨機調度模型在理論上對不確定性并行機調度問題的研究有很好的推進作用，但隨機調度模型的一些固有缺點，限制了其在實際的大規模生產調度中的應用。這些缺點主要體現在以下幾個方面：1)在隨機調度模型中，不確定參數的分布是需要精確知道的。然而在實際的生產環境中，隨著生產經營日益復雜，小批量個性化定制等生產模式的逐漸轉化，很多情況下精確的概率分布很難獲得，只能根據類似產品的加工時間來估計它的區間范圍。特別是在新產品，尤其是單件或單次加工的新產品方面，這個問題尤為突出。在這種情況下，基于隨機調度模型的生產調度方法將不再適用。2)在隨機調度模型中，一般采用某種系統性能的期望作為優化目標。這種目標比較適用于制定企業長期的發展計劃，而并不適合解決在每次實際運營過程中的利益最大化或風險最小化的問題。3)這類隨機調度模型的求解通常是NP-難的，一般只能通過啟發式算法或動態規劃算法來進行求解，隨著問題規模的逐漸擴大，求解隨機調度模型的難度將以指數形式增長。