面向離散制造業的生產調度算法研究與系統設計

姜 康，莊懷天，咸 凱

(合肥工業大學 交通運輸工程學院，合肥 230009)

?

面向離散制造業的生產調度算法研究與系統設計

姜 康，莊懷天，咸 凱

(合肥工業大學 交通運輸工程學院，合肥 230009)

針對離散制造業的單件、小批量生產模式，分析其特點與企業需求，設計合理的系統流程和功能組成。構建以生產批次為單位的，基于時間和成本約束的多目標優化模型，利用改進的遺傳算法求解調度模型的最優解。開發出符合離散生產模式的調度管理系統，通過實例驗證其有效性及可行性。

遺傳算法；時間和成本；設計開發；調度管理系統

0 引言

車間計劃與調度是企業車間管理的重點和難點，良好的計劃與調度系統對縮短生產周期，提高經濟效益十分有效[1-2]。近年來，越來越多的企業和學者投入大量的精力來研究車間調度。目前，研究方向主要分為兩個方面：一個就是調度系統的設計開發；另一個主要集中在調度模型的建立及調度算法的改善。如邵佳楠等在我國中小型離散制造業基礎上，研究適用的車間生產調度模式[3]；李鑫等人著重分析調度系統的結構、需求和功能組成，對系統的關鍵技術進行了深入的研究[4]；金峰等對生產調度的問題及解決方法做出了系統的歸納總結[5]。在調度模型及算法設計方面成果突出，如李京生等人在云制造技術面向服務思想的啟發下，構建了基于動態資源能力服務的分布式協同調度并取得了良好的效果[6]；崔維偉等人綜合考慮生產調度與設備維修，構建了基于周期性維護的最大加工時間最短的數學模型[7-9]。

目前對流程工業及大批量生產的調度系統研究已經非常成熟了，但對于離散企業的調度問題，還一直是難點。本文通過計劃管理的分批操作實現單件小批量生產，將處理后的小批量作為整體進行生產調度，并建立基于時間和成本的調度模型，通過遺傳算法優化目標函數。最終設計開發出能夠適應于單件小批量生產模式的調度系統。

1 系統整體設計

1.1 系統需求分析

離散制造業由于其特有的生產模式，使其在計劃制定與車間調度方面還存在許多問題。此外，車間生產現場的多變性也增加了調度執行的難度，所以在采用計算機調度的同時還應保留計劃員工的經驗操作。對超期的生產計劃，系統應能夠提供在更改車間及設備生產日歷的前提下進行重調度。

1.2 系統流程設計

根據企業生產實際，詳細設計任務指派子模塊的實現流程；同時生產現場變化多端，沒有任何一種計算機調度算法可以完全取代員工的作用，而且完全依賴計算機的調度并不能滿足生產實際。綜合考慮，本系統的主要流程如圖1所示。

圖1 系統流程圖

1.3 系統功能設計

結合生產實際和系統功能需求分析，最終確定系統的功能組成包括系統管理及任務指派兩個部分。系統管理以實現用戶添加、信息修改及車間與設備工作日歷的制定等功能；任務指派主要目的是管理車間計劃及對任務調度，具體如圖2所示。

圖2 系統的功能模型圖

2 調度建模與算法設計

2.1 調度的數學建模

為了方便車間調度問題，現做出如下假設：

(1)同一批次工件集中的各工件加工工藝相同、加工時間及成本都相同，并忽略各工件間的準備時間；

(2)車間中所有設備均完好，且能夠加工所有任務，只是時間和成本不同；

(3)同一時間，某個工件集的某個工序只能在一臺設備上加工；

(4)同一時間，某臺設備只能加工某個工件集的某個工序。

(1)

(2)

(3)

(4)

?α1≥0，?α2≥0

(5)

0≤i≤l，0≤j≤ki，0≤n≤m

(6)

模型的說明如下：

式(1)為基于時間和成本約束的目標函數；式(2)為變量的取值范圍；式(3)保證每個工序任務只能分配一次，且只能分配到某一個設備；式(4)保證任務的加工順序是按照工藝要求的；式(5)為加權值，為保證目標函數中時間和成本的量綱一致，α1的單位為分鐘，α2的單位為元；式(6)為各下標的取值范圍。

2.2 算法設計

本文采用改進的遺傳算法來求解調度最優解，算法設計如下：

(1)編碼和解碼

本文采用基于設備的編碼方式，每個染色體代表的是分配到設備上的工序任務和任務開始的先后順序。

(2)適應度函數

本文將求解式(1)的最小值作為適應度函數，即g(x)=Min f(x)。

(3)選擇、交叉和變異

采用比例選擇算子的方式來執行選擇操作，將概率大的個體的基因盡可能的保存下來。只對表示設備編號的基因位進行交叉，表示任務順序的基因位仍采用隨機生成發。而變異的過程中，則考慮設備編號和任務順序各自單獨變異。

2.3 調度實例

將5個工件集合理分配到5臺設備上加工，每個工件集包含3個工序任務。表1和表2分別表示在不同設備上工序任務消耗的時間和成本。

表1 不同設備加工不同任務的時間消耗

表2 不同設備加工不同任務的成本消耗

結合生產實際，參數設置如下：α1=1，α2=1，初始種群為20，交叉和變異的概率分別為0.7與0.08，迭代次數為500。仿真得出在迭代132次左右的時候消耗最小，約為149.1。對應的工序任務分配順序如表3所示。

表3 任務分配順序

