李浩平，葛曉博，王坤，王艷苗，羅少康，彭巍，孟榮華

考慮刀具剩余壽命的工件流－刀具流綜合調度研究

李浩平，葛曉博，王坤，王艷苗，羅少康，彭巍，孟榮華

（三峽大學 機械與動力學院，湖北 宜昌 443000）

為解決FMS中工件流－刀具流的調度優(yōu)化問題，考慮刀具剩余壽命，以完成時間最短為優(yōu)化目標，建立了工件流－刀具流綜合調度模型，提出了改進和聲－遺傳算法，并對模型進行優(yōu)化求解。設計了MSOS＋TSOS編碼方式和GS初始化方法，從而顯著提高了算法的收斂性能和求解效率。算例結果表明，該模型能有效降低完工時間，并且算法的收斂速度和穩(wěn)定性也得到了明顯提高，大大降低了問題求解的迭代次數。

FMS；綜合調度；和聲搜索；遺傳算法

以往對柔性制造系統(tǒng)（FMS，Flexible Manufacturing System）的研究[1-4]主要集中在工件流的調度，在這些調度優(yōu)化中，多數都不考慮刀具影響因素。且對刀具流的研究[5-8]大多集中于刀具系統(tǒng)管理，很少見與系統(tǒng)實時控制相關的刀具分派優(yōu)化研究[9-10]，但刀具資源優(yōu)化調度使用在許多方面發(fā)揮著舉足輕重的作用，因此有必要研究刀具剩余壽命綜合優(yōu)化調度問題。

在刀具綜合調度方面，張維[11]等考慮了由于刀具爭用引起的拖期懲罰費用以及工時損耗，采用了基于刀具時間沖突的調度算法對模型進行求解。邊培瑩[12]用粒子群算法（PSO）證明了帶PSO的可復用調度策略應用于刀具綜合調度帶來的經濟性。A. Setiawan[13]處理了FMS在生產調度過程中因壽命限制導致刀具無法使用的問題。SetiawanA[14]等研究了無人操作FMS的生產調度問題。

1 考慮刀具剩余壽命的刀具綜合調度模型

1.1 刀具剩余壽命約束下刀具綜合調度問題描述

一臺數控加工中心分配了個工件{1,2,...,J}各工序在臺機器{1,2,..., M}上加工，工藝要求確定了各工序加工順序。每道工序的可選加工刀具和機器由工藝規(guī)程確定，至少有一把/臺待選刀具機器可對其進行加工，其加工時間隨所選刀具和機器的不同而不同，其中共有把待選刀具{1,2,..., T}可供選擇，每把刀具可用壽命有限，加工不同工序可能存在多把刀具，對每把刀具壽命的損耗也不同。

首先給出如下基本假設：

（1）工件的加工工藝路線是固定的；

（2）每個工件一旦開始加工不能中斷；

（3）在零時刻所有工件都可以被加工；

（4）當前每把刀具的剩余壽命已知。

1.2 變量符號定義

：工件編號；

：工序編號；

：刀具編號；

C：機床的刀具庫容量；

max：系統(tǒng)生產時間；

T：工件的工序在機床上使用刀具加工后其剩余壽命；

P：工件的工序在機床上使用刀具的加工時間；

P：機床等待刀具的時間；

1.3 考慮刀具剩余壽命的刀具綜合調度模型

本文刀具調度是在考慮刀具剩余壽命情況下，建立工件流－刀具流綜合調度數學模型。表1和圖1描述了數控加工中心2工件5機器6刀具的綜合調度問題。

表1 工序－刀具表

注：“X”表示對應工序不可用該刀具進行加工。

圖1 問題描述圖

基于上述假設，建立考慮刀具剩余壽命的工件流－刀具流綜合調度問題數學模型。即：

此外，模型服從約束如下：

（1）在加工過程中，一臺機器只能裝夾一把刀具，即：

（2）在滿足b＝1的前提下，工件的工序在機床上使用刀具的加工時間應該小于刀具的剩余壽命，即：

（3）在滿足b＝1的前提下，機床上所有選用的刀具總數量應小于機床的刀具庫存量，即：

2 改進和聲－遺傳算法設計

