1 引言

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

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

2 NCL介紹

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

2.1 NCL語言的特點(diǎn)

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

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

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

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

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

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

圖1 NCL的求解框架

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

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

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

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

3 建模及求解

3.1 建模

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

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

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

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

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

    ①工作日歷約束

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

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

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

    ③訂單的時(shí)間窗口約束

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

3.2 求解規(guī)則

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

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

3.3 結(jié)果輸出

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

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

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

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

3.4 交互功能

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

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

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

圖3 資源負(fù)荷圖

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

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

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

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

4 應(yīng)用舉例

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

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

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

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

5 總結(jié)

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

核心關(guān)注：拓步ERP系統(tǒng)平臺(tái)是覆蓋了眾多的業(yè)務(wù)領(lǐng)域、行業(yè)應(yīng)用，蘊(yùn)涵了豐富的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)載請(qǐng)注明出處：拓步ERP資訊網(wǎng)http://www.oesoe.com/

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

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