混合工作日歷下批量生產(chǎn)柔性作業(yè)車間多目標調度方法

曾 強，吳錦錦，王培露，李明金

(河南理工大學 1.能源科學與工程學院；2.圖書館，河南 焦作 454000)

當前，批量生產(chǎn)已成為我國最主要的生產(chǎn)方式之一。批量生產(chǎn)作業(yè)車間調度對于提高生產(chǎn)率，降低生產(chǎn)成本，保證均衡生產(chǎn)等具有重要意義。隨著市場競爭的日益激烈，生產(chǎn)調度過程中需要綜合考慮多個目標。在同一個企業(yè)或車間里，不同型號、新舊不一而功能相同的設備共同存在，同一道工序往往能在多臺設備上加工。調查發(fā)現(xiàn)，在一些企業(yè)或車間里不同設備有可能按不同的工作日歷運行。因此，受到多目標、設備柔性、混合工作日歷因素的綜合影響，調度人員往往無從尋優(yōu)，主要依靠自身經(jīng)驗進行生產(chǎn)調度，導致調度效果較差，給企業(yè)帶來較大損失。因此，混合工作日歷下批量生產(chǎn)柔性作業(yè)車間調度成為一個重要研究方向。

現(xiàn)有作業(yè)車間調度對工作日歷的處理方式主要有3種：完全不考慮工作日歷、調度中不考慮調度后考慮工作日歷、調度中考慮工作日歷。第1種處理方式在調度前后均不考慮工作日歷[1-3]。該方式計算量最小，但調度方案與實踐脫節(jié)。第2種處理方式在調度前不考慮工作日歷，調度后進行時間映射[4]。該方式計算量較小，當設備采用相同工作日歷運行時可采用這種方式。第3種處理方式在調度過程中即根據(jù)工作日歷準確推算設備調整和工序加工起止時刻。該方式雖計算量相對較大，但當設備采用混合工作日歷運行時，采用該方式才能得到有效調度方案。工作日歷是工作制和工作時段(或工作班次)的合稱。目前，關于調度中考慮工作日歷的作業(yè)車間調度研究成果很少，這些文獻對工作日歷的處理不夠全面，文獻[5-6]未考慮工作班次(工作時段)，文獻[7]未考慮工作制。

柔性作業(yè)車間多目標調度常用的求解方法有“間接法”和“直接法”兩種。間接法將多目標轉化為單目標求解，如極大極小法、線性加權和法[8]、主要目標法[9]、功效系數(shù)法[10]、分層排序法[11]等。該方法一次只能得到一個“最優(yōu)解”而不能得到最優(yōu)解集。直接法在多目標空間中尋找最優(yōu)解集，其中運用最多的是基于Pareto尋優(yōu)的方法，包括多目標遺傳算法[12]、強化Pareto遺傳算法[13]、小生境Pareto遺傳算法[14]、非支配排序遺傳算法[15]等。文獻[14, 16]通過研究已經(jīng)得出NSGA優(yōu)于其他算法的結論。隨著研究的不斷深入，第一代非支配排序遺傳算法(non-dominated sorting genetic algorithm，NSGA)在多目標優(yōu)化算法中的缺點不斷地暴露。為了更好地解決多目標優(yōu)化問題，學者提出了帶精英策略的非支配排序的遺傳算法(elitist non-dominated sorting genetic algorithm，NSGA-Ⅱ)。NSGA-Ⅱ降低了非劣排序遺傳算法的復雜性，具有運行速度快、解集的收斂性好的優(yōu)點。

在批量生產(chǎn)方式下，生產(chǎn)周期的縮短，主要依賴于精細化調度。常用的措施有3種。1) 提前調整：將工序時間細分為設備調整時間和加工時間，若同一加工子批的前后2道工序所用設備不同，可使其下道工序提前進行設備調整。2) 交叉作業(yè)：將同一個加工子批劃分為多個移動子批，采用平順移動方式移動，實現(xiàn)同一個加工子批前后工序的交叉作業(yè)。3) 擠壓安排：采用“間隙擠壓”法安排工序[17]，最大程度地減少設備空閑時間。

