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

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

基于準時制的模具生產(chǎn)調(diào)度模型研究及應用

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

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

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

模具; 作業(yè)車間調(diào)度; 準時制; 動態(tài)規(guī)劃; 智慧制造

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

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

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

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

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

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

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

2.1 問題描述

(1)

s. t.

(2)

(3)

(4)

2.2 算法設計

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

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

2.3 算法擴展

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

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

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

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

2.4 試驗及分析

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

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

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

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

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

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

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

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

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

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

3.2 對比討論

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

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

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

(續(xù) 表)

4 結 語

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

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

[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] 潘全科, 趙保華, 屈玉貴, 等. 一類解決無等待流水車間調(diào)度問題的蟻群算法[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]. 組合機床與自動化加工技術, 2015 (1): 153-156.

[8] 宋娟. 基于JIT的面向JSSP的一種啟發(fā)式快速搜索算法[J]. 制造業(yè)自動化, 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í)元，馮亞崗，劉軍，等. 一種求解柔性多目標JIT作業(yè)車間調(diào)度優(yōu)化問題的方法[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)度和進度跟蹤模塊的研究與開發(fā)[J]. 機械制造與研究, 2009, 38(2): 42-46.

文章編號： 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

國家自然科學基金資助項目(71171132, 61373030)；上海市自然科學基金資助項目(13ZR1419800)

崔曉光(1989—)，男，河南鄭州人，碩士研究生，研究方向為信息可視化、智能制造.E-mail：cxgenjoy@163.com 蔡鴻明(聯(lián)系人)，男，副教授，E-mail：hmcai@sjtu.edu.cn

TB 497; TP 311

A