考慮產(chǎn)品型號的作業(yè)車間調(diào)度

郝慧敏， 孫國華 ， 王改麗

(1.新疆工程學(xué)院 經(jīng)濟管理學(xué)院， 新疆 烏魯木齊 830000；2.山東財經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院， 山東 濟南 250014)

制造企業(yè)的數(shù)字化轉(zhuǎn)型升級是一個漸進式的發(fā)展演變過程，重點是把有限的資源集中于產(chǎn)品前端的生產(chǎn)和后端的服務(wù)中，實現(xiàn)產(chǎn)品從“規(guī)模定制”向高度“個性化定制”轉(zhuǎn)變。面對消費者需求小規(guī)模、多樣性的特點，制造企業(yè)從提高生產(chǎn)效率和客戶滿意度、降低生產(chǎn)成本等角度優(yōu)化車間調(diào)度方案，提升綜合競爭力就顯得尤為重要，這也一直是制造領(lǐng)域和控制科學(xué)研究的熱點。

關(guān)于車間調(diào)度問題，Johnson[1]在1954年首先提出，自此車間調(diào)度方向的研究逐漸增多。在求解車間調(diào)度問題算法方面，小規(guī)模調(diào)度案例可以采用分支定界法、數(shù)學(xué)規(guī)劃法和枚舉法等精確算法，但實際生產(chǎn)過程中算例規(guī)模的擴大導(dǎo)致可行解以指數(shù)形式增大，因此，越來越多的智能算法應(yīng)運而生，例如，Zhao等[2]設(shè)計出并行順序移動和可變異概率的改進遺傳算法；Gong等[3]提出一種混合進化算法用于研究車間調(diào)度問題中工人靈活性和能耗對生產(chǎn)成本的影響；李寶帥等[4]將深度強化學(xué)習(xí)算法用于求解作業(yè)車間調(diào)度問題；林劍等[5]提出一種基于離散Jaya算法優(yōu)化線纜的生產(chǎn)調(diào)度，并通過仿真驗證算法的有效性，從而提高傳統(tǒng)電纜行業(yè)的生產(chǎn)與管理效率；為優(yōu)化動態(tài)單機調(diào)度問題，Jun等[6]設(shè)計出一種基于決策樹的數(shù)據(jù)挖掘方法；于蒙等[7]考慮將遺傳算法與粒子群算法結(jié)合用于求解車間調(diào)度問題。

在求解車間調(diào)度問題時考慮的因素及目標(biāo)函數(shù)構(gòu)建方面，任麗[8]通過總結(jié)線纜生產(chǎn)車間調(diào)度問題的特點，構(gòu)建了考慮設(shè)備選擇和工件順序2個關(guān)鍵因素的數(shù)學(xué)模型，并采用遺傳算法求解；Senyigit等[9]考慮了等待時間、生產(chǎn)周期和生產(chǎn)成本3種因素；SANCHEZ-HERREAR等[10]考慮了生產(chǎn)延遲的因素，設(shè)計相應(yīng)的局部迭代和貪婪隨機自適應(yīng)算法；針對車間生產(chǎn)效率低的問題，趙澤鈺等[11]找出影響生產(chǎn)的因子和生產(chǎn)過程中的瓶頸，為生產(chǎn)線分配設(shè)備提供依據(jù)；SOTSKOV等[12]構(gòu)建最小化最大完工時間的目標(biāo)函數(shù)，求解2臺并行設(shè)備的調(diào)度方案；陳魁等[13]采用粒子群算法求解運輸時間最少的作業(yè)車間調(diào)度問題；劉玉婷[14]考慮了低碳環(huán)保的目標(biāo)，對綠色柔性作業(yè)車間調(diào)度問題展開了研究。