流程如圖2所示，外層優(yōu)化工序加工順序，使系統(tǒng)加工時間最短。在工件流－刀具流綜合調度中，系統(tǒng)加工時間不僅受到機床選擇的影響，而且受到刀具分配的影響。為此，引入了可行的刀具內層優(yōu)化分配，其優(yōu)化目標仍是系統(tǒng)加工時間最短。

傳統(tǒng)的遺傳算法由于收斂速度慢，常常陷入局部最優(yōu)解。為了實現刀具綜合調度問題的解決方案，采用變鄰域搜索算法，提高了算法的收斂速度，跳出了局部最優(yōu)解。如圖3所示。

圖2 改進和聲－遺傳算法流程圖

2.1 機器編碼

針對刀具綜合調度問題，結合分段編碼的特點，如性能和操作簡便，對以前的編碼方法進行改進，設計了一種MSOS編碼，包括機器選擇（Machines Selection，MS）和工序排序（Operations Sequencing，OS），其編碼方式如圖4所示。

2.2 外層適應度計算

針對柔性作業(yè)車間調度問題FJSP（Flexible Job Shop Scheduling Problem）特點，提出一種全局選擇（Global Selection，GS）的機器選擇方法，如圖5所示。GS主要目的是使各臺加工機器的工作負載盡量均衡化，充分提高機器的利用率。

圖3 移動兩道工序變鄰域結構圖

圖4 機器編碼示意圖

圖5 GS流程圖

2.3 內層適應度計算

在解決生產調度問題的改進和聲－遺傳算法中，計算了每個可行的刀具調度染色體的Makespan值，以評估綜合調度的優(yōu)缺點，即：

則：

式中：max為系統(tǒng)Makespan的值；t為第臺機床加工所有工件所需要的時間；t為當前工步的開始時間；t為該機器上一個工序完工時間；t為前面一道工序的完成時間；t為當前工序所使用的刀具的釋放時間。

與機器編碼類似，刀具編碼由兩部分組成：刀具選擇（Tool Selection，TS）和工序排序，如圖6所示。

圖6 刀具編碼示意圖

2.4 外層和聲搜索

2.4.1 新和聲庫的產生

由于原始的新和聲是隨機生成的，因此不可能在短時間內獲得更好的解決方案。本文采用遺傳算法的精英保留策略，根據適應度確定新的和聲信息的組成。同時，將所有初始解的傳統(tǒng)隨機選擇信息更改為來自種群中某些較好個體的選擇信息。如圖7所示。

圖7 信息保留策略示意圖

2.4.2 更新和聲記憶庫

在和聲庫的更新操作中，改變鄰域后對新和聲進行解碼，如果新和聲優(yōu)于和聲庫的最差解，則用新和聲代替最差和聲，否則算法進入下一循環(huán)操作。

3 實例驗證與結果分析

建立工件流－刀具流調度模型，并采用改進和聲－遺傳算法求解得到工件流－刀具流的優(yōu)化配置方案，再設計雙重遺傳算法與本算法進行比較。

本實例中，有5個工件、6臺機器、30把待選刀具，每個工件包含了多道工序。每把刀具對應不同工序的加工時間，機器加工信息如表2所示，刀具加工信息如表3所示。與任務相關的刀具需求信息、刀具的剩余壽命及其極限壽命信息如表4所示。

表2 機器加工信息表

表3 刀具加工信息表

表4 刀具信息表

由表5可看出，與傳統(tǒng)的雙重遺傳算法相比，采用改進和聲－遺傳算法選擇機床及刀具加工工序，可使系統(tǒng)總的完工時間減少28.2%，等機器時間下降44.4%，等刀時間下降85.7%，換刀次數不變。由此可知，本文提出的考慮刀具剩余壽命工件流－刀具流綜合調度數學模型和求解算法實現了綜合目標最優(yōu)。圖8和圖9詳細給出了優(yōu)化解對應的工件加工順序及刀具分派順序。

表5 不同方法的總體指標

圖8 工件流－刀具流綜合調度甘特圖

4 結束語

對于工件流－刀具流綜合調度加工任務，機床選擇、工序排序和刀具分派是影響總生產時間的關鍵環(huán)節(jié)，只有集成調度工件流、刀具流，才有可能得到全局最優(yōu)解。為此，本文設計了整數編碼方法和全局選擇初始化方法，建立工件流－刀具流綜合調度模型，利用改進和聲－遺傳算法對該模型求解，最后對加工實例進行分析，并設計雙重遺傳算法與本算法進行比較。結果證明，本模型取得了較好結果。

