文章主要討論了柔性制造系統(tǒng)的刀具需求規(guī)劃問題，首先利用已有文獻所報道的結(jié)論簡化了實際問題麻惶，給出了求解在制時間和刀具等待時間的遞歸算法馍刮，同時給出了一個求解刀具需求規(guī)劃的啟發(fā)式算法。為了觀察該算法的性能窃蹋，我們通過隨機數(shù)據(jù)產(chǎn)生并構(gòu)成了60個刀具需求規(guī)劃問題卡啰，并采用兩種不同的刀具調(diào)度策略進行了數(shù)據(jù)測試。和已有算法進行比較后警没，我們發(fā)現(xiàn)無論采取什么工件調(diào)度策略匕冠，文章介紹的算法都具有較優(yōu)的解

1　引言

按照工件的處理方式胚僧，柔性制造系統(tǒng)(FMS)可分為兩類：工件移動系統(tǒng)和刀具移動系統(tǒng)。在工件移動系統(tǒng)中逾族，一旦工件的調(diào)度確定下來镇轿，加工中心所配置的刀具就不會再改變，除非刀具斷裂或磨損;而在刀具移動系統(tǒng)中淑助，每個工件在一個加工中心執(zhí)行完所有的操作后才能卸下來斟彻，所以必須在該工件加工開始之前，準備好所有必須的刀具光稽。刀具移動的系統(tǒng)比工件移動的系統(tǒng)具有以下優(yōu)勢而得到廣泛使用粟辛，①刀具較小，而工件較重也拳，實現(xiàn)刀具移動的自動化系統(tǒng)成本較低;②容易實現(xiàn)刀具的自動安裝和定位芙掖。在刀具移動系統(tǒng)中，每把刀具都是作為整體在機床之間頻繁借用的绝迁，這種借用會產(chǎn)生刀具延遲伊镐，進而對工件的加工產(chǎn)生時間上的拖延，這種拖延由兩部分組成：刀具運輸時間和刀具等待時間鹃栽，所謂刀具運輸時間就是把刀具從一個機床運送到另一個機床的時間躏率，所謂刀具等待時間就是等待正在使用被借刀具的機床加工完當前工件的時間。一般刀具運送時間遠小于工件的加工時間民鼓，且對工件的在制時間沒有明顯的影響薇芝，所以減小刀具等待時間是解決刀具延遲的主要途徑。

刀具是制造過程中的一個重要資源丰嘉，占到各種制造成本的25%～30%夯到。在制造車間，不合理的刀具配置常常使16%的生產(chǎn)調(diào)度無法進行饮亏，40～80%的時間都用來尋找或補充刀具耍贾。由于刀具引發(fā)的問題嚴重影響了車間的生產(chǎn)效率，所以加強刀具管理已越來越得到人們的重視路幸。

所謂刀具需求規(guī)劃荐开，就是如何配置柔性制造系統(tǒng)所需刀具規(guī)格的數(shù)量，使得刀具資源對生產(chǎn)過程的影響盡可能小劝赔。本文以一個刀具移動的柔性制造系統(tǒng)為背景誓焦，研究了在允許的刀具購買資金預(yù)算下胆敞，如何規(guī)劃給定任務(wù)的刀具需求并盡量減小任務(wù)的在制時間诸痢。

2　問題描述

本文研究的刀具移動柔性制造系統(tǒng)包含若干相同的箱體類數(shù)控機床和一個中央刀具庫。每臺數(shù)控機床都有一個容量有限的機床刀具庫酝梧，而中央刀具庫的容量比較大 (可認為無窮大 )斜回。當有工件加工完后簇寻，工人把當前機床不用的刀具 (包括磨損刀具 )從機床刀具庫中卸下并送入中央刀具庫，同時把下一個工件所需的剩余刀具從中央刀具庫裝入機床刀具庫;若該工件所需的刀具不能全部裝入機床刀具庫時凳贰，多余的刀具暫時存放在中央刀具庫中市通，當該工件的部分工序結(jié)束后，再裝入其它刀具以進行以后工序的加工哗励。一旦工件裝配到某個機床上苫瘾，它應(yīng)該在完成所有的工序后才卸下來。每個工件加工所需的刀具全部都安裝到機床刀具庫界橱，機床才能對該工件進行加工湃彻。加工過程中的刀具借用由人工來完成。

