基于調(diào)度序列的大型公共設(shè)備規(guī)劃優(yōu)化設(shè)計(jì)研究*

張 昕，施 爍，楊建國(guó)

(1.上海電氣機(jī)床成套工程有限公司，上海 200041;2.東華大學(xué) 機(jī)械工程學(xué)院，上海 200051)

0 引言

車(chē)間生產(chǎn)調(diào)度問(wèn)題是最困難的約束組合優(yōu)化問(wèn)題［1］，因?yàn)闆](méi)有有效的算法能在多項(xiàng)式時(shí)間之內(nèi)算得它的最優(yōu)解。對(duì)于許多具有大型工件的加工車(chē)間而言，車(chē)間的調(diào)度問(wèn)題除了一般的工件與機(jī)床的約束關(guān)系之外，還要受到例如行車(chē)、自動(dòng)化小車(chē)(AGV)等公共資源的約束。由于通常行車(chē)數(shù)量受限，故大型工件的搬運(yùn)除了考慮工序完工時(shí)間之外，還要考慮大型工件搬運(yùn)路徑、搬運(yùn)時(shí)間等約束［2］。

在實(shí)際生產(chǎn)過(guò)程中，大型公共設(shè)備的運(yùn)輸時(shí)間涉及行車(chē)的行走路徑，即設(shè)備布局情況。在本文算法中，先用遺傳算法解決基本車(chē)間的調(diào)度問(wèn)題，得出調(diào)度最優(yōu)解后，在調(diào)度序列的基礎(chǔ)上，進(jìn)行公共設(shè)備規(guī)劃設(shè)計(jì)。在公共設(shè)備規(guī)劃設(shè)計(jì)時(shí)，考慮其現(xiàn)有車(chē)間布局，動(dòng)態(tài)搜索大型公共設(shè)備行走路徑，利用動(dòng)態(tài)右重移策略解決大型公共設(shè)備合理規(guī)劃問(wèn)題。

1 調(diào)度問(wèn)題

大型公共設(shè)備調(diào)度問(wèn)題可以描述為:n個(gè)工件{J1，J2，…，Jn}，在m臺(tái)設(shè)備{M1，M2，…，Mm}上加工。每個(gè)工件由一系列工序Ojx(x=1，2，…，TOj)組成，Ojx和TOj分別表示工件j的第x道工序和工件j的總工序數(shù);工序Ojx在指定設(shè)備Mijx上加工，Mijx∈(M1，M2，…，Mm)，加工時(shí)間為tijx;其中n個(gè)工件中有q個(gè)工件是重型工件，對(duì)于某一個(gè)重型工件，其加工工序Ojx及Oj(x+1)之間必須有一個(gè)大型公共設(shè)備的運(yùn)輸時(shí)長(zhǎng)Njx，(x+1)，且大型公共設(shè)備使用次數(shù)為T(mén)Oj。大型公共設(shè)備的運(yùn)輸優(yōu)先級(jí)與加工時(shí)間的先后順序有關(guān)，且運(yùn)輸時(shí)長(zhǎng)與大型公共設(shè)備的行走路徑有關(guān)。同時(shí)，加工過(guò)程中，根據(jù)調(diào)度模型，作出如下假設(shè):

①每一個(gè)設(shè)備位置點(diǎn)旁有貨架緩沖區(qū);

②設(shè)備旁貨架緩沖區(qū)可存放的工件數(shù)不限;

③每個(gè)貨架緩沖區(qū)與設(shè)備加工區(qū)屬于同一區(qū)域，該區(qū)域內(nèi)不再使用大型公共設(shè)備;

④大型公共設(shè)備的起始位置默認(rèn)為初始工序的搬運(yùn)位置;

⑤同一重型工件的工序之間使用大型公共設(shè)備具有不同的優(yōu)先級(jí);

⑥不同重型工件的工序之間使用大型公共設(shè)備具有不同的優(yōu)先級(jí);

