基于準(zhǔn)時(shí)制的模具生產(chǎn)調(diào)度模型研究及應(yīng)用

崔曉光, 蔡鴻明, 步豐林, 鮑升偉

(上海交通大學(xué) 軟件學(xué)院, 上海 200240)

基于準(zhǔn)時(shí)制的模具生產(chǎn)調(diào)度模型研究及應(yīng)用

崔曉光, 蔡鴻明, 步豐林, 鮑升偉

(上海交通大學(xué) 軟件學(xué)院, 上海 200240)

模具生產(chǎn)過(guò)程具有離散化定制的特點(diǎn), 使得在質(zhì)量和產(chǎn)量約束下的準(zhǔn)時(shí)交貨較為困難. 結(jié)合準(zhǔn)時(shí)制與動(dòng)態(tài)規(guī)劃設(shè)計(jì)了一種多級(jí)調(diào)度算法及相關(guān)系統(tǒng), 將調(diào)度問(wèn)題從車間排產(chǎn)擴(kuò)展到整個(gè)產(chǎn)品生產(chǎn)流程, 并從信息建模出發(fā)建立了各模型的關(guān)聯(lián)關(guān)系, 以便更完全地分配企業(yè)生產(chǎn)資源, 均衡開展生產(chǎn), 從而縮短訂單的生產(chǎn)周期. 根據(jù)試驗(yàn)及初步應(yīng)用驗(yàn)證, 系統(tǒng)可以有效解決企業(yè)的離散化定制產(chǎn)品的調(diào)度問(wèn)題, 縮短訂單的生產(chǎn)周期.

模具; 作業(yè)車間調(diào)度; 準(zhǔn)時(shí)制; 動(dòng)態(tài)規(guī)劃; 智慧制造

輪轂?zāi)＞咧圃焓瞧囍圃斓纳嫌萎a(chǎn)業(yè), 業(yè)內(nèi)企業(yè)普遍面臨車間生產(chǎn)調(diào)度效率低下以及拖期嚴(yán)重的問(wèn)題. 這是由輪轂?zāi)＞咧圃斓奶攸c(diǎn)決定的: 一是生產(chǎn)離散化, 模具是用來(lái)成型批量產(chǎn)品的工具, 以定制為主, 由多個(gè)零部件裝配組成, 零件加工工藝的差異也非常大; 二是質(zhì)量要求高, 模具對(duì)于原料、結(jié)構(gòu)設(shè)計(jì)、加工精度等都有很高要求; 三是時(shí)間要求緊, 訂單的延誤會(huì)對(duì)客戶造成很大損失. 車間調(diào)度一方面需要保證交期, 另一方面為了保證質(zhì)量, 要盡可能地避免趕工. 因此, 在諸多目標(biāo)和約束下, 實(shí)現(xiàn)高效調(diào)度很困難, 企業(yè)產(chǎn)量和質(zhì)量受到限制, 往往影響企業(yè)的快速發(fā)展和能級(jí)提升.

目前在資源約束下調(diào)度的研究模型是作業(yè)車間調(diào)度問(wèn)題(job-shop scheduling problem, JSSP), 相關(guān)算法可分為全局算法和動(dòng)態(tài)規(guī)劃算法. 全局算法主要有遺傳算法、蟻群優(yōu)化算法(ant colony optimization, ACO)、神經(jīng)網(wǎng)絡(luò)等. 遺傳算法求解柔性JSSP的結(jié)果[1]比較好, 可以將設(shè)備故障率納入到問(wèn)題模型中[2]. 蟻群算法能夠很好地尋求復(fù)雜問(wèn)題的較優(yōu)解, 可實(shí)現(xiàn)自我學(xué)習(xí)[3]; 也可從設(shè)備負(fù)載均衡角度解決調(diào)度問(wèn)題[4], 平衡資源利用, 最大限度地挖掘產(chǎn)能. 對(duì)于時(shí)間要求比較嚴(yán)格的無(wú)等待流水車間調(diào)度問(wèn)題, 蟻群算法也能給出非常好的結(jié)果[5]. 神經(jīng)網(wǎng)絡(luò)一般用于求解復(fù)雜的混合問(wèn)題, 如將JSSP與增量資金方法糅合, 作為軟件項(xiàng)目的研究模型[6]. 但目前神經(jīng)網(wǎng)絡(luò)算法對(duì)設(shè)備要求高, 在大多企業(yè)中無(wú)法應(yīng)用. 動(dòng)態(tài)規(guī)劃方法是一種求解最優(yōu)化問(wèn)題的方法, 相比全局算法更容易實(shí)現(xiàn), 也能夠保證結(jié)果符合實(shí)際需求. 準(zhǔn)時(shí)制(just in time, JIT)思想也被用于JSSP的解決[7]. 準(zhǔn)時(shí)制是一種生產(chǎn)方式, 又被稱為“零庫(kù)存”, 其基本思想是盡可能后延生產(chǎn), 保證在交貨時(shí)完工, 避免貨物堆積. 將其用在車間調(diào)度上, 可從理論上最大化資源利用, 且計(jì)算速度更快、結(jié)果更加穩(wěn)定[8]. JIT一般與其他方法相結(jié)合來(lái)求解JSSP[9 - 10].