圖9 系統(tǒng)刀具分派圖

[1]Siemiatkowski M，Przybylski W. Simulation studies of process flow with in-line part inspection in machining cells[J]. Journal of Materials Processing Technology，2006，171（1）：27-34.

[2]陳超，王艷，嚴大虎，等. 面向能耗的柔性作業(yè)車間動態(tài)調度研究[J]. 系統(tǒng)仿真學報，2017，29（9）：2168-2174.

[3]朱傳軍，邱文，張超勇，等. 多目標柔性作業(yè)車間穩(wěn)健性動態(tài)調度研究[J]. 中國機械工程，2017，28（2）：173-182.

[4]龍?zhí)?，王俊? 基于調度規(guī)則和免疫算法的作業(yè)車間多目標調度[J]. 信息與控制，2016，45（3）：278-286.

[5]石小秋. 柔性作業(yè)車間的動態(tài)生產調度問題研究[D]. 綿陽：西南科技大學，2015.

[6]魯宏浩. 基于分布估計—蟻群混合算法的柔性作業(yè)車間調度問題研究[D]. 杭州：浙江理工大學，2019.

[7]L M，Sodhi M S，Lamond B F. Tool planning for a lights-out machining system[J]. Journal of Manufacturing Systems，2007，26（3-4）：161-166.

[8]張敏行，熊瑞平，常敏. 基于退火選擇微粒群算法的車間調度問題研究[J]. 機械，2016，43（5）：59-62，73.

[9]Matta A，Tolio T，Tontini F. Tool management in flexible manufacturing systems with network part program[J]. International Journal of Production Research，2004，42（17）：3707-3730.

[10]顏靜，朱伏平，楊婉琳. 基于準時交貨的多品種小批量生產調度系統(tǒng)研究[J]. 機械，2017，44（4）：10-14，41，68.

[11]張維，楊洋洋，王亮. 有限資源約束下的刀具綜合調度方法研究[J]. 工具技術，2017，51（11）：46-51.

[12]邊培瑩. PSO算法在FMS 刀具可復用調度中的應用與仿真[J]. 機械設計與制造，2012（3）：76-78.

[13] Setiawan A，Wangsaputra R，Martawirya Y Y，et al. An FMS Dynamic Production Scheduling Algorithm Considering Cutting Tool Failure and Cutting Tool Life[J]. IOP Conference Series：Materials Science and Engineering，2016，114（1）：012052.

[14]Setiawan A，Wangsaputra R，Martawirya Y Y，et al. A production scheduling model considering cutting tools for an FMS to minimize makespan[C]. Proceedings of the 16th Asia Pacific Industrial Engineering & ManagementSystemsConference，APIEMS-2015，Ho-Chi-Minh City.

Study on Integrated Scheduling of Part and Tool Flows Considering Tool’s Residual Life

LI Haoping，GE Xiaobo，WANG Kun，WANG Yanmiao，LUO Shaokang，PENG Wei，MENG Ronghua

( College of Mechanical and Power Engineering,Three Gorges University, Yichang 443000, China)

To solve the problem of scheduling optimization of part and tool flow in the FMS, a integrated scheduling mathematical model of part and tool flow is established based on the tool’s residual life while taking the shortest completion time as the optimization goal, and an improved harmonic genetic algorithm is proposed and the model is optimized. The MSOS+TSOS encoding method and GS initialization method are designed, which can significantly improve the convergence performance and solving efficiency of the algorithm. The results show that the model can effectively reduce the completion time, and improve the convergence speed and stability of the algorithm, thus greatly reducing the iteration times.

FMS；integrated scheduling；harmony search；genetic algorithm

TG714

A

10.3969/j.issn.1006-0316.2021.03.008

1006－0316 (2021) 03－0046－07

2020－10－14

國家重點研發(fā)計劃課題（2018YFB1700801）；宜昌市科技局自然科學研究項目（A20-3-008）

李浩平（1971－），女，廣東臺山人，碩士，教授，主要研究方向為制造系統(tǒng)自動化技術、制造系統(tǒng)智能故障診斷、系統(tǒng)安全分析與評價，E-mail：77450205@qq.com。