⑦同一時(shí)刻大型公共大型設(shè)備只能運(yùn)輸一個(gè)工件。

在滿足上述條件的前提下對(duì)大型公共設(shè)備調(diào)度模型中的工件進(jìn)行調(diào)度安排，確定每個(gè)工件的加工設(shè)備以及在各臺(tái)設(shè)備上的開(kāi)工時(shí)間，考慮大型公共設(shè)備生產(chǎn)調(diào)度過(guò)程中涉及的目標(biāo)函數(shù)［3-4］:工件完工時(shí)間，建立(1)所示目標(biāo)，使工件最大完工時(shí)間最小。

min(f1)=min(makespan)=min(max(Ci)) (1)其中，設(shè)Ci表示第i個(gè)工件的完工時(shí)間。

2 調(diào)度問(wèn)題模型構(gòu)建

2.1 車(chē)間布局的數(shù)學(xué)描述

車(chē)間設(shè)施布局就是按照一定的原則，在已確定的車(chē)間場(chǎng)地內(nèi)，合理地安排車(chē)間內(nèi)部各類(lèi)加工設(shè)施、輔助服務(wù)設(shè)施等的具體位置，并對(duì)人員及物料的移動(dòng)路線做最可行的設(shè)計(jì)。既保證生產(chǎn)活動(dòng)能有效進(jìn)行和獲得最大的生產(chǎn)經(jīng)濟(jì)效益，又為員工提供一個(gè)安全、方便、舒適的工作環(huán)境［5］。

現(xiàn)已知，普遍應(yīng)用的典型布局方式有:按工藝布置、按產(chǎn)品布置、按固定工位布置和按成組生產(chǎn)原則布置。根據(jù)調(diào)研可知，某車(chē)間為按工藝布置方式。按車(chē)間布局即是將相近的工藝歸入同一組，如車(chē)床組、五軸加工中心組、三軸立式加工中心組、銑床組等，并基于設(shè)施間的物流來(lái)確定一個(gè)工藝設(shè)備相對(duì)另一個(gè)設(shè)備的位置，在制造業(yè)內(nèi)廣泛用于單件小批量生產(chǎn)方式。按工藝布置見(jiàn)圖1。

車(chē)間布局矩陣與車(chē)間布局及大型公共設(shè)備的軌道方向有關(guān)。其中車(chē)間多為矩形c·d，大型公共設(shè)備的軌道方向與車(chē)間矩形一致。車(chē)間布局矩陣大小為p×q，其中p代表該車(chē)間d 方向最大設(shè)備行數(shù)，q代表該車(chē)間c 方向最大設(shè)備數(shù)，當(dāng)矩陣對(duì)應(yīng)的位置處無(wú)設(shè)備則用0 表示。由圖1 知，則p=4，q=5。則車(chē)間布局矩陣為:

其中M11對(duì)應(yīng)圖1 中車(chē)床1。

圖1 按工藝布置車(chē)間布局圖

2.2 工件信息的數(shù)學(xué)描述

若已知有n個(gè)工件{J1，J2，…，Jn}參與調(diào)度，其中有q個(gè)重型工件{q=1，2，3...n-1}，則工件矩陣大小為的矩陣，其中重型工件在矩陣中用1 表示，普通工件用0 表示。假設(shè)參與調(diào)度的工件共有J1，J2，J3，則矩陣表示為［0 1 0 ］，其中J2為重型工件。

2.3 大型公共設(shè)備動(dòng)態(tài)路徑規(guī)劃

(1)大型公共設(shè)備行走路徑計(jì)算公式