由于混合工作日歷下批量生產(chǎn)柔性作業(yè)車間多目標調度在柔性作業(yè)車間調度的基礎上進一步考慮了混合工作日歷、多目標優(yōu)化、批量生產(chǎn)等因素，因此是一個高度復雜的NP難問題。基于此，本文提出了一種混合工作日歷下批量生產(chǎn)柔性作業(yè)車間多目標調度方法以輔助生產(chǎn)調度。

1 混合工作日歷下批量生產(chǎn)柔性作業(yè)車間多目標調度模型

1.1 問題描述

車間需在m臺設備上安排n批量產(chǎn)品(n個加工子批)的加工任務。假設如下：1) 各加工子批有多道工序，一道工序的可選加工設備可能不唯一；2) 各加工子批的工藝流程、設備調整時間、加工時間已知；3) 同一加工子批允許劃分為移動子批，采用平順移動方式移動，移動時間可忽略；4) 一個加工子批的加工不允許被其他加工子批打斷；5) 各加工子批優(yōu)先級相同；6) 在同一個調度周期內，各設備按設定的工作日歷(工作制和工作時段的合稱)運行，不允許改變；7) 當設備按其工作日歷啟停時，該設備上對應的工作同步啟停；8) 設備初始時間軸連續(xù)；9) 調度從指定的調度起始時刻往后進行。在以上假設條件下，為調度人員提供一個Pareto調度集供其決策，優(yōu)化目標是生產(chǎn)周期最短，制造成本最低。

1.2 符號說明

表1給出了本模型涉及的符號。

表1 符號定義Table1 Symbol definition

1.3 模型構建

1) 目標函數(shù)。

2) 約束條件。

其中，式(1)表示生產(chǎn)周期最小；式(2)表示制造成本最低；式(3)表示一道工序只能由m臺設備中的其中一臺完成；式(4)表示若Ji的工序j和工序j?1在同一臺設備上加工，則Ji的第一移動子批必須在工序j?1全部加工之后才能開始調整；式(5)表示若Ji的工序j和工序j?1不在同一臺設備上加工，則Ji的任意移動子批s的工序j可以提前進行調整，但必須在工序j?1完工后才可以開始加工；式(6)表示一臺設備不能同時加工兩道工序；式(7)表示任意工序的完工時刻與開始調整時刻之差不能小于其所需加工時間和調整時間之和；式(8)表示任意工序的設備加工開始時刻與加工結束時刻之間的有效時間與實際加工時間相等；式(9)表示任意工序的設備調整開始時刻與調整結束時刻之間的有效時間與實際調整時間相等；式(10)表示任意工序的設備調整開始時刻和結束時刻、任意移動子批加工開始時刻和結束時刻都在設備的工作時段內；式(11)表示任意工序的調整開始時刻不能早于調度起始時刻。

2 NSGA II算法設計

上述問題是一個高度復雜的NP難問題，一般的數(shù)學方法無法求解。鑒于NSGA-Ⅱ的優(yōu)點，以Excel VBA為平臺，設計NSGA-Ⅱ算法對其求解。

2.1 定義對象、變量及數(shù)組

根據(jù)算法需要，定義了圖1所示的自定義類型、表2所示的變量和數(shù)組。圖1中，Mb為調度前設備時間狀態(tài)數(shù)組，Mb(i).Ts為設備i的調度前時間狀態(tài)數(shù)組；J為加工子批數(shù)組，J(i)為加工子批i；Chr為種群數(shù)組，Chr(i)為個體i。

圖1 自定義類型Figure1 Custom type

2.2 算法流程

本文算法流程[18]如圖2所示。

圖2 算法流程Figure2 Flow of the algorithm

2.3 讀取參數(shù)

從工作表“設備”讀取參數(shù)賦給數(shù)組Mi；從工作表“加工子批”和“工藝流程”讀取參數(shù)賦給對象數(shù)組J；從工作表“工作制”讀取參數(shù)賦給數(shù)組Ws；按照假設條件8)，令i從1～m變化，為Mb(i).Ts的每行賦2個元素，bt和tln；從工作表“算法參數(shù)”讀取參數(shù)賦給表2中的變量。