以上算法研究在自動(dòng)化程度高的條件下較為有效, 但在模具這種具有高度定制化的離散化過(guò)程卻很難保證時(shí)間進(jìn)度要求. 因此, 本文從準(zhǔn)時(shí)制算法出發(fā), 將準(zhǔn)時(shí)制與動(dòng)態(tài)規(guī)劃結(jié)合, 給出了一種生產(chǎn)調(diào)度算法, 能夠很好地分配企業(yè)生產(chǎn)資源, 縮短訂單的生產(chǎn)周期, 實(shí)現(xiàn)了相關(guān)調(diào)度系統(tǒng)并開展應(yīng)用.

1 企業(yè)生產(chǎn)過(guò)程的信息建模

模具的生產(chǎn)過(guò)程從接單開始到交貨結(jié)束. 接單有兩種模式: 客戶提供圖紙和企業(yè)負(fù)責(zé)設(shè)計(jì)圖紙. 接單后的生產(chǎn)過(guò)程可以分為設(shè)計(jì)、采購(gòu)、加工3個(gè)階段. 設(shè)計(jì)階段主要是圖紙?jiān)O(shè)計(jì). 一般模具要求完成3份圖紙: 備料圖紙、設(shè)計(jì)圖紙、3D分模. 備料圖紙規(guī)定模具原料規(guī)格和數(shù)目; 設(shè)計(jì)圖紙主要是制定模具物料清單(bill of material, BOM), 給定各部分的加工要求, 工藝員據(jù)此為零件編制工藝路線; 3D分模主要為裝配提供參考. 采購(gòu)環(huán)節(jié)在備料圖紙完成后開始. 圖紙完成并且采購(gòu)后, 產(chǎn)品就可以進(jìn)入加工環(huán)節(jié). 調(diào)度員將模具加入工作序列中, 安排車間工人加工. 所有零件完成后, 裝配工進(jìn)行裝配、封箱, 完成最終交貨. 信息建模的難點(diǎn)在于構(gòu)建的模型對(duì)調(diào)度算法的支持. 根據(jù)產(chǎn)品特性和調(diào)度特點(diǎn), 本文采用三級(jí)展開方式. 將訂單映射到單個(gè)模具, 再根據(jù)BOM列出模具的零件列表, 最后為每個(gè)零件指定工藝路線. 通過(guò)工藝路線將產(chǎn)品與生產(chǎn)資源聯(lián)系在一起. 圖1給出了主要信息模型類圖. 其中符號(hào)“1..*”“1”表示映射關(guān)系中的實(shí)體數(shù)目. 訂單與客戶之間的映射關(guān)系: 一個(gè)客戶可以擁有多個(gè)訂單, 一個(gè)訂單只屬于一個(gè)客戶. 模具與零件之間的關(guān)系: 零件是模具的一部分, 多個(gè)零件聚合構(gòu)成一個(gè)模具.

圖1 信息模型圖Fig.1 Diagram of information model

2 基于準(zhǔn)時(shí)制的作業(yè)車間調(diào)度算法

2.1 問(wèn)題描述

(1)

s. t.

(2)

(3)

(4)

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

圖2是算法的流程圖. 基本思路: 在現(xiàn)有的設(shè)備資源下, 計(jì)算出一個(gè)零件的完成時(shí)間, 如果明顯早于交貨日期, 就不加入生產(chǎn)隊(duì)列. 最終實(shí)現(xiàn)是將JIT與動(dòng)態(tài)規(guī)劃相結(jié)合, 具體方法是試排找到最緊迫的零件, 將最后一道工藝的完成時(shí)間設(shè)為交貨日期, 做前序遍歷, 將工藝安排合適的設(shè)備. 排產(chǎn)結(jié)果盡可能使每一個(gè)零件恰好在交貨期時(shí)完成.