在啟用大型公共設(shè)備運(yùn)輸重型工件時(shí)，考慮大型公共設(shè)備運(yùn)行平穩(wěn)為勻速運(yùn)動(dòng)，忽略其設(shè)備初始時(shí)間，即起吊時(shí)間?？芍笮凸苍O(shè)備運(yùn)輸時(shí)其位置由初始設(shè)備轉(zhuǎn)至另一設(shè)備的時(shí)間與其行走路徑和車(chē)間布局有關(guān)，且和車(chē)間布局中設(shè)備間的距離有關(guān)［6］。

根據(jù)2.1 節(jié)車(chē)間布局的數(shù)學(xué)描述及車(chē)間布局矩陣，計(jì)算大型公共設(shè)備行走路徑。其計(jì)算公式見(jiàn)式(2)、(3)、(4)。

式中，(a1，b1)，(a2，b2)代表設(shè)備M1、M2在車(chē)間布局矩陣中的位置坐標(biāo)。式(2)表示車(chē)間方向c 上，大型公共設(shè)備在車(chē)間布局矩陣中同一行設(shè)備中轉(zhuǎn)移的路徑計(jì)算公式。式(3)表示車(chē)間方向c 上，大型公共設(shè)備在車(chē)間布局矩陣中相鄰兩行設(shè)備間轉(zhuǎn)移的路徑計(jì)算公式。式(4)表示在車(chē)間方向c 上，大型公共設(shè)備在車(chē)間布局矩陣中非相鄰非同行兩行設(shè)備間轉(zhuǎn)移的路徑計(jì)算公式。

(2)大型公共設(shè)備行走時(shí)長(zhǎng)計(jì)算

大型公共設(shè)備行走時(shí)長(zhǎng)的計(jì)算與行走路徑，車(chē)間中設(shè)備間的距離dis及大型公共設(shè)備行走速度v相關(guān)。由于默認(rèn)大型公共設(shè)備起始位置默認(rèn)為初始工序的搬運(yùn)位置，故大型公共設(shè)備第一步行走時(shí)長(zhǎng)為0。行走時(shí)長(zhǎng)T=(dis×route)/v。

(3)工序優(yōu)先級(jí)確定

一般地說(shuō)，大型公共設(shè)備路徑行走的關(guān)鍵問(wèn)題在于解決多個(gè)重型工件之間工序的優(yōu)先級(jí)問(wèn)題。已知同一工件工序間的加工具有優(yōu)先級(jí)順序，而不同工件工序間的加工具有相同優(yōu)先級(jí)［7-8］。采用遺傳算法求解出調(diào)度最優(yōu)結(jié)果，根據(jù)最優(yōu)結(jié)果中各工序的起始加工時(shí)間，可得出多個(gè)重型工件的工序加工優(yōu)先級(jí)矩陣。根據(jù)多個(gè)重型工件的加工優(yōu)先級(jí)矩陣，可得出大型公共設(shè)備的初始行走路徑。

(4)右重移策略

右重移策略常用于解決動(dòng)態(tài)調(diào)度問(wèn)題［9］，當(dāng)緊急工件插入時(shí)，未受影響的工序統(tǒng)一向右移，右移量為緊急工序的時(shí)長(zhǎng)。算法中將大型公共設(shè)備運(yùn)輸時(shí)間作為緊急插入時(shí)間來(lái)處理，但與緊急工件工序插入的解決策略并不完全一致。圖2 為示例甘特圖，虛線矩形為重型工件工序。根據(jù)大型公共設(shè)備的調(diào)度模型之可知，默認(rèn)大型公共設(shè)備的初始位置在第一道工序處，故其搬運(yùn)路徑為0，下一步搬運(yùn)是從初始位置1/1(工件1 工序1)處至如圖中在虛線部位1/2(工件1 工序2)處，插入大型公共設(shè)備的運(yùn)輸時(shí)長(zhǎng)，此步的右重移策略過(guò)程如下:

