張 昕，施 爍，楊建國

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

0 引言

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

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

1 調(diào)度問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中M11對應(yīng)圖1 中車床1。

圖1 按工藝布置車間布局圖

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

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

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

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

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

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

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

(2)大型公共設(shè)備行走時長計算

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

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

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

(4)右重移策略

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

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

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

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

圖2 右重移策略圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 應(yīng)用示例

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

調(diào)度結(jié)果見甘特圖，如圖4 所示。由測試得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;對應(yīng)大型公共設(shè)備行走時長為:0→2→2→3→2→2。圖中，矩形作為邊界表示大型公共設(shè)備的優(yōu)化情況。

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

表2 車間約束

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

5 結(jié)束語

本文建立了大型公共設(shè)備調(diào)度模型，對算法關(guān)鍵部分進行了詳細設(shè)計。在調(diào)度序列的基礎(chǔ)上，構(gòu)造了車間布局、工件信息、大型公共設(shè)備行走路徑和行走時長的數(shù)學(xué)計算模型，同時制定了動態(tài)右重移策略，實現(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］王海瑤，蔣增強，葛茂根.基于規(guī)則組合的Job Shop 多目標柔性調(diào)度方法［J］.合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版)，2010，33(1):14 -18.

［4］余建軍，孫樹棟，劉易勇.基于免疫算法的多目標柔性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é)報，2012，47(3):509-515.

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

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

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

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