1 引言

    生產(chǎn)排程問題，又稱排序問題或生產(chǎn)調(diào)度問題，是針對一項可分解的工作(如產(chǎn)品制造)，探討在盡可能滿足約束條件(如交貨期、工藝路線、資源情況等)的前提下，通過下達生產(chǎn)指令，安排其每步操作使用哪些資源、其加工時間及加工的先后順序。以獲得產(chǎn)品制造時間或制造成本的最優(yōu)化。

    生產(chǎn)排程問題是對于具體生產(chǎn)問題的一種抽象和簡化。即便對單機排序問題，如果考慮n個作業(yè)而每個作業(yè)只考慮加工時間及與序列有關(guān)的準備時間，就可以規(guī)約到n個城市的TSP問題。一般的生產(chǎn)排程問題就更為復(fù)雜了，也就是說，絕大多數(shù)的生產(chǎn)排程問題都是NP-hard問題。常規(guī)的優(yōu)化算法研究這些生產(chǎn)排程問題已經(jīng)有很長一段時間了，而本文采用一種全新的算法和建模思想，使用邏輯優(yōu)化語言NCL對復(fù)雜的多約束、多目標的生產(chǎn)排程問題進行建模研究。

2 NCL介紹

    自然約束語言NCL是一門集邏輯、優(yōu)化算法及求解規(guī)則于一體的業(yè)務(wù)建模和問題求解的智能描述型語言。NCL采用混合集合規(guī)劃算法系統(tǒng)，支持在多種類型(特別是集合類型)上的混合約束推理，突破了傳統(tǒng)的線性求解機制，通過域切割算法體系和高效、靈活的求解規(guī)則控制，實現(xiàn)對復(fù)雜優(yōu)化問題的求解。

2.1 NCL語言的特點

    NCL是一門以基礎(chǔ)數(shù)理邏輯為語法的運籌學(xué)自然語言。人工智能的模式識別技術(shù)廣泛應(yīng)用于NCL的自然語法分析及語義識別，使用戶在面對復(fù)雜的工業(yè)優(yōu)化問題時，可以在更高層級關(guān)注對問題的建模。

    混合集合規(guī)劃(Mixed Set Programming，簡稱MSP)構(gòu)成NCL的算法內(nèi)核：支持求解布爾值、實數(shù)、整數(shù)、時間、索引及集合類型上的混合約束；支持一階邏輯、集合推理、實數(shù)域數(shù)值分析等�；旌霞�合規(guī)劃支持對復(fù)雜大規(guī)模問題進行業(yè)務(wù)邏輯一級的建模并求解。

    NCL是一門可以對搜索策略高度簡潔地進行編程的語言。它可以簡單靈活地實現(xiàn)對搜索樹的邏輯控制，包括對分支、回溯、搜索模式的邏輯控制，對軟約束的應(yīng)用，對多目標優(yōu)化及優(yōu)化步長的控制，對近似解的控制等。

2.2 NCL語言的算法與求解系統(tǒng)

    NCL的算法理念源于約束規(guī)劃(Constraint Programming)，它的核心思想是通過約束間的網(wǎng)狀關(guān)系聯(lián)合推理，合理、有效地切削組合優(yōu)化問題的解空間，抑制組合爆炸，從而達到求解問題的目的。NCL以混合集合規(guī)劃(MSP)為算法內(nèi)核，其算法屬于精確算法�；旌霞�合規(guī)劃并不是在推理中簡單地使用集合符號，而是嚴格、完備地使用集合論作為推理體系的一部分，從而實現(xiàn)一種能夠超越線性限制(不同于基于線性松弛算法的線性解算器)的、更通用的算法系統(tǒng)來求解約束滿足問題。

    簡而言之，NCL的求解系統(tǒng)基于約束切割(Constraint Cut)與深度優(yōu)先搜索(Depth-First Search)原則，其求解框架如圖1所示。首先用約束推理切割解的搜索空間：之后通過查詢關(guān)鍵變量對解空間進行完備的搜索。

圖1 NCL的求解框架

2.3 基于NCL的工程化開發(fā)

    實際生活中的優(yōu)化排程問題遠比學(xué)術(shù)問題復(fù)雜，如下面所列幾項。