步驟1:由大型公共設(shè)備行走路徑公式計(jì)算大型公共設(shè)備從初始位置1/1 處運(yùn)輸至1/2 處的行車(chē)行走路徑，以及行走路徑時(shí)長(zhǎng)即M3至M2的運(yùn)輸時(shí)間t，大型公共設(shè)備運(yùn)輸將重型工件從原始位置運(yùn)輸至下一加工位置的設(shè)備，即圖2 中設(shè)備為M2。

步驟2:大型公共設(shè)備運(yùn)輸至M2上時(shí)，該重型工件工序(工件1 工序2)以及在M2設(shè)備上在重型工件工序之后加工的所有工序，向右移t的時(shí)間量。

步驟3:其他設(shè)備(不包括大型公共設(shè)備運(yùn)輸至的設(shè)備，如圖2 中M1，M3)上工序時(shí)間右移判斷。其他設(shè)備，若插入時(shí)間點(diǎn)(工件1 工序2 的加工起始時(shí)間)在該工序加工過(guò)程中(如工件3 工序1)，則該工序之后的所有加工工序(如圖2 中工件1 工序3)，向右移t的時(shí)間量;否則，該插入時(shí)間點(diǎn)后的所有加工工序向右移t的時(shí)間量(如圖2 中工件3 工序2 和工件2 工序3)。

圖2 右重移策略圖

3 混合遺傳算法的實(shí)現(xiàn)

步驟1:讀取調(diào)度任務(wù)信息及車(chē)間布局矩陣信息;

步驟2:將所得任務(wù)信息處理成遺傳算法所需的設(shè)備約束矩陣、時(shí)間約束矩陣，工件信息矩陣及車(chē)間布局矩陣，同時(shí)初始化大型公共設(shè)備路徑矩陣和工序優(yōu)先級(jí)矩陣。

步驟3:將設(shè)備約束矩陣及時(shí)間約束矩陣作為遺傳算法的輸入并輸入。

步驟4:采用遺傳算法求解調(diào)度問(wèn)題。輸出其調(diào)度起始時(shí)間矩陣以及調(diào)度終止時(shí)間矩陣。

步驟5:根據(jù)步驟4 中的調(diào)度起始時(shí)間矩陣、調(diào)度終止時(shí)間矩陣和步驟2 中的工件信息矩陣及車(chē)間布局矩陣，生成公共設(shè)備路徑矩陣Route。

步驟6:設(shè)置計(jì)數(shù)器i=0;

步驟7:讀取路徑矩陣Route(i)中的設(shè)備，并計(jì)算出該路徑范圍內(nèi)路徑行走時(shí)長(zhǎng)。

步驟8:判斷行走路徑是否需要添加多工件同時(shí)運(yùn)輸工序，若是則確定多工件同時(shí)運(yùn)輸工序并計(jì)算器行走時(shí)長(zhǎng)，否則轉(zhuǎn)入步驟9。

步驟9:采用動(dòng)態(tài)右重移策略，將該路徑的行走時(shí)長(zhǎng)插入至調(diào)度結(jié)果中。

步驟10:更新調(diào)度起始時(shí)間矩陣、調(diào)度終止時(shí)間矩陣。并根據(jù)更新后的起始時(shí)間矩陣和終止時(shí)間矩陣得出更新后的路徑矩陣及工序優(yōu)先級(jí)矩陣。

步驟11:i=i+1，若i=N，則輸出調(diào)度結(jié)果，算法終止。否則，返回步驟7。

步驟12:結(jié)束，見(jiàn)圖3。

圖3 公共設(shè)備調(diào)度流程圖

4 應(yīng)用示例

根據(jù)大型公共設(shè)備優(yōu)化方法，利用該方法針對(duì)大型公共設(shè)備優(yōu)化調(diào)度實(shí)例進(jìn)行測(cè)試，以驗(yàn)證方法的有效性。測(cè)試案例來(lái)源于案例ft06(6* 6)案例［10］，見(jiàn)表1。同時(shí)根據(jù)車(chē)間實(shí)際生產(chǎn)情況，確定車(chē)間的約束見(jiàn)表2。調(diào)度最優(yōu)解的遺傳算法參數(shù)為:種群大小popSize=50，迭代次數(shù)maxGen=40，選擇算子psel=0.1，交叉因子pxover=0.85，變異因子pmutation=0.2，保優(yōu)個(gè)體數(shù)=3。