由于加工過程中有刀具的磨損丛君，我們假定每個刀具都有可以估計的使用壽命短酵，當?shù)毒叩氖褂脡勖∮谒惺褂迷摰毒叩墓ば驎r間長度時，我們認為該刀具不能再使用修噪。為了保證生產(chǎn)的正常進行查库，一定數(shù)量的同規(guī)格刀具必須同時裝載到中央刀具庫中以供備用。如果每種規(guī)格的刀具數(shù)量較多黄琼，加工中的刀具借用次數(shù)就少樊销，刀具的等待時間就短，任務(wù)的在制時間就小;反之脏款，如果每種規(guī)格的刀具數(shù)量較少现柠，加工中的刀具借用次數(shù)就多，刀具的等待時間就長弛矛，任務(wù)的在制時間就大够吩。如何在一個容許的刀具購買資金預(yù)算下配置中央刀具庫中的刀具規(guī)格和數(shù)量，并最大限度的減少任務(wù)的在制時間丈氓，是本文研究的內(nèi)容周循。在本文中，假定：

不考慮機器故障;

每臺機床最多只分配一把同一規(guī)格的刀具;

每把刀具只占用一個刀盤位置;

每一個工序的執(zhí)行時間確定万俗，且事先已知;

3　求解在制時間和刀具等待時間的遞歸算法

3.1　問題簡化

在刀具移動的柔性制造系統(tǒng)中湾笛，刀具的控制策略決定了哪把刀具從哪個機床借用以及用完后是否歸還，所以刀具控制策略是產(chǎn)生刀具等待時間和運送時間的根源辆泄。但是蟋真，大量的實驗數(shù)據(jù)表明，刀具控制策略對任務(wù)的在制時間沒有明顯的影響;實際生產(chǎn)車間布局范圍都比較小铐坠，刀具的運送時間遠遠小于刀具的等待時間酷它，也遠遠小于工件的加工時間。

所以遂涛，在下文中悦阿，我們均不考慮刀具的運送時間和刀具的控制策略柄露。這樣，所有機床對刀具的申請都可以看成是向中央刀具庫提出來的丝板，而機床刀具庫僅僅變成對機床所能使用刀具數(shù)的一種形式上的約束窒汤。因此，整個加工過程中中央刀具庫配置的修改可以看成這樣：當機床加工完機床刀具庫所允許的所有工序后吓篙，把后面工序不再需要的刀具放回中央刀具庫杉硅，同時把后面工序需要的刀具裝入機床刀具庫。在工件的調(diào)度策略確定下深怕，求解任務(wù)的在制時間和每個機床對所需刀具的等待時間可以采用遞歸的方法來計算膘掰。要注意的是，當某種規(guī)格的一把刀具的使用壽命到達時佳遣，可以看成該規(guī)格刀具的總數(shù)量減1识埋，當某種規(guī)格的刀具數(shù)量為0時，則所有等待該規(guī)格刀具的時間都為無窮大零渐。整個加工過程類似于資源約束下的項目調(diào)度問題窒舟。在下文中，為了簡化計算诵盼，我們假定每個工件僅需要一道工序惠豺，這種假設(shè)對問題的分析不會產(chǎn)生影響。

3.2　算法步驟

令W為所有刀具規(guī)格集合风宁，稱向F=(n1洁墙，n2，…戒财，n|W|)為中央刀具庫的狀態(tài)或配置热监，其中ni表示刀具規(guī)格i的數(shù)量，ni≥0饮寞，i? W悬占。為了方便描述，在不會引起混淆的情況下拜岂，當特指“一個具體規(guī)格的刀具”時邓秕，我們在下文中有時也用“刀具”簡化稱呼，讀者可聯(lián)系上下文理解庵偏。

記M為柔性制造系統(tǒng)中的機床數(shù)目轻江，Pim機床m在時刻ti時當前工件剩余的加工時間長度。ti的修改方程為：

ti=ti-1+min(Pi-11母掀，Pi-12挤帕，…，Pi-1n)。

用Om表示指定給機床m加工的工件集合桌苔，Ajm表示機床m加工工件j時最后得到的刀具集合革睬，Om表示指定給機床m加工的工件集合安影，Tj表示工件j所需的全部刀具集合腻喇，djm表示機床m等待Ajm的有效等待時間長度，它表示工件j最后一次借到刀具的時間和上一次借到刀具的時間差膏蚓，j ? Om瓢谢，m?M。為了防止由于刀具的短缺而產(chǎn)生無限制的等待驮瞧，我們在算法中設(shè)計了一個定時器Timer氓扛，當其計數(shù)值超過設(shè)定的最大時間時，說明算法進入了無限制的等待论笔，從而自動退出采郎。求解在制時間和刀具等待時間的遞歸算法(算法1)的主要步驟如下：

