考慮刀具剩余壽命的工件流－刀具流綜合調(diào)度研究

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

考慮刀具剩余壽命的工件流－刀具流綜合調(diào)度研究

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

（三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院，湖北 宜昌 443000）

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

FMS；綜合調(diào)度；和聲搜索；遺傳算法

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

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

1 考慮刀具剩余壽命的刀具綜合調(diào)度模型

1.1 刀具剩余壽命約束下刀具綜合調(diào)度問題描述

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

首先給出如下基本假設(shè)：

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

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

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

（4）當(dāng)前每把刀具的剩余壽命已知。

1.2 變量符號(hào)定義

：工件編號(hào)；

：工序編號(hào)；

：刀具編號(hào)；

C：機(jī)床的刀具庫容量；

max：系統(tǒng)生產(chǎn)時(shí)間；

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

P：工件的工序在機(jī)床上使用刀具的加工時(shí)間；

P：機(jī)床等待刀具的時(shí)間；

1.3 考慮刀具剩余壽命的刀具綜合調(diào)度模型

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

表1 工序－刀具表

注：“X”表示對(duì)應(yīng)工序不可用該刀具進(jìn)行加工。

圖1 問題描述圖

基于上述假設(shè)，建立考慮刀具剩余壽命的工件流－刀具流綜合調(diào)度問題數(shù)學(xué)模型。即：

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

（1）在加工過程中，一臺(tái)機(jī)器只能裝夾一把刀具，即：

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

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

2 改進(jìn)和聲－遺傳算法設(shè)計(jì)

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

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

圖2 改進(jìn)和聲－遺傳算法流程圖

2.1 機(jī)器編碼

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

2.2 外層適應(yīng)度計(jì)算

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

圖3 移動(dòng)兩道工序變鄰域結(jié)構(gòu)圖

圖4 機(jī)器編碼示意圖

圖5 GS流程圖

2.3 內(nèi)層適應(yīng)度計(jì)算

在解決生產(chǎn)調(diào)度問題的改進(jìn)和聲－遺傳算法中，計(jì)算了每個(gè)可行的刀具調(diào)度染色體的Makespan值，以評(píng)估綜合調(diào)度的優(yōu)缺點(diǎn)，即：

則：

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

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

圖6 刀具編碼示意圖

2.4 外層和聲搜索

2.4.1 新和聲庫的產(chǎn)生

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

圖7 信息保留策略示意圖

2.4.2 更新和聲記憶庫

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

3 實(shí)例驗(yàn)證與結(jié)果分析

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

本實(shí)例中，有5個(gè)工件、6臺(tái)機(jī)器、30把待選刀具，每個(gè)工件包含了多道工序。每把刀具對(duì)應(yīng)不同工序的加工時(shí)間，機(jī)器加工信息如表2所示，刀具加工信息如表3所示。與任務(wù)相關(guān)的刀具需求信息、刀具的剩余壽命及其極限壽命信息如表4所示。

表2 機(jī)器加工信息表

表3 刀具加工信息表

表4 刀具信息表

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

表5 不同方法的總體指標(biāo)

圖8 工件流－刀具流綜合調(diào)度甘特圖

4 結(jié)束語

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

圖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án)大虎，等. 面向能耗的柔性作業(yè)車間動(dòng)態(tài)調(diào)度研究[J]. 系統(tǒng)仿真學(xué)報(bào)，2017，29（9）：2168-2174.

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

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

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

[6]魯宏浩. 基于分布估計(jì)—蟻群混合算法的柔性作業(yè)車間調(diào)度問題研究[D]. 杭州：浙江理工大學(xué)，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]張敏行，熊瑞平，常敏. 基于退火選擇微粒群算法的車間調(diào)度問題研究[J]. 機(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]顏靜，朱伏平，楊婉琳. 基于準(zhǔn)時(shí)交貨的多品種小批量生產(chǎn)調(diào)度系統(tǒng)研究[J]. 機(jī)械，2017，44（4）：10-14，41，68.

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

[12]邊培瑩. PSO算法在FMS 刀具可復(fù)用調(diào)度中的應(yīng)用與仿真[J]. 機(jī)械設(shè)計(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

國家重點(diǎn)研發(fā)計(jì)劃課題（2018YFB1700801）；宜昌市科技局自然科學(xué)研究項(xiàng)目（A20-3-008）

李浩平（1971－），女，廣東臺(tái)山人，碩士，教授，主要研究方向?yàn)橹圃煜到y(tǒng)自動(dòng)化技術(shù)、制造系統(tǒng)智能故障診斷、系統(tǒng)安全分析與評(píng)價(jià)，E-mail：77450205@qq.com。