調(diào)度結(jié)果見(jiàn)甘特圖，如圖4 所示。由測(cè)試得ft06案例調(diào)度最優(yōu)解makespan=55，已知現(xiàn)有ft06 案例的最優(yōu)解為55。在ft06 案例最優(yōu)解的基礎(chǔ)上，考慮大型公共設(shè)備優(yōu)化的調(diào)度結(jié)果為MakeSpan=64。大型公共設(shè)備優(yōu)化方法可得，大型公共設(shè)備的行走路徑為:M2→M4→M6→M1→M5→M3;對(duì)應(yīng)大型公共設(shè)備行走時(shí)長(zhǎng)為:0→2→2→3→2→2。圖中，矩形作為邊界表示大型公共設(shè)備的優(yōu)化情況。

表1 ft06 設(shè)備/時(shí)間約束

表2 車(chē)間約束

圖4 大型公共設(shè)備調(diào)度甘特圖

5 結(jié)束語(yǔ)

本文建立了大型公共設(shè)備調(diào)度模型，對(duì)算法關(guān)鍵部分進(jìn)行了詳細(xì)設(shè)計(jì)。在調(diào)度序列的基礎(chǔ)上，構(gòu)造了車(chē)間布局、工件信息、大型公共設(shè)備行走路徑和行走時(shí)長(zhǎng)的數(shù)學(xué)計(jì)算模型，同時(shí)制定了動(dòng)態(tài)右重移策略，實(shí)現(xiàn)大型公共設(shè)備優(yōu)化規(guī)劃的目的。

［1］BRUCKER P，SCHLIE R. Job-Shop scheduling with multi-purpose machines［J］. Computing，1990，45(4):369-375.

［2］BRANDIMARTE P. Routing and scheduling in a flexible Job-shop by taboo search［J］. Annals of Operations Research，1993，22(2):157 -183.

［3］王?，?，蔣增強(qiáng)，葛茂根.基于規(guī)則組合的Job Shop 多目標(biāo)柔性調(diào)度方法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010，33(1):14 -18.

［4］余建軍，孫樹(shù)棟，劉易勇.基于免疫算法的多目標(biāo)柔性Job Shop 調(diào)度研究［J］.系統(tǒng)工程學(xué)，2007，22(5):214 -222.

［5］NELSON R，HOLLOWAY C，WONG R. Centralized scheduling and priority implementation heuristics for a dynamic Job Shop model with due dates and variable processing time［J］.IIE Transactions，1997，9(1):96 -102.

［6］帥旗，姚錫凡.基于啟發(fā)性規(guī)則及關(guān)鍵路徑調(diào)整的柔性作業(yè)調(diào)度優(yōu)化算法［J］.西南交通大學(xué)學(xué)報(bào)，2012，47(3):509-515.

［7］袁 坤，朱劍英.一種求解多目標(biāo)柔性Job Shop 調(diào)度的改進(jìn)遺傳算法［J］.中國(guó)機(jī)械工程，2007，18(2):651 -656.

［8］趙有輝.動(dòng)態(tài)多目標(biāo)柔性調(diào)度問(wèn)題的改進(jìn)遺傳算法研究［J］.電腦知識(shí)與技術(shù)，2012，8(4):829 -832.

［9］潘全科.智能制造系統(tǒng)多目標(biāo)車(chē)間調(diào)度研究［D］. 南京:南京航空航天大學(xué)，2003.

［10］MUTH J，THOMPSON G E. Industrial Scheduling［R］.Prentice Hall.NJ:Endlewood Cliffs，1963.