step1 i=0，ti=0狂魔，Ajm=Tj蒜埋，djm=0，lm=0最楷，" 1 ￡ m ￡ M整份，" j ￡ Om，初始化所有機床的狀態(tài)為空閑籽孙，初始化Timer為一個較大的整數(shù);

Step2 如果所有機床的狀態(tài)都為空閑且其隊列都為空烈评，Makespan=ti，停止犯建。如果Timer定時時間到達该捎，Makespan=￥，停止张相。

Step3 卸載所有在ti時刻狀態(tài)為空閑的機床上的工件循贝，并把所有閑置的刀具歸還中央刀具庫;

Step4 按機床正在裝載時間的長度非遞增排序得到機床序列m1，m2根朱，…尉利，mM;

Step5 令k=1;

Step6 如果機床的狀態(tài)為空閑，則

Step6.1 如果機床mk的等待隊列為空敏盒，Step8;

Step6.2 如果機床mk的等待隊列不為空汤顷，從該機床的等待隊列中取優(yōu)先級最高的工件j并裝載到該機床上，令djmk=￥翁凳，修改該機床的狀態(tài)為正在裝載递促，lm=ti;

Step7 如果機床mk的狀態(tài)為正在裝載，如果中央刀具庫中有工件j所缺的閑置刀具，則選擇這些刀具送魁，修改中央刀具庫的狀態(tài)涉粘。如果工件j所需的刀具還沒有裝載完畢，修改Ajm中的集合元素笨奠，lm=ti;否則袭蝗，=ti-lmdjmk，修改該機床的狀態(tài)為正在加工般婆。

Step8 k=k+l到腥，如果k≤M，轉(zhuǎn)Step6;

Step9 i=i+1蔚袍，按公式(1)移動ti到下一次正在加工工件的完時刻乡范，并置相應(yīng)機床狀態(tài)為空閑，轉(zhuǎn)Step2;

4　規(guī)劃中央刀具庫配置的啟發(fā)式算法

本節(jié)介紹的啟發(fā)式算法就是逐步增加關(guān)鍵機床上的關(guān)鍵刀具的數(shù)量啤咽，所謂關(guān)鍵機床就是指所有機床中最后一個加工完工件的機床晋辆，所為關(guān)鍵刀具就是指“刀具的等待時間之和/刀具成本”最大的刀具。算法的重復(fù)執(zhí)行過程可以用圖1來描述宇整。假定機床3在當前這一步是關(guān)鍵機床瓶佳，任務(wù)的在制時間在A點結(jié)束，那么在初始中央刀具庫狀態(tài)中增加機床3加工過程中關(guān)鍵刀具的數(shù)量没陡，重新計算任務(wù)的在制時間和關(guān)鍵機床涩哟，并確定關(guān)鍵機床上的關(guān)鍵刀具。假設(shè)機床3在B點結(jié)束焊循，這一步任務(wù)的在制時間在C點結(jié)束帝愉，機床1變成了關(guān)鍵機床，則在初始中央刀具庫中增加機床1加工過程中的關(guān)鍵刀具的數(shù)量沈跷，依此類推暖麻。整個過程不斷重復(fù)，直到超過允許的刀具購買資金亮铛。本文的算法綜合了一些其它文獻的思想瘾手。

本文僅研究刀具需求規(guī)劃問題。雖然工件調(diào)度對在制時間影響很大受卒，但這是一個非常復(fù)雜的問題光拥。我們可以認為在制時間由兩部分組成：一部分由工件調(diào)度引起，另一部分由刀具配置引起筋蝴。性能最好的工件調(diào)度策略可以通過比較來選擇厨摔，但這不是本文的重點。在以后的描述中岛涝，我們均假定工件調(diào)度策略已經(jīng)確定脓杉。

令B為允許的刀具購買資金，Ci為刀具規(guī)格i的購買價格。則規(guī)劃中央刀具庫配置的算法(算法2)如下：

step1 ni=1球散，對所有i? W尿赚， B'=B- S Ci

i? W

;

step2 采用算法1求的關(guān)鍵機床(如果有多臺關(guān)鍵機床，任意取其中一臺作為關(guān)鍵機床)蕉堰，記為c凌净，同時得到Ajc和djc，" j ? Oc;

step3 令i=1;

step4 令j=1嘁灯，xi=0;

step5 如果 i ?Ajc泻蚊，則xi=djc+xi;

step6 j=j+1躲舌，如果j≤|Oc|丑婿，轉(zhuǎn)Step5;

