姜 康，莊懷天，咸 凱

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

?

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

姜 康，莊懷天，咸 凱

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

?α1≥0，?α2≥0

(5)

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

(6)

模型的說明如下：

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

2.2 算法設(shè)計

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

(1)編碼和解碼

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

(2)適應(yīng)度函數(shù)

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

(3)選擇、交叉和變異

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

2.3 調(diào)度實例

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

表1 不同設(shè)備加工不同任務(wù)的時間消耗

表2 不同設(shè)備加工不同任務(wù)的成本消耗

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

表3 任務(wù)分配順序

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

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

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

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

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

圖3 用戶管理

圖4 車間日歷制定與修改

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

(2)任務(wù)指派

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

圖5 車間計劃管理與資源準(zhǔn)備

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

圖7 加工計劃審核

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

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

4 結(jié)論

本文主要內(nèi)容是設(shè)計面向離散制造業(yè)的車間生產(chǎn)調(diào)度系統(tǒng)，對系統(tǒng)的需求、流程及功能組成進行了詳細(xì)的分析。研究針對單件小批量生產(chǎn)模式的調(diào)度模型及算法，建立了以批次為單位的基于時間和成本的多目標(biāo)優(yōu)化模型，用改進的遺傳算法驗證模型的有效性。最后，在前文研究基礎(chǔ)上，開發(fā)出所設(shè)計的調(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)度模式的設(shè)計[J].組合機床與自動化加工技術(shù)，2011(3)：105-107.

[4] 李鑫，夏莜筠，常曉芳.企業(yè)車間生產(chǎn)調(diào)度MES系統(tǒng)的設(shè)計與研究[J].組合機床與自動化加工技術(shù)，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)資源能力服務(wù)的分布式協(xié)同調(diào)度技術(shù)[J].計算機集成制造系統(tǒng)，2012，18(7)：1563-1574.

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

[8] 王桂娜，俞秉昊，潘爾順,等.成組生產(chǎn)條件下考慮學(xué)習(xí)和遺忘效應(yīng)及設(shè)備維護的調(diào)度策略[J].上海交通大學(xué)學(xué)報，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

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

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

TH162;TG65

A