表2 變量和數(shù)組Table2 Variables and arrays

2.4 編碼方式

采用“基于工序和設備的分段編碼”方式分別對工序和設備進行編碼。式(12)中，Chr(i).R為tpn×13的數(shù)組，第2、4列用于編碼，第1列為任務號，第3列為各加工子批的工序號，第5～13列用于解碼。第2列的自然數(shù)表示加工子批號，取值范圍為1～n，各自然數(shù)出現(xiàn)的次數(shù)與對應加工子批的工序數(shù)相等；第4列為各工序選擇的設備號，來自于該工序的可行加工設備號向量。式(12)表示加工子批1的第1道工序在設備4上加工(行2)，第2道工序在設備1上加工(行4)，加工子批2的第1道工序在設備2上加工(行1)，第2道工序在設備3上加工(行3)，依次類推。

2.5 種群初始化

對于個體Chr(i)的編碼獲取步驟如下。

第1步，為Chr(i).R的第1列賦以從1～tpn的任務號；第2步，令j從1～n變化，在Chr(i).R第2列依次隨機尋找J(j).pn個空元素，賦為j，同時將對應工序號賦給Chr(i).R的同行第3列；第3步，令j從1～n變化，對每個j，產(chǎn)生1～J(Chr(i).R(j, 2)).Pr(Chr(i).R(j, 3)).an的隨機自然數(shù)k，令J(Chr(i).R(j, 2)).Pr(Chr(i).R(j, 4)=J(Chr(i).R(j, 2)).Pr(Chr(i).R(j, 3)).Mn(k)。易知，通過上述方式獲得的個體是可行的。

令i從1～ps變化，分別對Chr(i).R賦值，完成種群初始化。

2.6 遺傳操作

遺傳操作包括交叉操作和變異操作。采用“基于工序和設備的分段”交叉和變異方式分別進行交叉和變異，并采用“遺傳算子改進策略”以保證交叉后子代個體可行[19-20]。

2.7 解碼操作

相對于傳統(tǒng)的柔性作業(yè)車間調度，本算法要同時考慮混合工作日歷、間隙擠壓、平順移動等因素，因此大大增加了解碼的難度。解碼操作的任務是對于個體Ch(i)，計算Ch(i).R的第5～13列值，它們依次對應工序的移動子批對應的加工時間(第5列)、調整時間(第6列)、加工時間(第7列)、調整成本(第8列)、加工成本(第9列)、調整開始時刻(第10列)、調整結束時刻(第11列)、加工開始時刻(第12列)和加工結束時刻(第13列)。

解碼操作的具體步驟如下。

1) 令R=ch(i).R, Ma=Mb。

2) 給第5～9列賦值。先獲取R(i, 4)在J(R(i, 2)).Pr(R(i, 3)).Mn數(shù)組中的索引號in, 再令R(i, 5)=J(R(i, 2)).Pr(R(i, 3)).Ct1(in)；令R(i, 6)=J(R(i, 2)).Pr(R(i, 3)).St (in)；令R(i, 7)=J(R(i, 2)).Pr(R(i, 3)).Ct (in)；R(i, 8)=J(R(i, 2)).Pr(R(i, 3)).St(in)×J(R(i, 2)).Pr(R(i, 3)).Ps(in)；R(i, 9)=J(R(i, 2)).Pr(R(i, 3)).Ct(in)×J(R(i, 2)).Pr(R(i, 3)).Pc (in)。

3) 給第10～13列賦值。令i從1～n變化，對于任務i，操作如下。

(1) 確定最早可能的調整開始時刻g。分3種情況處理。

① 若當前工序是加工子批R(i, 2)的第1道工序，令g=bt。

② 找到加工子批R(i, 2)的上一道工序所在的行號x，若R(x, 4)=R(i, 4)(圖3(a))，則 令g=max (t1,bt)，表示若當前工序與上道工序所用設備相同，則須上道工序加工結束后才能開始當前工序的調整工作。