從以上文獻(xiàn)可以看出，研究車間調(diào)度問題時對產(chǎn)品的型號問題關(guān)注較少，通常將產(chǎn)品的計劃生產(chǎn)數(shù)量看作工件的數(shù)量，如果當(dāng)所有型號產(chǎn)品的計劃生產(chǎn)量都較大時，工件總數(shù)的成倍增長使得遺傳算法的染色體長度成倍增加，那么控制算法的運行時間將成為制定調(diào)度方案的難點。其次，忽略了同一類型不同規(guī)格型號產(chǎn)品所用的加工設(shè)備存在的相似性和產(chǎn)品的生產(chǎn)量差異，不考慮將性能相似的設(shè)備合并后根據(jù)生產(chǎn)量進行分配，致使調(diào)度方案的設(shè)計不能隨著產(chǎn)品生產(chǎn)量的變化而靈活改變。如果當(dāng)不同型號產(chǎn)品生產(chǎn)量相差較大時，生產(chǎn)量較小的設(shè)備在完成加工任務(wù)后就處于閑置狀態(tài)，導(dǎo)致車間中性能相似的設(shè)備利用率存在較大差別，延長了產(chǎn)品的完工時間。更為重要的一點，制定的調(diào)度方案未考慮企業(yè)在實際生產(chǎn)過程中的排班問題；因此在縮短產(chǎn)品完工時間的同時也需要減少企業(yè)生產(chǎn)線操作人員排班的個數(shù)，最終才能有效降低企業(yè)的生產(chǎn)費用。

課題組結(jié)合企業(yè)的實際生產(chǎn)情況，針對以往調(diào)度方案的設(shè)計是基于產(chǎn)品的數(shù)量而忽略了產(chǎn)品的型號，以及不能根據(jù)產(chǎn)品的生產(chǎn)量合理分配加工設(shè)備，以減少排班次數(shù)的2個問題，構(gòu)建以產(chǎn)品型號為基礎(chǔ)的多目標(biāo)數(shù)學(xué)規(guī)劃模型，合并性能相似的設(shè)備，并通過遺傳算法求解出既考慮產(chǎn)品型號又考慮生產(chǎn)量差異這2個因素的整體調(diào)度方案，達(dá)到均衡設(shè)備利用率，縮短產(chǎn)品交付周期和降低企業(yè)生產(chǎn)費用的效果。

1 問題描述

某一類型的產(chǎn)品有m種規(guī)格型號，加工這些產(chǎn)品的設(shè)備有(x+y+…+z)臺，每種規(guī)格型號的產(chǎn)品有u道相同的工序和不同的生產(chǎn)數(shù)量Q，每道工序可在一臺或多臺設(shè)備上進行加工，不同規(guī)格型號產(chǎn)品的相同工序在不同的設(shè)備上花費的加工時間不同，調(diào)度方案原理如圖1所示。

圖1 調(diào)度方案設(shè)計原理

圖中，1-1表示可用于加工第1道工序的第1臺設(shè)備，2-1表示可用于加工第2道工序的第1臺設(shè)備；每道工序的并行可加工設(shè)備確定好后，為每臺設(shè)備分配需要加工的產(chǎn)品型號，第2行第1個數(shù)字2表示為加工第1道工序的第1臺設(shè)備分配規(guī)格型號為2的產(chǎn)品進行加工，以此類推，為每道工序的每臺設(shè)備分配相應(yīng)的產(chǎn)品進行加工。

2 模型建立

作業(yè)車間調(diào)度方案的設(shè)計為符合企業(yè)的發(fā)展目標(biāo)，構(gòu)建的數(shù)學(xué)模型包括2個目標(biāo)函數(shù)：①單件產(chǎn)品的最大加工時間最少；②按計劃數(shù)量生產(chǎn)加工完成所有產(chǎn)品的總時間最短。模型假設(shè)如下：

1) 每種類型產(chǎn)品之間沒有依賴關(guān)系，相互獨立存在；

2) 產(chǎn)品在加工過程中不考慮設(shè)備故障等突發(fā)情況，且產(chǎn)品在加工完某道工序轉(zhuǎn)運至下一道工序加工期間花費的轉(zhuǎn)運時間忽略不計；

