基于調度序列的大型公共設備規劃優化設計研究*

張 昕，施 爍，楊建國

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

0 引言

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

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

1 調度問題

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

①每一個設備位置點旁有貨架緩沖區;

②設備旁貨架緩沖區可存放的工件數不限;

③每個貨架緩沖區與設備加工區屬于同一區域，該區域內不再使用大型公共設備;

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

⑤同一重型工件的工序之間使用大型公共設備具有不同的優先級;

⑥不同重型工件的工序之間使用大型公共設備具有不同的優先級;

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

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

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

2 調度問題模型構建

2.1 車間布局的數學描述

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

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

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

其中M11對應圖1 中車床1。

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

2.2 工件信息的數學描述

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

2.3 大型公共設備動態路徑規劃

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

在啟用大型公共設備運輸重型工件時，考慮大型公共設備運行平穩為勻速運動，忽略其設備初始時間，即起吊時間?？芍笮凸苍O備運輸時其位置由初始設備轉至另一設備的時間與其行走路徑和車間布局有關，且和車間布局中設備間的距離有關［6］。

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

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

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

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

(3)工序優先級確定

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

(4)右重移策略

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

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

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

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

圖2 右重移策略圖

3 混合遺傳算法的實現

步驟1:讀取調度任務信息及車間布局矩陣信息;

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

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

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

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

步驟6:設置計數器i=0;

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

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

步驟9:采用動態右重移策略，將該路徑的行走時長插入至調度結果中。

步驟10:更新調度起始時間矩陣、調度終止時間矩陣。并根據更新后的起始時間矩陣和終止時間矩陣得出更新后的路徑矩陣及工序優先級矩陣。

步驟11:i=i+1，若i=N，則輸出調度結果，算法終止。否則，返回步驟7。

步驟12:結束，見圖3。

圖3 公共設備調度流程圖

4 應用示例

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

調度結果見甘特圖，如圖4 所示。由測試得ft06案例調度最優解makespan=55，已知現有ft06 案例的最優解為55。在ft06 案例最優解的基礎上，考慮大型公共設備優化的調度結果為MakeSpan=64。大型公共設備優化方法可得，大型公共設備的行走路徑為:M2→M4→M6→M1→M5→M3;對應大型公共設備行走時長為:0→2→2→3→2→2。圖中，矩形作為邊界表示大型公共設備的優化情況。

表1 ft06 設備/時間約束

表2 車間約束

圖4 大型公共設備調度甘特圖

5 結束語

本文建立了大型公共設備調度模型，對算法關鍵部分進行了詳細設計。在調度序列的基礎上，構造了車間布局、工件信息、大型公共設備行走路徑和行走時長的數學計算模型，同時制定了動態右重移策略，實現大型公共設備優化規劃的目的。

［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］王?，帲Y增強，葛茂根.基于規則組合的Job Shop 多目標柔性調度方法［J］.合肥工業大學學報(自然科學版)，2010，33(1):14 -18.

［4］余建軍，孫樹棟，劉易勇.基于免疫算法的多目標柔性Job Shop 調度研究［J］.系統工程學，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］帥旗，姚錫凡.基于啟發性規則及關鍵路徑調整的柔性作業調度優化算法［J］.西南交通大學學報，2012，47(3):509-515.

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

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

［9］潘全科.智能制造系統多目標車間調度研究［D］. 南京:南京航空航天大學，2003.

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