③找到加工子批R(i, 2)的上一道工序所在的行號x，若R(x, 4)≠R(i, 4)(圖3(b))，則令g=max (t2,t3,bt)，t2取R(x, 13)逆 向 推 算[20]min (R(x, 5),R(i, 5))×(J(R(i, 2)).vn?1)+R(i, 6) 所得的時刻，t3取R(x, 12)正向推算[19](R(x, 5)所得的時刻。表示若當前工序與上道工序所用設備不相同，則按“平順移動原理”得到下一道工序最早可能的調整開始時刻。由于設備R(k, 4)與R(i, 4)所用的工作日歷有可能不同，導致t2有小于t3的可能，但上道工序的第一個移動子批未加工結束時，不可能開始下一道工序，故要取g=max (t2,t3, bt)。

圖3 理論最早可調整開始時刻Figure3 Earliest start time of adjustment in theory

(2) 從左向右，采用“間隙擠壓法”，根據(jù)Ma(R(i, 4)).Ts數(shù)組，依次尋找設備R(i, 4)的可行空閑時間段。如圖4所示，對于空閑時段k，取tb=max (g, Ma(R(i, 4)).Ts(2×k?1))，然后從tb正向推算[19]R(i, 6)+R(i, 7) 后得到加工結束時刻te，若te≤Ma(R(i,4)).Ts(2×k?1)，表明當前工序能安排在設備R(i, 4)的第k個空閑時間段，否則判斷設備的下一個空閑時間段，直到找到可行空閑時間段為止。Ma(R(i, 4)).Ts(2×k?1))、Ma(R(i, 4)).Ts(2×k))分別是設備R(i, 4)的第k個空閑時間段的下限和上限。

圖4 間隙擠壓法Figure4 Clearance extrusion method

(3)安排當前任務。設找到設備R(i, 4)的第k個空閑時間段為可行時間段，令R(i, 10)=tb，R(i, 11)、R(i, 12)取tb正向推算R(i, 6)所得時刻，R(i, 13)取te。

(4)更新設備R(i, 4)的時間狀態(tài)向量Ma(R(i, 4)).Ts。如圖5所示，調度開始時，Ma(R(i, 4)).Ts由bt、tln兩個元素組成，表示空閑時段為bt～tln(空閑時間段數(shù)frn=1)。若工序a被安排給設備R(i, 4)，需將 tsba(設備調整開始時刻)和 t cea(工序加工結束時刻)插入到bt～tln之 間，此時空閑時間段分別為b t～tsba和 tcea～tln(空閑時間段數(shù)frn=2)。進一步，若工序b也被安排給設備R(i, 4)(排在工序a之后)，此時，設備空閑時間段分別為 bt～tsba 、 tcea～tsbb 和 tceb～tln(空閑時間段數(shù)frn=3)?；诖?，Ma(R(i, 4)).Ts更新步驟如下。將Ma(R(i, 4)).Ts的長度增加2位，從設備R(i,4)的k空閑時段對應的第2個數(shù)據(jù)起，將其后的數(shù)據(jù)后移2位，空出2個空位，在這2個空位處分別填入待插入工序的設備調整開始時刻和加工結束時刻。

圖5 更新Ma(R(i,4)).TsFigure5 Updating Ma(R(i,4)).Ts

當所有任務安排完畢，令Ch(i).R=R，解碼結束。

2.8 計算目標值

在得到Ch(i).R的第5～13列之后，求出Ch(i).R第13列最大值與第10列最小值的差值賦給Chr(i).O(1)，將第8、9列之和賦給Chr(i).O(2)。

3 案例分析

某機械加工車間擁有18臺設備，某次生產(chǎn)任務涉及到產(chǎn)品1～4，其工藝流程如表3所示。為縮短生產(chǎn)周期，調度前將4種產(chǎn)品進行批量劃分，形成8個加工子批，各加工子批的參數(shù)如表4所示。設備所用工作制共有X、Y、Z 3種，其設置如表5所示。表中每2列代表一個工作制。以工作制X為例，A列是非周末但不運行的日期，B列是周末但要運行的日期。各設備的工作日歷如表6所示?，F(xiàn)要合理安排8個加工子批的生產(chǎn)作業(yè)計劃，達到生產(chǎn)周期和生產(chǎn)成本最小化。

表3 工藝流程Table3 Process flow

