1 引言
生產排程問題，又稱排序問題或生產調度問題，是針對一項可分解的工作(如產品制造)，探討在盡可能滿足約束條件(如交貨期、工藝路線、資源情況等)的前提下，通過下達生產指令，安排其每步操作使用哪些資源、其加工時間及加工的先后順序。以獲得產品制造時間或制造成本的最優化。
生產排程問題是對于具體生產問題的一種抽象和簡化。即便對單機排序問題，如果考慮n個作業而每個作業只考慮加工時間及與序列有關的準備時間，就可以規約到n個城市的TSP問題。一般的生產排程問題就更為復雜了，也就是說，絕大多數的生產排程問題都是NP-hard問題。常規的優化算法研究這些生產排程問題已經有很長一段時間了，而本文采用一種全新的算法和建模思想，使用邏輯優化語言NCL對復雜的多約束、多目標的生產排程問題進行建模研究。
2 NCL介紹
自然約束語言NCL是一門集邏輯、優化算法及求解規則于一體的業務建模和問題求解的智能描述型語言。NCL采用混合集合規劃算法系統，支持在多種類型(特別是集合類型)上的混合約束推理，突破了傳統的線性求解機制，通過域切割算法體系和高效、靈活的求解規則控制，實現對復雜優化問題的求解。
2.1 NCL語言的特點
NCL是一門以基礎數理邏輯為語法的運籌學自然語言。人工智能的模式識別技術廣泛應用于NCL的自然語法分析及語義識別，使用戶在面對復雜的工業優化問題時，可以在更高層級關注對問題的建模。
混合集合規劃(Mixed Set Programming，簡稱MSP)構成NCL的算法內核：支持求解布爾值、實數、整數、時間、索引及集合類型上的混合約束；支持一階邏輯、集合推理、實數域數值分析等�；旌霞弦巹澲С謱碗s大規模問題進行業務邏輯一級的建模并求解。
NCL是一門可以對搜索策略高度簡潔地進行編程的語言。它可以簡單靈活地實現對搜索樹的邏輯控制，包括對分支、回溯、搜索模式的邏輯控制，對軟約束的應用，對多目標優化及優化步長的控制，對近似解的控制等。
2.2 NCL語言的算法與求解系統
NCL的算法理念源于約束規劃(Constraint Programming)，它的核心思想是通過約束間的網狀關系聯合推理，合理、有效地切削組合優化問題的解空間，抑制組合爆炸，從而達到求解問題的目的。NCL以混合集合規劃(MSP)為算法內核，其算法屬于精確算法�；旌霞弦巹澆⒉皇窃谕评碇泻唵蔚厥褂眉戏枺菄栏�、完備地使用集合論作為推理體系的一部分，從而實現一種能夠超越線性限制(不同于基于線性松弛算法的線性解算器)的、更通用的算法系統來求解約束滿足問題。
簡而言之，NCL的求解系統基于約束切割(Constraint Cut)與深度優先搜索(Depth-First Search)原則，其求解框架如圖1所示。首先用約束推理切割解的搜索空間：之后通過查詢關鍵變量對解空間進行完備的搜索。
圖1 NCL的求解框架
2.3 基于NCL的工程化開發
實際生活中的優化排程問題遠比學術問題復雜，如下面所列幾項。
- 數據邏輯復雜、約束繁瑣；
- 問題規模大，往往是上萬道工序：
- 除了優化模型和算法，還需要相應的結果可視化：
- 要求對結果的可視化交互，要求對結果進行二次優化；
- 用戶在需求分析過程中對問題的理解經常變化；
- 實施困難：周期長、見效慢、成本高……
NCL是一門支持工程化開發的運籌學語言。NCL中包含豐富的、基礎性的、可參數化的優化模塊，這些模塊往往獨立于行業，具有很強的通用性。NCL在需求不斷變化時可以進行低成本系統調整，便于使用者進行開發和維護。此外，NCL中包含一體化的結果顯示，如甘特圖、地圖、直方圖和統計表等，便于開發者進行高效、并行的開發和部署。
3 建模及求解
3.1 建模
3.1.1 生產排程中的約束
生產排程的主模型是在滿足訂單優先級、設備生產能力、訂單和其工序的生產工藝等約束情況下，按照設備最大利用率、訂單最小延遲數等優化目標，在一個周期內，對各個設備上工序進行優化排序。生產排程中的基礎約束包括：
- 資源的能力約束；
- 資源的工作時間約束；
- 資源的工作日歷約束；
- 訂單的優先級約束；
- 不同訂單的耦合約束；
- 訂單各工序的次序約束；
- 訂單時間窗口約束；
- 工序的資源需求約束：
- 工序的時間窗口約束……
3.1.2 生產排程的建模
NCL建模的重點是對問題進行數理邏輯描述以設計優化問題的數學模型。本節介紹對生產排程問題中幾個主要約束的建模。
①工作日歷約束
對于任意一個工序i，工序實際加工時間長度workTimeTaski等于該工序所需資源的可工作時間ScheduleResourceresourceTaski；和該工序加工時間區間TimeTaski交集WorkTimeTaski的長度。復雜的工作日歷約束在NCL中高度簡潔的描述如下。
②工序對資源及時間的需求約束
對于任意兩個不同工序i，J，所用資源resourceTaski不同或者加工時間TimeTaski不沖突。此約束稱為二維排程約束，是生產排程的核心約束。
③訂單的時間窗口約束
訂單i的加工時間TimeJobi是該訂單的所有工序的加工時間集合TimeTask之并，要求TimeJobi在給定的開工時間tlJobi和完工時間t2Jobi之間。
3.2 求解規則
在本模型的求解規則中，首先查詢工序所用資源，然后確定工序的開工時間，具體如下。
在搜索策略的設計中，我們將精確算法和啟發式思想有機地結合在一起。一方面，生產排程模型中所有的約束都被嚴格滿足，確保求解的精確性；另一方面，求解規則中的最小松弛度和順序性等原則是啟發式的，以確保在求解過程中靈活、個性化地控制搜索樹過程。完備的二維排程算法和經過大量數據驗證的通用型搜索策略確保對滿足所有約束的可行解的求解，并在此基礎上以回溯方式尋找更優解直至求得最優解。
3.3 結果輸出
生產排程的結果輸出主要有表格、甘特圖、直方圖等幾種形式。
①將訂單、工序優化后的時間和資源安排輸出到表格中，見表1。
②用甘特圖表示訂單、工序的安排情況。用戶不僅能直觀地查看生產計劃安排，還可對計劃進行What-If…交互，如圖2所示。
③用負荷圖(直方圖)呈現資源的周期利用率，以清晰地展現關鍵資源的使用狀況，如圖3所示。
3.4 交互功能
交互功能是在結果可視化的基礎上，對已有的優化排程結果進行局部調整。其重要性主要體現在：一方面是對突發事件的應急處理，即對生產條件發生變化后的情況迅速地進行處理，以生成新的計劃；另一方面體現在通過不斷的What-If…交互進行分析并改善排程結果
表1 訂單執行計劃表
圖2 設備-工序甘特圖
圖3 資源負荷圖
基礎交互功能包括以下幾類。
①刪除訂單，是指在結果甘特圖上，將指定的單個或者多個訂單從計劃中刪除的操作。生產中如果遇到有些訂單停止生產，則可以通過該功能來刪除訂單，并進行二次優化。
②插入訂單，是指在結果甘特圖上，將一個或多個新的訂單安排到原有計劃中的操作。生產中如果遇到緊急插單的情況，可以選擇不可拖期插入，二次優化算出的結果可以保證新插入的訂單無拖期。
③拖拉，是指在結果甘特圖上，對指定工序的時間或者所用資源用鼠標進行直覺式修改的操作。拖拉操作可以改變指定工序的加工時問，也可以改變其所用的資源。拖動后優化引擎會進行二次優化，返回新的可行解。
4 應用舉例
為驗證本文中生產排程模型，我們以一個實例來進行說明。本例是某煙廠離散和流水混合的多條生產線的生產計劃與排程問題。在該問題中，工藝在部分設備上呈流水特征，在其它設備上呈離散特征，離散設備和流水設備交替排布。該問題主要目標有：
- 對已有的老式生產線的現有手工計劃進行試算，驗證其可行性；
- 對尚未建成的新式生產線，驗證其設備配置和產品配方是否能達到其產能要求：
- 針對新舊兩條生產線，對周期內的訂單制定生產排程計劃。
煙草行業生產自動化、精細化程度較高，對生產過程控制和質量管理非常嚴格，生產計劃必須嚴格滿足工藝流程要求。而且該問題中行業性約束較多且復雜，如前日留柜、今日留柜、喂絲機選取、換批和換牌時間間隔、儲柜容量約束、儲柜試用時間的不確定性約束、同一品牌不同模塊關系約束等，對數學模型和算法是極大的挑戰。由于采用NCL語言建立的排程模型獨立于行業、抽象度高，非常易于擴展和維護，作者可以很方便、自然地建立煙草行業的生產排程模型。通過大量真實數據測試，證明算法效率高，計算速度快，結果滿足符合生產需要。結果甘特圖如圖4所示。
圖4 煙草生產線結果圖
5 總結
本文對工業生產中常見的生產排程問題進行了研究。基于NCL語言和POEM平臺，文中給出了全新的生產排程問題的建模方法。該方法使用混合集合規劃的求解算法體系，借鑒約束切割和分支搜索的算法思想，特別適用于復雜的、多約束的、多目標的離散生產排程問題。煙草行業的應用結果表明，本文所設計的生產排程模型和算法對于對于大規模的復雜工業問題可以求得滿意的解。
核心關注：拓步ERP系統平臺是覆蓋了眾多的業務領域、行業應用，蘊涵了豐富的ERP管理思想，集成了ERP軟件業務管理理念，功能涉及供應鏈、成本、制造、CRM、HR等眾多業務領域的管理，全面涵蓋了企業關注ERP管理系統的核心領域，是眾多中小企業信息化建設首選的ERP管理軟件信賴品牌。
轉載請注明出處：拓步ERP資訊網http://www.guhuozai8.cn/
本文標題：生產排程算法及工業應用
相關文章