3) 產(chǎn)品加工階段每道工序之間的暫存區(qū)容量較大，且產(chǎn)品在加工過程中，配置的設(shè)備只有在這件產(chǎn)品對應(yīng)的工序加工完成后才可以加工下一件產(chǎn)品或停止加工。

構(gòu)建模型用到的參數(shù)變量如表1。

表1 模型參數(shù)含義及說明

①目標(biāo)函數(shù)

(1)

(2)

式(1)為第1個目標(biāo)函數(shù)，表示單件產(chǎn)品的最大加工時間最少；式(2)為第2個目標(biāo)函數(shù)式，表示所有產(chǎn)品按計劃生產(chǎn)數(shù)量加工完成花費的總時間最短。

②約束條件

(3)

(4)

(5)

(6)

(7)

(8)

sjkh≥0,cjkh≥0;j=1,2,3，L,m;h=1,2,L,u。

(9)

其中，式(3)表示一共需要加工的j種規(guī)格型號產(chǎn)品的數(shù)量等于計劃生產(chǎn)總量；式(4)表示每種規(guī)格型號產(chǎn)品中每個產(chǎn)品的每道工序至少有1臺設(shè)備加工；式(5)和(6)表示每種規(guī)格型號產(chǎn)品其中每個產(chǎn)品每道工序的加工順序約束；式(7)和(8)表示同一設(shè)備同一時刻只能加工1個產(chǎn)品的1道工序；式(9)表示加工時間為正數(shù)。

3 算法設(shè)計

遺傳算法是一種常用的人工智能算法，該算法具有較強的穩(wěn)定性和搜索能力，在應(yīng)用過程中都能取得較好的計算效果，課題組也采用這種算法求解。

雖然不同規(guī)格型號產(chǎn)品的計劃生產(chǎn)數(shù)量比較多，但只要是同一種規(guī)格型號的產(chǎn)品，在產(chǎn)品的規(guī)格型號數(shù)量不發(fā)生變化的情況下，得到的最優(yōu)解中規(guī)格型號相同的產(chǎn)品單件加工時間不會發(fā)生變化，即規(guī)格型號相同的產(chǎn)品相同工序選擇的加工設(shè)備不會發(fā)生變化。只有當(dāng)產(chǎn)品的規(guī)格型號數(shù)量發(fā)生變化時，例如某種型號的產(chǎn)品加工的數(shù)量已經(jīng)達(dá)到計劃數(shù)量后，其余產(chǎn)品的加工時間才有可能發(fā)生變化，因此，課題組在設(shè)計遺傳算法時，將同種規(guī)格型號的產(chǎn)品看作一個整體，從而簡化算法的編碼方式。此外，單件產(chǎn)品最大加工時間最少并不一定保證總加工時間最短，而采用2層遺傳算法可以更好地滿足2個目標(biāo)函數(shù)。

3.1 染色體編碼

課題組采用實數(shù)的編碼方式，染色體編碼以工序數(shù)為基礎(chǔ)，將需要經(jīng)過的加工工序數(shù)和可以加工每道工序的所有設(shè)備并行排列，每個基因表示對應(yīng)工序性能相似的設(shè)備選擇加工的產(chǎn)品，當(dāng)產(chǎn)品的型號數(shù)量和對應(yīng)工序的可選加工設(shè)備數(shù)相同時，一臺設(shè)備對應(yīng)一種型號的產(chǎn)品；當(dāng)產(chǎn)品的型號數(shù)大于對應(yīng)工序可選加工設(shè)備數(shù)時，增加虛擬設(shè)備，虛擬設(shè)備的加工情況和現(xiàn)有設(shè)備相同，增加虛擬設(shè)備的數(shù)量等于未分配加工設(shè)備的產(chǎn)品型號數(shù)；當(dāng)產(chǎn)品的型號數(shù)量小于對應(yīng)工序的可選加工設(shè)備數(shù)時，未分配產(chǎn)品的加工設(shè)備可重復(fù)選擇產(chǎn)品型號，相當(dāng)于增加虛擬產(chǎn)品，虛擬產(chǎn)品的規(guī)格型號和現(xiàn)有的某產(chǎn)品相同，染色體編碼如圖2所示。

