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

姜 康，莊懷天，咸 凱

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

?

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

姜 康，莊懷天，咸 凱

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

?α1≥0，?α2≥0

(5)

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

(6)

模型的說明如下：

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

2.2 算法設(shè)計(jì)

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

(1)編碼和解碼

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

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

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

(3)選擇、交叉和變異

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

2.3 調(diào)度實(shí)例

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

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

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

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

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

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

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

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

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

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

圖3 用戶管理

圖4 車間日歷制定與修改

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

(2)任務(wù)指派

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

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

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

圖7 加工計(jì)劃審核

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

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

4 結(jié)論

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

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

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

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

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

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

[9] 黃方明，陸志強(qiáng)，崔維偉.平行機(jī)系統(tǒng)生產(chǎn)調(diào)度與維護(hù)計(jì)劃聯(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ǔ)科研重大項(xiàng)目資助(A1120131044)；國防技術(shù)基礎(chǔ)項(xiàng)目資助(JSBZ2014210A005，JSBZ2014210b007)

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

TH162;TG65

A