• 數(shù)據(jù)邏輯復(fù)雜、約束繁瑣；
• 問題規(guī)模大，往往是上萬道工序：
• 除了優(yōu)化模型和算法，還需要相應(yīng)的結(jié)果可視化：
• 要求對結(jié)果的可視化交互，要求對結(jié)果進行二次優(yōu)化；
• 用戶在需求分析過程中對問題的理解經(jīng)常變化；
• 實施困難：周期長、見效慢、成本高……

    NCL是一門支持工程化開發(fā)的運籌學(xué)語言。NCL中包含豐富的、基礎(chǔ)性的、可參數(shù)化的優(yōu)化模塊，這些模塊往往獨立于行業(yè)，具有很強的通用性。NCL在需求不斷變化時可以進行低成本系統(tǒng)調(diào)整，便于使用者進行開發(fā)和維護。此外，NCL中包含一體化的結(jié)果顯示，如甘特圖、地圖、直方圖和統(tǒng)計表等，便于開發(fā)者進行高效、并行的開發(fā)和部署。

3 建模及求解

3.1 建模

    3.1.1 生產(chǎn)排程中的約束

    生產(chǎn)排程的主模型是在滿足訂單優(yōu)先級、設(shè)備生產(chǎn)能力、訂單和其工序的生產(chǎn)工藝等約束情況下，按照設(shè)備最大利用率、訂單最小延遲數(shù)等優(yōu)化目標，在一個周期內(nèi)，對各個設(shè)備上工序進行優(yōu)化排序。生產(chǎn)排程中的基礎(chǔ)約束包括：

• 資源的能力約束；
• 資源的工作時間約束；
• 資源的工作日歷約束；
• 訂單的優(yōu)先級約束；
• 不同訂單的耦合約束；
• 訂單各工序的次序約束；
• 訂單時間窗口約束；
• 工序的資源需求約束：
• 工序的時間窗口約束……

    3.1.2 生產(chǎn)排程的建模

    NCL建模的重點是對問題進行數(shù)理邏輯描述以設(shè)計優(yōu)化問題的數(shù)學(xué)模型。本節(jié)介紹對生產(chǎn)排程問題中幾個主要約束的建模。

    ①工作日歷約束

    對于任意一個工序i，工序?qū)嶋H加工時間長度workTimeTaski等于該工序所需資源的可工作時間ScheduleResourceresourceTaski；和該工序加工時間區(qū)間TimeTaski交集WorkTimeTaski的長度。復(fù)雜的工作日歷約束在NCL中高度簡潔的描述如下。

    ②工序?qū)�資源及時間的需求約束

    對于任意兩個不同工序i，J，所用資源resourceTaski不同或者加工時間TimeTaski不沖突。此約束稱為二維排程約束，是生產(chǎn)排程的核心約束。

    ③訂單的時間窗口約束

    訂單i的加工時間TimeJobi是該訂單的所有工序的加工時間集合TimeTask之并，要求TimeJobi在給定的開工時間tlJobi和完工時間t2Jobi之間。

3.2 求解規(guī)則

    在本模型的求解規(guī)則中，首先查詢工序所用資源，然后確定工序的開工時間，具體如下。

    在搜索策略的設(shè)計中，我們將精確算法和啟發(fā)式思想有機地結(jié)合在一起。一方面，生產(chǎn)排程模型中所有的約束都被嚴格滿足，確保求解的精確性；另一方面，求解規(guī)則中的最小松弛度和順序性等原則是啟發(fā)式的，以確保在求解過程中靈活、個性化地控制搜索樹過程。完備的二維排程算法和經(jīng)過大量數(shù)據(jù)驗證的通用型搜索策略確保對滿足所有約束的可行解的求解，并在此基礎(chǔ)上以回溯方式尋找更優(yōu)解直至求得最優(yōu)解。

3.3 結(jié)果輸出

    生產(chǎn)排程的結(jié)果輸出主要有表格、甘特圖、直方圖等幾種形式。

    ①將訂單、工序優(yōu)化后的時間和資源安排輸出到表格中，見表1。

    ②用甘特圖表示訂單、工序的安排情況。用戶不僅能直觀地查看生產(chǎn)計劃安排，還可對計劃進行What-If…交互，如圖2所示。

    ③用負荷圖(直方圖)呈現(xiàn)資源的周期利用率，以清晰地展現(xiàn)關(guān)鍵資源的使用狀況，如圖3所示。

3.4 交互功能

    交互功能是在結(jié)果可視化的基礎(chǔ)上，對已有的優(yōu)化排程結(jié)果進行局部調(diào)整。其重要性主要體現(xiàn)在：一方面是對突發(fā)事件的應(yīng)急處理，即對生產(chǎn)條件發(fā)生變化后的情況迅速地進行處理，以生成新的計劃；另一方面體現(xiàn)在通過不斷的What-If…交互進行分析并改善排程結(jié)果