圖2 染色體編碼

染色體的長度取決于產(chǎn)品的型號數(shù)量和每道工序可以選擇的加工設(shè)備數(shù)量，這里將染色體按照工序數(shù)分為3段：M1-1表示可以加工第1道工序的第1臺設(shè)備，M2-1表示可以加工第2道工序的第1臺設(shè)備，VM2-3表示第2道工序的第3臺設(shè)備為虛擬設(shè)備，基因上不同的數(shù)字表示不同型號的產(chǎn)品。因為可以加工第1道工序的設(shè)備數(shù)量和產(chǎn)品的型號數(shù)量相等，所以每臺設(shè)備剛好對應(yīng)一種型號的產(chǎn)品；加工第2道工序的設(shè)備有2臺，而產(chǎn)品有3種型號，因此增加1臺虛擬設(shè)備，理解為前2臺設(shè)備中的其中1臺設(shè)備在加工完一定數(shù)量的產(chǎn)品A或者產(chǎn)品B后再加工產(chǎn)品C，2臺設(shè)備中最短的加工時間默認(rèn)為產(chǎn)品C的加工時間；加工第3道工序的設(shè)備比產(chǎn)品的型號數(shù)量多，多出的設(shè)備可重復(fù)選擇加工的產(chǎn)品。

3.2 適應(yīng)度函數(shù)

第1個目標(biāo)函數(shù)是每種規(guī)格型號產(chǎn)品的單件最大加工時間最少，對應(yīng)的適應(yīng)度函數(shù)為：

F=1/f1。

第2個目標(biāo)函數(shù)是所有產(chǎn)品按計劃數(shù)量加工需要的總完工時間最短，同時，為避免第2個目標(biāo)函數(shù)對應(yīng)的解中出現(xiàn)每種規(guī)格型號產(chǎn)品的單件加工時間大于第1個目標(biāo)函數(shù)求解的結(jié)果，因此加入1個無限大的正數(shù)L和變量d，公式如下：

F=1/(f2+d×L)。

變量d的取值可以為0或者1，L為1個足夠大的正數(shù)，如果染色體表示的解中出現(xiàn)了單件加工時間大于第1個目標(biāo)函數(shù)即第1層遺傳算法已經(jīng)求解的結(jié)果，則通過變量d和L排除該解成為最終最優(yōu)解的可能。

3.3 選擇操作

選擇操作采用輪盤賭策略，個體被選中的概率與適應(yīng)度值相聯(lián)系，若染色體i的適應(yīng)度為Fi，染色體總數(shù)為N，則該染色體被選擇的概率Pi為：

3.4 交叉操作

交叉操作的目的主要是生成新的染色體，考慮到車間調(diào)度問題設(shè)備選擇加工產(chǎn)品的特性，染色體分段交叉的操作步驟如下：

1) 將每條染色體根據(jù)加工的工序數(shù)分成3段，每段的交叉概率設(shè)置為相同的參數(shù)，首先隨機生成幾個[0，1]的實數(shù)，這幾個數(shù)可相同也可以不同，當(dāng)每段的交叉概率大于對應(yīng)生成的隨機數(shù)時，從父代群體中選擇2條染色體。

2) 隨機生成與工序數(shù)相同的3對整數(shù)，每對整數(shù)的范圍與每段需要選擇加工的產(chǎn)品規(guī)格型號數(shù)相同，本例中第1對整數(shù)范圍在[1，3]，第2對整數(shù)范圍在[4，6]，以此類推，第3對整數(shù)范圍在[7，10]，生成的整數(shù)分別對應(yīng)2條染色體中的基因位置。

