姜 康，莊懷天，咸 凱

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

?

面向離散制造業(yè)的生產(chǎn)調(diào)度算法研究與系統(tǒng)設計

姜 康，莊懷天，咸 凱

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

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

遺傳算法；時間和成本；設計開發(fā)；調(diào)度管理系統(tǒng)

0 引言

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

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

1 系統(tǒng)整體設計

1.1 系統(tǒng)需求分析

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

1.2 系統(tǒng)流程設計

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

圖1 系統(tǒng)流程圖

1.3 系統(tǒng)功能設計

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

圖2 系統(tǒng)的功能模型圖

2 調(diào)度建模與算法設計

2.1 調(diào)度的數(shù)學建模

為了方便車間調(diào)度問題，現(xiàn)做出如下假設：

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

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

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

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

(1)

(2)

(3)

(4)

?α1≥0，?α2≥0

(5)

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

(6)

模型的說明如下：

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

2.2 算法設計

本文采用改進的遺傳算法來求解調(diào)度最優(yōu)解，算法設計如下：

(1)編碼和解碼

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

(2)適應度函數(shù)

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

(3)選擇、交叉和變異

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

2.3 調(diào)度實例

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

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

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

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

表3 任務分配順序

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

3 系統(tǒng)應用實例

本文中設計的生產(chǎn)調(diào)度系統(tǒng)采用B/S結(jié)構(gòu)體系，利用Java及Oracle11g相關技術，在Eclipse開發(fā)平臺上開發(fā)適應于離散制造企業(yè)的調(diào)度系統(tǒng)。以下為該系統(tǒng)的應用實例：

(1)系統(tǒng)管理

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

圖3 用戶管理

圖4 車間日歷制定與修改

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

(2)任務指派

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

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

圖6 加工計劃調(diào)度

圖7 加工計劃審核

圖8 生產(chǎn)任務派工

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

4 結(jié)論

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

[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] 邵秋楠，耿也.中小型離散制造企業(yè)車間生產(chǎn)調(diào)度模式的設計[J].組合機床與自動化加工技術，2011(3)：105-107.

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

[5] 金峰，吳澄.大規(guī)模生產(chǎn)調(diào)度問題的研究現(xiàn)狀與展望[J].計算機集成制造系統(tǒng)，2006，12(2)：161-167.

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

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

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

[9] 黃方明，陸志強，崔維偉.平行機系統(tǒng)生產(chǎn)調(diào)度與維護計劃聯(lián)合優(yōu)化[J].工業(yè)工程與管理，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—)，男，山東文登人，合肥工業(yè)大學副教授，研究生導師，研究方向為數(shù)字化設計與制造、信息與控制；通訊作者：莊懷天(1989—)，男，安徽宿州人，合肥工業(yè)大學碩士研究生，研究方向為數(shù)字化設計與制造，(Email)zhuanghuaitian@126.com。

TH162;TG65

A