表1 訂單執(zhí)行計劃表

圖2 設(shè)備-工序甘特圖

圖3 資源負荷圖

    基礎(chǔ)交互功能包括以下幾類。

    ①刪除訂單，是指在結(jié)果甘特圖上，將指定的單個或者多個訂單從計劃中刪除的操作。生產(chǎn)中如果遇到有些訂單停止生產(chǎn)，則可以通過該功能來刪除訂單，并進行二次優(yōu)化。

    ②插入訂單，是指在結(jié)果甘特圖上，將一個或多個新的訂單安排到原有計劃中的操作。生產(chǎn)中如果遇到緊急插單的情況，可以選擇不可拖期插入，二次優(yōu)化算出的結(jié)果可以保證新插入的訂單無拖期。

    ③拖拉，是指在結(jié)果甘特圖上，對指定工序的時間或者所用資源用鼠標進行直覺式修改的操作。拖拉操作可以改變指定工序的加工時問，也可以改變其所用的資源。拖動后優(yōu)化引擎會進行二次優(yōu)化，返回新的可行解。

4 應(yīng)用舉例

    為驗證本文中生產(chǎn)排程模型，我們以一個實例來進行說明。本例是某煙廠離散和流水混合的多條生產(chǎn)線的生產(chǎn)計劃與排程問題。在該問題中，工藝在部分設(shè)備上呈流水特征，在其它設(shè)備上呈離散特征，離散設(shè)備和流水設(shè)備交替排布。該問題主要目標有：

• 對已有的老式生產(chǎn)線的現(xiàn)有手工計劃進行試算，驗證其可行性；
• 對尚未建成的新式生產(chǎn)線，驗證其設(shè)備配置和產(chǎn)品配方是否能達到其產(chǎn)能要求：
• 針對新舊兩條生產(chǎn)線，對周期內(nèi)的訂單制定生產(chǎn)排程計劃。

    煙草行業(yè)生產(chǎn)自動化、精細化程度較高，對生產(chǎn)過程控制和質(zhì)量管理非常嚴格，生產(chǎn)計劃必須嚴格滿足工藝流程要求。而且該問題中行業(yè)性約束較多且復(fù)雜，如前日留柜、今日留柜、喂絲機選取、換批和換牌時間間隔、儲柜容量約束、儲柜試用時間的不確定性約束、同一品牌不同模塊關(guān)系約束等，對數(shù)學(xué)模型和算法是極大的挑戰(zhàn)。由于采用NCL語言建立的排程模型獨立于行業(yè)、抽象度高，非常易于擴展和維護，作者可以很方便、自然地建立煙草行業(yè)的生產(chǎn)排程模型。通過大量真實數(shù)據(jù)測試，證明算法效率高，計算速度快，結(jié)果滿足符合生產(chǎn)需要。結(jié)果甘特圖如圖4所示。

圖4 煙草生產(chǎn)線結(jié)果圖

5 總結(jié)

    本文對工業(yè)生產(chǎn)中常見的生產(chǎn)排程問題進行了研究�；�于NCL語言和POEM平臺，文中給出了全新的生產(chǎn)排程問題的建模方法。該方法使用混合集合規(guī)劃的求解算法體系，借鑒約束切割和分支搜索的算法思想，特別適用于復(fù)雜的、多約束的、多目標的離散生產(chǎn)排程問題。煙草行業(yè)的應(yīng)用結(jié)果表明，本文所設(shè)計的生產(chǎn)排程模型和算法對于對于大規(guī)模的復(fù)雜工業(yè)問題可以求得滿意的解。

核心關(guān)注：拓步ERP系統(tǒng)平臺是覆蓋了眾多的業(yè)務(wù)領(lǐng)域、行業(yè)應(yīng)用，蘊涵了豐富的ERP管理思想，集成了ERP軟件業(yè)務(wù)管理理念，功能涉及供應(yīng)鏈、成本、制造、CRM、HR等眾多業(yè)務(wù)領(lǐng)域的管理，全面涵蓋了企業(yè)關(guān)注ERP管理系統(tǒng)的核心領(lǐng)域，是眾多中小企業(yè)信息化建設(shè)首選的ERP管理軟件信賴品牌。

轉(zhuǎn)載請注明出處：拓步ERP資訊網(wǎng)http://www.ezxoed.cn/

本文標題：生產(chǎn)排程算法及工業(yè)應(yīng)用

本文網(wǎng)址：http://www.ezxoed.cn/html/solutions/1401936208.html