圖2 算法流程圖Fig.2 Flow diagram of algorithm

2.3 算法擴(kuò)展

算法實(shí)現(xiàn)中需要考慮更多因素, 比較典型的有以下兩個(gè)因素.

一是上游環(huán)節(jié)管控. 由于在圖紙完成后, 不同部門人員之間溝通有延遲, 這可能會(huì)導(dǎo)致后續(xù)工作無(wú)法開展, 嚴(yán)重的會(huì)導(dǎo)致訂單的遺漏. 這個(gè)問(wèn)題通過(guò)將相關(guān)系統(tǒng)接入本系統(tǒng)解決. 系統(tǒng)自動(dòng)獲取狀態(tài)更新, 并將信息展示給相關(guān)人員. 同時(shí)記錄這個(gè)過(guò)程中的所有時(shí)間點(diǎn)及相關(guān)操作, 方便追責(zé).

上述問(wèn)題導(dǎo)致在排產(chǎn)時(shí), 某些工藝的開始時(shí)間增加了一個(gè)約束條件, 算法需要增加一個(gè)分支處理這種特殊情況.

圖3 拓展算法流程圖Fig.3 Flow diagram of expansion algorithm

2.4 試驗(yàn)及分析

試驗(yàn)數(shù)據(jù)為企業(yè)的生產(chǎn)數(shù)據(jù). 首先介紹一下數(shù)據(jù)的處理方式, 生產(chǎn)環(huán)境下不斷有訂單加入, 而排產(chǎn)算法是在某一個(gè)時(shí)間點(diǎn)上做出的預(yù)測(cè), 是無(wú)法考慮追加訂單這種情況的, 因此, 試驗(yàn)數(shù)據(jù)與生產(chǎn)數(shù)據(jù)的數(shù)據(jù)環(huán)境無(wú)法完全一致, 只能尋求一個(gè)等價(jià)時(shí)間點(diǎn). 具體做法: 將生產(chǎn)狀態(tài)恢復(fù)到特定的某一天, 在這天之后接到的訂單需要剔除, 之前交付的訂單需要剔除, 這天之后的所有生產(chǎn)狀態(tài)需要復(fù)位, 這就得到了算法的輸入狀態(tài), 在此基礎(chǔ)上計(jì)算得到訂單交期的預(yù)測(cè)值, 與實(shí)際值有一定的可比性.

試驗(yàn)數(shù)據(jù)來(lái)自企業(yè)生產(chǎn)數(shù)據(jù), 選取2015-10-21—2016-01-29接到的訂單. 按照上述處理方式, 根據(jù)下單日期和實(shí)際交付日期的分布情況, 將恢復(fù)時(shí)間定為2016年1月14號(hào).1月14號(hào)之前交付的訂單、之后接到的訂單均剔除, 1月14號(hào)及之后的所有生產(chǎn)狀態(tài)清零. 經(jīng)篩選共有166個(gè)訂單, 這批訂單經(jīng)BOM展開后有2 054個(gè)非標(biāo)件, 包含13 748道工藝. 其中132個(gè)訂單在1月29號(hào)前完成交付, 將這批訂單作為對(duì)比數(shù)據(jù), 將實(shí)際生產(chǎn)周期與排產(chǎn)計(jì)算結(jié)果進(jìn)行對(duì)比. 將數(shù)據(jù)恢復(fù)到1月14號(hào)之后, 這批訂單的未完成工藝有8 419道, 分屬于1 545個(gè)零件, 總計(jì)加工時(shí)長(zhǎng)為35 336.8 h.

試驗(yàn)結(jié)果如表1所示. 由表1可知, 相比企業(yè)之前的調(diào)度方式, 試驗(yàn)中訂單延誤率降低了13.6%, 平均延誤天數(shù)降低了37.0%, 按期交貨率提高了21.2%, 平均生產(chǎn)周期降低了21.6%. 訂單交貨嚴(yán)重不均衡也得到了改善.

表1 實(shí)際生產(chǎn)結(jié)果與算法排產(chǎn)結(jié)果比較
Table 1 Comparison of production data and results of the algorithm