表4 加工子批Table4 Processing sub-batch

表5 工作制設置Table5 Settings of worksheet“work systems”

表6 設備工作日歷Table6 Work calendars of machines

取調度起始時刻bt =“2020/3/2 8:00”，ps=50，mg=100，cr =0.7，mr =0.3，mbs=2，tln=100 000(對應日期時間格式值4 637/11/26 0:00)，移動批量均取5，多次獨立運算，得到的Pareto解集接近且均勻。圖6是Pareto解集之一，其中，Pareto解A對應的調度表如表7所示，加工子批甘特圖如圖7所示，設備甘特圖如圖8所示。

圖6 Pareto解集Figure6 Pareto solution set

圖7中每一行代表一個加工子批的生產(chǎn)作業(yè)計劃。圖8中每一行代表一個設備的生產(chǎn)排程，黑色框代表設備調整起止時刻，白色框代表工序加工起止時刻。從圖7和表7可見，同一加工子批的部分相鄰兩道工序之間存在時間上的交叉現(xiàn)象，這正是平順移動的結果。平順移動有利于下道工序盡早開工，從而有效縮短生產(chǎn)周期。

圖7 Pareto解A對應的加工子批甘特圖Figure7 Gantt chart of processing sub-batch of Pareto solution A

圖8 Pareto解A對應的設備甘特圖Figure8 Gantt chart of the machines of Pareto solution A

由表7第10行可知，工序J4.4在設備1(200T)上加工，加工開始時刻為2020/3/6 14:30，加工結束時刻為2020/3/10 14:30，易知2020/3/6 14:30～2020/3/10 14:30的日歷時間為96 h，遠大于加工時間20 h。從表4可知，設備1采用“Z工作制”，每天運行10 h。從表5可知，按照“Z工作制”2020/3/7和2020/3/8為非運行日期，易知2020/3/6 14:30 ～ 2020/3/10 14:30的實際運行時間只有20 h，正好與工序的加工時間相等。同樣，由表7第16行知，工序J6.2在設備2(150T)上加工，其調整開始時刻為2020/3/7 21:18，結束時刻為2020/3/9 9:06，易知2020/3/7 21:18 ～ 2020/3/9 9:06的日歷時間為35.8 h，也遠遠大于其調整時間1.8 h。同理可得2020/3/7 21:18 ～ 2020/3/9 9:06的實際運行時間只有1.8 h，正好與設備的調整時間相等。綜上，算法在進行時間推算的時候考慮了設備的工作日歷，保證了所推算的設備調整起止時刻、工序加工起止時刻與實際情況吻合。

為了比較移動批量對生產(chǎn)效率的影響，保持其他參數(shù)不變，分別取如下兩種移動批量進行進化計算。1) 30-30-20-20-20-20-20-20；2) 移動批量10-10-10-10-10-10-10-10。將得到的Pareto解集與移動批量5-5-5-5-5-5-5-5的Pareto解集進行對比，如圖9所示。

圖9 移動批量變化對Pareto解集的影響Figure9 Impact to Pareto solution set by change of shift batch

由圖9可見，在一定范圍內，移動批量越小，Pareto解集整體左移，即生產(chǎn)周期越短。這是因為平順移動下，移動批量的減小可以使單個移動批次的加工時間縮短。按照平順移動原則，下道工序可以提前更多的時間開始進行設備調整，最終使得生產(chǎn)周期縮短。然而，隨著移動批量的減少，移動次數(shù)有可能會增加。

4 結論

針對調度設備采用混合工作日歷的現(xiàn)象，提出了一種混合工作日歷下批量生產(chǎn)柔性作業(yè)車間多目標調度方法，主要結論如下。

1) 算法能得到分布較均勻，收斂性較好的Pareto解集，能輔助調度人員快速找到滿意的調度方案。

2) 算法在安排工序的過程中，采用了時間推算技術，根據(jù)各設備的工作日歷推算設備調整起止時刻和工序加工起止時刻，保證了調度方案的可行性。

3) 加工批量不變，減小移動批量，通過平順移動生產(chǎn)周期能得到縮短，提高了調度方案的質量。