step7 i=i+1，如果i≤|W|没卸，轉(zhuǎn)step4;

step8 按xi/Ci非遞增的順序排列得到刀具序列t1羹奉，t2，…约计，t|Oc|;

step9 令k=1

step10 如果Ctk￡ B'诀拭，則ntk=ntk+1，B'=B'-Ctk善簸，轉(zhuǎn)Step2;

step11 k=k+1传撰，如果k > |W|，停止呛产。否則距搂，轉(zhuǎn)Step10;

5　計算結(jié)果與比較

計算環(huán)境如下：機床數(shù)4～8，工件數(shù)目30～80治勒，每個工件所需得刀具規(guī)格數(shù)30～50恰磷，刀具規(guī)格總數(shù)50～100，每個工件的執(zhí)行時間50～100路倔，每種規(guī)格刀具的價格10～100熏屎，使用壽命為2000～3000，每臺機床的機床刀具庫容量固定為60逮赋，允許的刀具購買資金預(yù)算取任務(wù)所需的最小刀具成本的1.5倍京嗽，最小刀具成本就是當在制時間不為無窮大時任務(wù)所需的最小刀具集合的成本。

工件調(diào)度策略采用如下兩個經(jīng)常使用的策略：

加工時間最短的優(yōu)先(SPT);

加工時間最長的優(yōu)先(LPT);

我們隨機產(chǎn)生了60個問題來測試卓奄，并和其它某文獻中最優(yōu)算法TGSA進行比較墨叛。為了使其具有可比性，我們在編寫TGSA算法時并村，令刀具的運送時間為0巍实，并修改本文介紹的遞歸算法來求解任務(wù)的在制時間和每把刀具的實際等待時間。由于無法得到最優(yōu)解，我們?nèi)∠鄬π阅鼙?relative performance ratio棚潦，RPR)作為評價標準令漂，RPR定義為(Sa-SB)/SB，Sa表示采用算法a得到的解丸边，SB表示兩個算法中的最優(yōu)解叠必。表1列出了兩種算法的比較結(jié)果。

無論采取什么工件調(diào)度策略妹窖，本文介紹的算法和TGSA相比纬朝，都有較優(yōu)的解。我們分析原因如下：

TGSA增加刀具時不考慮關(guān)鍵機床骄呼，導(dǎo)致某些等待時間較長而對在制時間沒有影響的刀具浪費了刀具購買資金共苛，而本文算法恰恰避免了這種情況的出現(xiàn);

TGSA嚴格的把刀具按其成本分為A，B蜓萄，C三類氢莫，沒有綜合考慮其對在制時間的影響，本文以刀具在關(guān)鍵機床上的等待時間之和與刀具成本之比來定義關(guān)鍵刀具秤慌，綜合了單位成本上的等待時間邦擎，有效利用了刀具購買資金;

6　結(jié)論

文章主要討論了柔性制造系統(tǒng)的刀具需求規(guī)劃問題，首先利用已有文獻所報道的結(jié)論簡化了實際問題式涝，給出了求解在制時間和刀具等待時間的遞歸算法僧逞，同時給出了一個求解刀具需求規(guī)劃的啟發(fā)式算法。為了觀察該算法的性能图汪，我們通過隨機數(shù)據(jù)產(chǎn)生并構(gòu)成了60個刀具需求規(guī)劃問題杏蟋，并采用兩種不同的刀具調(diào)度策略進行了數(shù)據(jù)測試。和已有算法進行比較后派憨，我們發(fā)現(xiàn)無論采取什么工件調(diào)度策略购廊，文章介紹的算法都具有較優(yōu)的解。

聲明：本網(wǎng)站所收集的部分公開資料來源于互聯(lián)網(wǎng)笔碌，轉(zhuǎn)載的目的在于傳遞更多信息及用于網(wǎng)絡(luò)分享刃镶，并不代表本站贊同其觀點和對其真實性負責，也不構(gòu)成任何其他建議甚脉。本站部分作品是由網(wǎng)友自主投稿和發(fā)布丸升、編輯整理上傳，對此類作品本站僅提供交流平臺牺氨，不為其版權(quán)負責狡耻。如果您發(fā)現(xiàn)網(wǎng)站上所用視頻、圖片猴凹、文字如涉及作品版權(quán)問題夷狰，請第一時間告知岭皂，我們將根據(jù)您提供的證明材料確認版權(quán)并按國家標準支付稿酬或立即刪除內(nèi)容，以保證您的權(quán)益沼头！聯(lián)系電話：010-58612588 或 Email:editor@mmsonline.com.cn爷绘。