指標(biāo)實(shí)際數(shù)據(jù)排產(chǎn)計(jì)算結(jié)果總加工天數(shù)/d27642168延誤訂單數(shù)/個(gè)8069平均延誤天數(shù)/d9．25．8如期完成訂單/個(gè)5263平均提前天數(shù)/d14．16．4

3 調(diào)度系統(tǒng)實(shí)現(xiàn)及驗(yàn)證

3.1 系統(tǒng)實(shí)現(xiàn)及展現(xiàn)

根據(jù)算法實(shí)現(xiàn)了相關(guān)的調(diào)度系統(tǒng), 系統(tǒng)采用瀏覽器和服務(wù)器架構(gòu), 前端頁(yè)面與調(diào)度相關(guān)頁(yè)面分組包括訂單管理、工藝編制、智能排產(chǎn)、生產(chǎn)管理、加工任務(wù). 圖4和5分別為調(diào)度頁(yè)面和生產(chǎn)進(jìn)度界面. 通過(guò)生產(chǎn)狀態(tài)反饋等信息支持排產(chǎn)系統(tǒng)的執(zhí)行監(jiān)控和動(dòng)態(tài)調(diào)整, 并開發(fā)實(shí)現(xiàn)手工設(shè)置、仿真優(yōu)化預(yù)測(cè)、可視化展示、警示推送等功能模塊, 構(gòu)成一個(gè)可以實(shí)現(xiàn)具有動(dòng)態(tài)適應(yīng)能力的多策略排產(chǎn)系統(tǒng). 隨著生產(chǎn)管理的粒度細(xì)化, 逐步實(shí)現(xiàn)以班次排產(chǎn)為主, 并兼顧可變時(shí)間間隔, 以及零件動(dòng)態(tài)批次的生產(chǎn)模式.

圖4 調(diào)度頁(yè)面Fig.4 Schedule interface

圖5 生產(chǎn)進(jìn)度界面Fig.5 Progress report interface

3.2 對(duì)比討論

調(diào)度系統(tǒng)屬于制造企業(yè)生產(chǎn)執(zhí)行系統(tǒng)(manu-facturing execution system, MES), 核心是調(diào)度算法, 企業(yè)沒(méi)有通用系統(tǒng)可選, 只能通過(guò)定制開發(fā)方式獲得. 企業(yè)缺乏可選的成熟系統(tǒng). 這是因?yàn)檎{(diào)度過(guò)程與企業(yè)業(yè)務(wù)關(guān)聯(lián)度非常高, 不同企業(yè)業(yè)務(wù)差別非常大, 系統(tǒng)往往是針對(duì)特定企業(yè)定制開發(fā). 本文主要與同類文獻(xiàn)做對(duì)比, 結(jié)果如表2所示. 本文實(shí)現(xiàn)的系統(tǒng)是為輪轂?zāi)＞咂髽I(yè)定制開發(fā), 針對(duì)模具生產(chǎn)過(guò)程做了優(yōu)化, 貼合企業(yè)的生產(chǎn)實(shí)際, 實(shí)際使用效果比較好.

表2 本文系統(tǒng)與相關(guān)系統(tǒng)比較
Table 2 This article system compared with related systems

本文系統(tǒng)文獻(xiàn)[9]文獻(xiàn)[11]文獻(xiàn)[12]設(shè)備規(guī)模142[2，10][5，10]任務(wù)規(guī)模8419[10，20][50，500]算法JIT，動(dòng)態(tài)規(guī)劃JIT，動(dòng)態(tài)規(guī)劃組合優(yōu)化標(biāo)記優(yōu)先級(jí)，順排

(續(xù) 表)

4 結(jié) 語(yǔ)

調(diào)度算法只是車間調(diào)度問(wèn)題解決方案的一部分, 要徹底解決這個(gè)問(wèn)題, 需要多個(gè)系統(tǒng)協(xié)同, 對(duì)整個(gè)生產(chǎn)流程施加影響. 本文設(shè)計(jì)實(shí)現(xiàn)了以基于準(zhǔn)時(shí)制的調(diào)度算法為核心的車間調(diào)度系統(tǒng), 通過(guò)與企業(yè)現(xiàn)有系統(tǒng)的對(duì)接, 對(duì)整個(gè)生產(chǎn)流程進(jìn)行監(jiān)控. 創(chuàng)新之處在于考慮到上游環(huán)節(jié)的問(wèn)題, 消除部分調(diào)度問(wèn)題產(chǎn)生的源頭, 降低了延誤的發(fā)生頻率, 同時(shí)縮短了企業(yè)的生產(chǎn)周期.