3) 對調(diào)父代中對應(yīng)區(qū)間的基因，如果生成的解不符合要求，則保留新生成的子代中位于交叉區(qū)間內(nèi)的基因，將區(qū)間外的基因進行調(diào)整，依次生成符合要求的子代染色體，如圖3所示。

圖3 染色體交叉

按照這樣的交叉策略可以防止父代染色體經(jīng)過1次交叉發(fā)生改變的基因數(shù)過多，在實際問題中，企業(yè)作業(yè)車間的設(shè)備以及產(chǎn)品的規(guī)格型號數(shù)量肯定相對較大，構(gòu)成的染色體也較長，如果2條染色體按照2點交叉，很有可能導(dǎo)致優(yōu)秀的父代染色體在遺傳的過程中變化較大，減慢遺傳算法的收斂速度，根據(jù)工序數(shù)分段2點交叉較好地彌補了這一缺點。

3.5 變異操作

變異操作是通過改變?nèi)旧w中的個別基因，產(chǎn)生新個體。課題組采用互換方式完成變異操作，即隨機選擇染色體的其中1段，以變異概率交換1段中2個不同位置的基因，確保染色體的多樣性。

4 算例分析

4.1 算例背景

為驗證模型和算法的有效性，引用一家從事汽車儀表制造行業(yè)的某企業(yè)實際數(shù)據(jù)，該企業(yè)作業(yè)車間有15條生產(chǎn)線，其中9條生產(chǎn)線各生產(chǎn)加工一種規(guī)格型號的組合儀表，將這9種型號的組合儀表分別用產(chǎn)品A，產(chǎn)品B，…，產(chǎn)品I表示，產(chǎn)品某天計劃生產(chǎn)的數(shù)量如表2所示，此時產(chǎn)品的單件最大加工時間為308 s。雖然儀表的規(guī)格型號不同，但加工過程中包含相同的8道工序，且相同工序在加工過程中使用的設(shè)備沒有實質(zhì)性的區(qū)別，所以每道工序的加工設(shè)備有9臺。該企業(yè)的生產(chǎn)線每天安排2個班次，每個班次的工作時間為7 h，要求根據(jù)目標(biāo)函數(shù)尋找每種型號產(chǎn)品每道工序配置的加工設(shè)備。

表2 產(chǎn)品計劃生產(chǎn)量

4.2 算例求解

首先，通過第1層遺傳算法尋找9種不同型號的產(chǎn)品每道工序配置的加工設(shè)備；其次，在滿足第1層遺傳算法求解結(jié)果的情況下，通過第2層遺傳算法尋找9種型號的產(chǎn)品按計劃完成加工任務(wù)，花費總時間最少的調(diào)度方案；最后，考慮減少排班個數(shù)以降低企業(yè)的生產(chǎn)費用，從而獲得整體最優(yōu)的調(diào)度方案。

2層遺傳算法的設(shè)計原理和參數(shù)相同，種群規(guī)模設(shè)為100，交叉概率Pc為0.9，變異概率Pm為0.05，并加入精英染色體保留策略，保證算法的收斂速度，種群的保留概率設(shè)置為0.9。實驗環(huán)境為Windows10 系統(tǒng)，Intel(R)Core(TM)i5-7300HQ CPU@2.5 GHz，采用MATLAB 2019a軟件求解該企業(yè)的車間調(diào)度問題，第1層遺傳算法的求解結(jié)果是產(chǎn)品D用時270 s，說明9種產(chǎn)品的單件最大加工時間最少為270 s，迭代次數(shù)如圖4所示。

圖4 遺傳算法迭代圖

當(dāng)算法迭代至178次時，加工時間趨于穩(wěn)定，求解單件最大加工時間最少的調(diào)度方案結(jié)果如表3所示。

表3 單件最大加工時間最少的結(jié)果

