基于準時制的模具生產調度模型研究及應用

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

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

基于準時制的模具生產調度模型研究及應用

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

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

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

模具; 作業車間調度; 準時制; 動態規劃; 智慧制造

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

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

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

1 企業生產過程的信息建模

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

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

2 基于準時制的作業車間調度算法

2.1 問題描述

(1)

s. t.

(2)

(3)

(4)

2.2 算法設計

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

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

2.3 算法擴展

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

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

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

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

2.4 試驗及分析

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

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

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

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

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

3 調度系統實現及驗證

3.1 系統實現及展現

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

圖4 調度頁面Fig.4 Schedule interface

圖5 生產進度界面Fig.5 Progress report interface

3.2 對比討論

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

表2 本文系統與相關系統比較
Table 2 This article system compared with related systems

本文系統文獻[9]文獻[11]文獻[12]設備規模142[2，10][5，10]任務規模8419[10，20][50，500]算法JIT，動態規劃JIT，動態規劃組合優化標記優先級，順排

(續 表)

4 結 語

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

下一步的工作將包括幫助企業進行接單前的產能分析, 避免超出產能的接單; 根據調度情況給出企業實際產能利用分析, 對資源重新規劃分配; 將系統進一步擴展, 為未來企業實行智能制造提供一個系統基礎.

[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] 潘全科, 趙保華, 屈玉貴, 等. 一類解決無等待流水車間調度問題的蟻群算法[J]. 計算機集成制造系統, 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的一種啟發式快速搜索算法[J]. 制造業自動化, 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] 芮執元，馮亞崗，劉軍，等. 一種求解柔性多目標JIT作業車間調度優化問題的方法[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生產調度和進度跟蹤模塊的研究與開發[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 蔡鴻明(聯系人)，男，副教授，E-mail：hmcai@sjtu.edu.cn

TB 497; TP 311

A