下一步的工作將包括幫助企業(yè)進(jìn)行接單前的產(chǎn)能分析, 避免超出產(chǎn)能的接單; 根據(jù)調(diào)度情況給出企業(yè)實(shí)際產(chǎn)能利用分析, 對(duì)資源重新規(guī)劃分配; 將系統(tǒng)進(jìn)一步擴(kuò)展, 為未來(lái)企業(yè)實(shí)行智能制造提供一個(gè)系統(tǒng)基礎(chǔ).

[1] FAN S, WANG J. Scheduling for the flexible job-shop problem based on genetic algorithm (GA) [J]. Advanced Materials Research, 2012, 457/458(1): 616-619.

[2] AL-HINAI N, ELMEKKAWY T. Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm [J]. International Journal of Production Economics, 2011, 132(2): 279-291.

[3] XING L, CHEN Y, WANG P, et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems [J]. Applied Soft Computing, 2010, 10(3): 888-896.

[4] CHAUKWALE R, KAMATH R. A modified ant colony optimization algorithm with load balancing for job shop scheduling[C]// International Conference on Advanced Computing Technologies. 2013: 1-5.

[5] 潘全科, 趙保華, 屈玉貴, 等. 一類解決無(wú)等待流水車間調(diào)度問(wèn)題的蟻群算法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2007, 13(3): 1801-1804.

[6] IPSILANDIS P, TSELIOS D, GEROGIANNIS V. Consolida-tion of the IFM with the JSSP through neural networks as model for software projects[C]// International Conference on Artificial Intelligence, Modelling & Simulation. 2014: 33-38.

[7] 徐兵, 陶麗華, 胡月梅. 基于JIT的多車間混流裝配計(jì)劃排序問(wèn)題 [J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2015 (1): 153-156.

[8] 宋娟. 基于JIT的面向JSSP的一種啟發(fā)式快速搜索算法[J]. 制造業(yè)自動(dòng)化, 2010, 32(11): 106-109.

[9] WANG S, LI Y. Variable neighborhood search and mathema-tical programming for just-in-time job-shop scheduling problem [J]. Mathematical Problems in Engineering, 2014, 71(3): 741-764.

[10] 芮執(zhí)元，馮亞崗，劉軍，等. 一種求解柔性多目標(biāo)JIT作業(yè)車間調(diào)度優(yōu)化問(wèn)題的方法[J]. 機(jī)械與電子， 2009(6)： 10-14.

[11] KOUIDER A, BOUZOUIA B. Multi-agent job shop scheduling system based on co-operative approach of idle time minimization [J]. International Journal of Production Research, 2012, 50(2): 409-424.

[12] 肖波, 葉文華. 工裝MES生產(chǎn)調(diào)度和進(jìn)度跟蹤模塊的研究與開發(fā)[J]. 機(jī)械制造與研究, 2009, 38(2): 42-46.

文章編號(hào)： 1671-0444 (2016)04-0461-05

Research and Implementation of Mold Production Scheduling Model Based on JIT

CUIXiao-guang,CAIHong-ming,BUFeng-lin,BAOSheng-wei

(School of Software, Shanghai Jiao Tong University, Shanghai 200240, China)

The mold production process has the characteristic of the discrete customization, which makes it difficult to deliver the goods on time due to the restriction of quality and production. Combining JIT (just in time) and dynamic programming, a multilevel scheduling algorithm and the related system are designed. The scheduling algorithm extends the scheduling problem from the shop floor to the entire production process, and establishes the relationship of the model from information modeling, which makes the allocation of production resources more fully, and balances development of production, so as to shorten the production cycle of orders. According to the experimental study and preliminary application verification, the system can effectively solve the enterprise discretization constant product scheduling problem, and shorten the production cycle of orders.

mold; job-shop scheduling; just in time; dynamic programming; intelligent manufacturing

1671-0444 (2016)04-0455-06

2016-04-20

國(guó)家自然科學(xué)基金資助項(xiàng)目(71171132, 61373030)；上海市自然科學(xué)基金資助項(xiàng)目(13ZR1419800)

崔曉光(1989—)，男，河南鄭州人，碩士研究生，研究方向?yàn)樾畔⒖梢暬⒅悄苤圃?E-mail：cxgenjoy@163.com 蔡鴻明(聯(lián)系人)，男，副教授，E-mail：hmcai@sjtu.edu.cn

TB 497; TP 311

A