第1層遺傳算法無法保證除了其中單件加工時間最大的產(chǎn)品D，其余產(chǎn)品的單件加工時間也為最優(yōu)，因此加入第2層遺傳算法，該層算法需要在第1層算法求解結(jié)果的基礎(chǔ)上進行設(shè)計，將已經(jīng)求解出的產(chǎn)品D經(jīng)過8道工序加工配置的設(shè)備固定，每道工序剩余的設(shè)備可以選擇其它型號的產(chǎn)品加工，第2層算法的其余操作與第1層相似，求解的調(diào)度方案如表4所示。

表4 基于2層遺傳算法求解的調(diào)度方案

表中每一行可以解釋為每種型號產(chǎn)品的8道工序配置的加工設(shè)備，以及在這些設(shè)備上單件產(chǎn)品花費的加工時間和按照生產(chǎn)量每種型號產(chǎn)品的完工時間。以第1行為例，A1-M1-1表示產(chǎn)品A的第1道工序在編號為M1-1的設(shè)備上加工，然后依次在相應(yīng)的設(shè)備上完成8道工序的生產(chǎn)加工，且加工1件產(chǎn)品A的時間為167 s，加工246件產(chǎn)品A需要11.4 h。

4.3 最終調(diào)度方案

在解決實際調(diào)度問題時，只考慮單件產(chǎn)品最大加工時間最少和總完工時間最短這2個因素是不夠充分的，還需要考慮企業(yè)安排工人的班次。某企業(yè)1個班次的工作時間為7 h，不論工作時間是否達(dá)到7 h，均按照1個班次的費用計算工人工資，所以接下來設(shè)計的最終調(diào)度方案主要是減少班次，或者在班次數(shù)量已經(jīng)不能減少的情況下，盡量減少并行班次的工作時間。例如當(dāng)某一種型號的產(chǎn)品生產(chǎn)加工數(shù)量達(dá)到計劃生產(chǎn)量時，加工該產(chǎn)品的設(shè)備繼續(xù)用來加工其它還未加工完的產(chǎn)品，此舉既減少排班數(shù)，又縮短了產(chǎn)品完工時間，確保產(chǎn)品最終可以按時交付。產(chǎn)品加工最終調(diào)度方案如圖5所示。

圖5 產(chǎn)品加工調(diào)度方案

改進后的調(diào)度方案將產(chǎn)品的單件最大加工時間從308 s降至270 s，并且每種規(guī)格型號的產(chǎn)品按計劃數(shù)量生產(chǎn)加工需要的總時間從13.75 h降至13.40 h，提高了班次內(nèi)設(shè)備的利用率。另外，此方案將初始方案安排的加班次數(shù)由4個減少至3個，從而降低了企業(yè)的生產(chǎn)費用。

5 結(jié)語

課題組研究了加工產(chǎn)品總數(shù)較多，且加工產(chǎn)品型號相似的作業(yè)車間調(diào)度問題，通過建立單件最大加工時間最少以及所有產(chǎn)品按計劃數(shù)量加工需要的總完工時間最短的多目標(biāo)數(shù)學(xué)規(guī)劃模型，采用2層遺傳算法求解，并根據(jù)調(diào)度問題中設(shè)備選擇加工的產(chǎn)品型號和產(chǎn)品經(jīng)過的加工工序這2大特點，設(shè)計算法的編碼、分段多點交叉和變異操作，縮短染色體的基因個數(shù)，盡可能多的保留優(yōu)秀染色體的基因，加快算法收斂速度；同時，為更加符合企業(yè)的實際生產(chǎn)情況，提出減少企業(yè)排班數(shù)量的調(diào)度方案，并結(jié)合案例，驗證算法的有效性，最終達(dá)到了均衡性能相似設(shè)備的利用率以及縮短總完工時間，降低企業(yè)生產(chǎn)費用的目的。在后續(xù)研究過程中，擬考慮產(chǎn)品在加工完某道工序轉(zhuǎn)運至下一道工序加工期間花費的轉(zhuǎn)運時間和設(shè)備故障等突發(fā)事件對調(diào)度方案的影響，進一步提高研究的全面性。