當只考慮時間時，雖然完工時間提前，但總消耗卻增加了很大，出現了局部最優的情況，充分說明了該調度模型的優越性。考慮到設備5僅執行了一個任務，若將其取出，通過仿真可以發現，所有任務完成是的總消耗反而增加了，這說明任務較多時設備數足夠多反而可以降低消耗。

3 系統應用實例

本文中設計的生產調度系統采用B/S結構體系，利用Java及Oracle11g相關技術，在Eclipse開發平臺上開發適應于離散制造企業的調度系統。以下為該系統的應用實例：

(1)系統管理

系統管理的主要功能包括用戶添加刪除及修改角色權限、車間日歷制定和設備日歷制定與修改，如圖3、圖4所示。

圖3 用戶管理

圖4 車間日歷制定與修改

圖3是用戶管理，主要提供給系統管理員添加用戶、修改用戶信息等功能；圖4是車間日歷管理和制定車間日歷，通過圖3用戶可以查詢該車間工作日和休息日及工作日的工作時間段，圖4即制定某一車間的工作日歷，剔除非工作日及安排每天工作時間；設備日歷的管理與制定與實例圖4，這里就不再累述。

(2)任務指派

任務指派是該系統的核心模塊，其中車間生產調度就包含著該模塊中。任務指派主要有車間計劃管理、生產資源準備、加工計劃調度、加工計劃審核與生產任務派工。各功能的實現實例如圖5～圖8所示。

圖5 車間計劃管理與資源準備

圖6 加工計劃調度

圖7 加工計劃審核

圖8 生產任務派工

圖5是計劃管理與資源準備的應用實例，這里包括對計劃分批處理，主要是每批次需加工的數量、開始結束時間等，還可以對計劃分批的詳情作一定的修改。資源準備，主要是指毛坯的準備情況，對于不足的資源應盡快下達外購指令或者尋找替代品。圖6是調度模塊，該部分內嵌算法，通過自動調度將各計劃按照工藝文件自動分解并合理安排加工設備及起始時間，對于超過交貨期的任務可以調整設備日歷或者任務的優先級，重新調度直至滿足交貨期為止。調度時還可以查詢設備的負荷率，以促進設備利用率的提高。調度時優先考慮優先級，其次考慮目標函數，即總消耗最小。圖7是加工計劃審核，可以錄入審核人員對計劃審核的意見。圖8主要實現的是生產任務派工，對通過審核的調度及資源準備計劃，可以生成派工單下達到車間生產加工。

4 結論

本文主要內容是設計面向離散制造業的車間生產調度系統，對系統的需求、流程及功能組成進行了詳細的分析。研究針對單件小批量生產模式的調度模型及算法，建立了以批次為單位的基于時間和成本的多目標優化模型，用改進的遺傳算法驗證模型的有效性。最后，在前文研究基礎上，開發出所設計的調度系統，通過某離散企業的實際試用證明系統的可行性和有效性。

[1] MESA International. The Benefits of MES: A Report From The Field[R]. MESA International White Paper,1997.

[2] Sieberg J, Walter R. A scheduling and resource optimizing MES for the semiconductor and MEMS industry [J]. Advanced Semiconductor Manufacturing Conference and Workshop, 2003: 101- 105.

[3] 邵秋楠，耿也.中小型離散制造企業車間生產調度模式的設計[J].組合機床與自動化加工技術，2011(3)：105-107.

[4] 李鑫，夏莜筠，常曉芳.企業車間生產調度MES系統的設計與研究[J].組合機床與自動化加工技術，2010(8):109-112.

[5] 金峰，吳澄.大規模生產調度問題的研究現狀與展望[J].計算機集成制造系統，2006，12(2)：161-167.

[6] 李京生，王愛民,唐承統,等.基于動態資源能力服務的分布式協同調度技術[J].計算機集成制造系統，2012，18(7)：1563-1574.

[7] 崔維偉，陸志強，潘爾順.基于多目標優化的生產調度與設備維護集成研究[J]. 計算機集成制造系統，2014，20(4)：1398-1404.

[8] 王桂娜，俞秉昊，潘爾順,等.成組生產條件下考慮學習和遺忘效應及設備維護的調度策略[J].上海交通大學學報，2013，47(5)：723-727.

[9] 黃方明，陸志強，崔維偉.平行機系統生產調度與維護計劃聯合優化[J].工業工程與管理，2013，18(4)：49-55.

(編輯 李秀敏)

Scheduling Algorithm Research and System Design for Discrete Manufacturing Industry

JIANG Kang, ZHUANG Huai-tian, XIAN Kai

(School of Transportation Engineering, Hefei University of Technology, Hefei 230009, China)

On account of discrete manufacturing industry’s single piece and batch production mode, the paper analyzed its characteristics and demand, and the system process and functional composition were designed. Built multi-objective optimization mode in consideration of time and cost based on batch production, then used genetic algorithm to seek for the optimal solution. Exploited a scheduling management system which is fit for discrete industry, a example was taken to verify its validity and feasibility.

genetic algorithm; time and cost; design and develop; scheduling management system

1001-2265(2016)11-0154-03

10.13462/j.cnki.mmtamt.2016.11.041

2016-01-08

國防基礎科研重大項目資助(A1120131044)；國防技術基礎項目資助(JSBZ2014210A005，JSBZ2014210b007)

姜康(1974—)，男，山東文登人，合肥工業大學副教授，研究生導師，研究方向為數字化設計與制造、信息與控制；通訊作者：莊懷天(1989—)，男，安徽宿州人，合肥工業大學碩士研究生，研究方向為數字化設計與制造，(Email)zhuanghuaitian@126.com。

TH162;TG65

A