徐 璜

（安徽理工大學(xué)經(jīng)濟(jì)與管理學(xué)院，安徽 淮南 232000）

0 引言

1950年起，發(fā)達(dá)國家對生產(chǎn)效率提出了新需求，有學(xué)者開始研究作業(yè)車間調(diào)度問題（Job-Shop Scheduling Problem，JSP）。國際生產(chǎn)學(xué)會（CIRP）根據(jù)生產(chǎn)型國家對現(xiàn)代制造系統(tǒng)進(jìn)行研究，總結(jié)了多達(dá)34種先進(jìn)制造模式。這些模式為實(shí)現(xiàn)制造企業(yè)的現(xiàn)代化轉(zhuǎn)型和發(fā)展帶來了十分重要的理論價(jià)值和現(xiàn)實(shí)意義[1]。

20世紀(jì)末，我國制造業(yè)開始崛起，產(chǎn)業(yè)進(jìn)入高速發(fā)展時(shí)期。制造業(yè)開始成為國民經(jīng)濟(jì)向好發(fā)展的重要力量[2]。隨著制造業(yè)發(fā)展及物流運(yùn)輸系統(tǒng)的完善，國內(nèi)制造業(yè)產(chǎn)業(yè)集聚程度不斷提高[3]。隨后，經(jīng)濟(jì)全球化，制造業(yè)競爭加大，給我國制造業(yè)帶來沖擊和挑戰(zhàn)。這就要求企業(yè)降低生產(chǎn)制造成本、保證產(chǎn)品長期品質(zhì)、適應(yīng)市場和提供高附加服務(wù)，由此車間調(diào)度問題研究在國內(nèi)進(jìn)入新階段。

該文基于JSP的優(yōu)化策略幫助Z企業(yè)改進(jìn)作業(yè)車間調(diào)度問題，提高產(chǎn)能，增強(qiáng)公司綜合競爭力。

1 Z企業(yè)作業(yè)車間調(diào)度現(xiàn)狀

Z企業(yè)是生產(chǎn)高低壓成套配電設(shè)備的國企，近年來，隨著公司產(chǎn)能擴(kuò)張，作業(yè)車間沿用的傳統(tǒng)管理模式難以滿足需要。作業(yè)車間陸續(xù)出現(xiàn)產(chǎn)能積壓、訂單順序紊亂以及加急貨物難以優(yōu)先生產(chǎn)等問題。其中，制定生產(chǎn)調(diào)度方案是影響優(yōu)化加工時(shí)間、提高積壓庫存流轉(zhuǎn)以及盡可能滿足產(chǎn)品交貨期的重要因素[4]。同時(shí)，Z企業(yè)管理層每過幾年會有不同程度的人員流動，這種流動嚴(yán)重影響了生產(chǎn)管理工作效率，因此需要弱化崗位經(jīng)驗(yàn)對崗位的影響。

為解決該問題，公司試行了ERP+MES計(jì)算機(jī)輔助軟件，同時(shí)引入更多新的管理策略，雖然取得了一定成效，但是仍無法解決公司日益擴(kuò)大規(guī)模對產(chǎn)能的要求、作業(yè)車間調(diào)度管理力度不足之間的矛盾和非長期從事該崗位的新管理人員帶來的管理效率降低的問題。因此，研究基于人工智能算法的作業(yè)車間調(diào)度問題，為Z企業(yè)提供生產(chǎn)管理解決方案非常必要。

2 配電箱作業(yè)車間調(diào)度問題的數(shù)學(xué)模型

Z企業(yè)長期使用的作業(yè)車間調(diào)度數(shù)學(xué)模型可歸于基于啟發(fā)式算法的優(yōu)先分派規(guī)則法（Priority Dispatch Rulers，PDR）。該模型在實(shí)際應(yīng)用中常用的規(guī)則有RS、SPT、LPT、EDD和FCFS等。EDD是Z企業(yè)實(shí)際車間調(diào)度中擁有最高優(yōu)先級的規(guī)則，即當(dāng)出現(xiàn)加急訂單時(shí)，作業(yè)車間管理者會安排無條件優(yōu)先加工該加急訂單；在無加急訂單的情況下，作業(yè)車間管理者使用FCFS法則安排加工生產(chǎn)，即先到的訂單先安排生產(chǎn)；同時(shí)，根據(jù)實(shí)際觀察，在同等情況出現(xiàn)多個(gè)可選作業(yè)班組時(shí)一般會使用RS規(guī)則，即隨機(jī)選擇；作業(yè)班組/作業(yè)人員在面對多個(gè)訂單時(shí)常常自發(fā)使用SPT法則，即最快能加工完成的優(yōu)先加工，以在當(dāng)前計(jì)件模式下謀求最高收益。

Z企業(yè)為解決作業(yè)車間調(diào)度問題引入ERP系統(tǒng)后，同時(shí)使用了ERP系統(tǒng)中的生產(chǎn)調(diào)度輔助工具，形成新的調(diào)度方法（以下簡稱ERP輔助法）。ERP輔助法融合了SPT法則、EDD法則、MOR法則和FCFS法則形成的新法則，可部分提高配電箱作業(yè)車間調(diào)度效率。

2.1 變量描述

n為工件總數(shù)，m為機(jī)器總數(shù)，Cj為每個(gè)工件的完工時(shí)間，Cmax為最大完工時(shí)間，Ojh為第j個(gè)工件的第h道工序，Mijh為第j個(gè)工件的第h道工序在機(jī)器“i”上加工，Pijh為第j個(gè)工件的第h道工序在機(jī)器“i”上加工的時(shí)間，Cjh為第j個(gè)工件的第h道工序完工時(shí)間。

2.2 配電箱作業(yè)車間調(diào)度問題的約束條件和數(shù)學(xué)描述

配電箱作業(yè)車間調(diào)度問題的約束條件和數(shù)學(xué)描述如公式（1）所示。

Cmax表述的是在作業(yè)車間內(nèi)制造加工全部的工件所需要花費(fèi)的最多時(shí)間，即所有工件工序數(shù)都為h，工件總數(shù)為j，所有配電箱的所有工序在機(jī)器上加工的時(shí)間都不為0，且每道工序都需要經(jīng)過i臺機(jī)器。

j臺不同的配電箱在i臺設(shè)備上加工，要滿足工序的約束條件，即加工每個(gè)配電箱需要經(jīng)過h道工序，因?yàn)楣に囈?，所以配電箱有自己的工序先后順序，每道工序可選用的加工機(jī)器不止1臺，根據(jù)機(jī)器的不同工序所用時(shí)長也不同。工序的約束條件如下：1） 任一時(shí)刻，一道工序能且只能在唯一一臺機(jī)器上加工，且工序加工作業(yè)不能中斷。2） 任一時(shí)刻，1臺機(jī)器上只能加工一道工序，不考慮工序間轉(zhuǎn)運(yùn)時(shí)間。3） 同一工件的工序先后順序是固定的，而不同的工件間加工工序無先后順序約束。4） 不考慮作業(yè)現(xiàn)場隨機(jī)性因素。

配電箱作業(yè)車間調(diào)度問題調(diào)度目標(biāo)是明確每臺機(jī)器上工序加工順序和工序?qū)?yīng)的開工時(shí)間，使Cmax盡可能小。

3 基于遺傳算法的作業(yè)車間調(diào)度優(yōu)化

遺傳算法屬于啟發(fā)式算法，最早是從生物遺傳學(xué)和“物競天擇，適者生存”等生物學(xué)概念獲得啟發(fā)的，模型的解就是遺傳算法中的“染色體”，通過遺傳過程中自然選擇、交叉以及基因變異等現(xiàn)象來提高個(gè)體存活率，經(jīng)過一代代的傳遞，逐步發(fā)現(xiàn)最優(yōu)的子代（解）的過程。1954年，學(xué)者Johnson針對2臺機(jī)器有序加工的流水車間調(diào)度的問題進(jìn)行了研究，隨后各國的學(xué)者在對車間調(diào)度問題進(jìn)行了后續(xù)的相關(guān)研究，也取得了比較顯著的研究成果[5]。車間調(diào)度問題衍生出流水線車間調(diào)度問題、柔性作業(yè)車間調(diào)度問題等，但都是以經(jīng)典作業(yè)車間調(diào)度問題（Job-Shop Scheduling Problem，JSP）為基礎(chǔ)進(jìn)行研究的。在經(jīng)典作業(yè)車間調(diào)度問題中，每件工件的每道工序僅能在1臺機(jī)器上加工，且僅能加工1次，同時(shí)加工時(shí)間t是一個(gè)固定值[6]。

當(dāng)使用遺傳算法求解時(shí)，從1組隨機(jī)數(shù)中產(chǎn)生的初代種群開始進(jìn)行演化。產(chǎn)生的每個(gè)個(gè)體（individual）都表示模型的1個(gè)解，稱為染色體（chromosome）[7]。種群通過不斷地演化和進(jìn)化過程，每次都會產(chǎn)生新的一代（generation）。在模擬自然界對物種進(jìn)行篩選的自然法則啟發(fā)下，使用適應(yīng)度函數(shù)（fitness function）或目標(biāo)函數(shù)（objective function）對每個(gè)個(gè)體進(jìn)行評價(jià)，適應(yīng)度值高的個(gè)體生存下來的概率高，也就意味著問題的這個(gè)解被選中的概率高。演化產(chǎn)生出的下一代被稱為子代（offspring）。上一代經(jīng)過選擇（selection）、交叉（crossover）以及變異（mutation）等操作產(chǎn)生子代。遺傳算法共有5個(gè)基本要素，首先，是編碼和解碼。其次，是對種群初始化的方法。再次，是適應(yīng)度函數(shù)的選擇。從次，是選擇、交叉和變異等遺傳算子。最后，是種群的規(guī)模、交叉變異等算子的概率設(shè)置。

設(shè)定D為種群的規(guī)模，t為當(dāng)前一代，D（t）和C（t）代表第t代的父代和子代，遺傳算法的步驟如下。

步驟1：初始化產(chǎn)生初始種群D（t）t=0。

步驟2：評價(jià)種群D（t），計(jì)算每個(gè)個(gè)體的適應(yīng)度值。

步驟3：判斷是否滿足終止條件，不滿足就轉(zhuǎn)步驟4，滿足就直接輸出結(jié)果。

步驟4 ：選擇、交叉和變異3個(gè)遺傳算子產(chǎn)生子代C（t）。

步驟5：D（t）=C（t）轉(zhuǎn)步驟2t=t+1。

車間調(diào)度問題是通過優(yōu)化在每個(gè)機(jī)器上工序加工順序和對應(yīng)工序開工時(shí)間，使Cmax盡可能取較小值。

3.1 約束條件

約束條件如公式（2）所示。

式中：i=1，2，3，…，m；j=1，2，3，…，n；h=1，2，3，…h(huán)j；Sjh為第j個(gè)工件的第h道工序加工開始的時(shí)間；Xijh為第j個(gè)工件的第h道工序在機(jī)器i上加工；Pijh為第j個(gè)工件的第h道工序在機(jī)器i上加工的時(shí)間；Cjh為第j個(gè)工件的第h道工序完工時(shí)間。

第j個(gè)工件的第h道工序完工時(shí)間Cjh如公式（3）所示。

Cjh≤S（h+1）（3）式中：S（h+1）為第j個(gè)工件的第h+1道工序開始時(shí)間（j=1，2，3，…，n；h=1，2，3，…，hj-1）。

第j個(gè)工件的第h道工序完工時(shí)間小于加工總時(shí)間，如公式（4）所示。

式中：j=1，2，3，…，n；Cmax為最大完工時(shí)間。

同一時(shí)間、同一道工序僅能在1臺設(shè)備上加工，如公式（5）所示。

工件加工時(shí)間必須是正數(shù)，如公式（6）所示。

式中：h=1，2，3，…，hj；j=1，2，3，…，n。

3.2 染色體編碼方式

染色體編碼方法是遺傳算法首先需要解決的問題。求解JSP問題的常見編碼方式有MSOS編碼、表格編碼、A/B串編碼、三元組編碼和矩陣編碼等。該文選用MSOS編碼方式，如圖1所示。

圖1 基于MSOS的染色體編碼

其中，Qab為工件a的第b道工序，a={1，4}，b={1，3}；Mx為工序可選設(shè)備中的第x臺，x={1，6}；Jx為第x件工件，x={1，2}。

按機(jī)器選擇的機(jī)器編碼：每個(gè)工件的每道工序按順序排列，例如第一個(gè)工件的第一道工序?yàn)镺11，第j個(gè)工件的h道工序?yàn)镺jh。

按這個(gè)順序排列：O11，O12，O21，O22，O23……。每個(gè)框代表每個(gè)工序所選擇的機(jī)器，例如第一個(gè)框代表O11選擇的機(jī)器?？蚶锏臄?shù)字則代表該道工序能夠選擇的機(jī)器里的第幾個(gè)機(jī)器。例如O11能夠加工的機(jī)器為M1、M2、M3、M4、M5和M6，4代表為這6臺機(jī)器里的第四臺機(jī)器，為M4。O21工序能夠加工的機(jī)器為M2和M4，1則代表這2臺機(jī)器里的第二臺機(jī)器，為M2。以此生成MS這邊的染色體。

按工序排列的機(jī)器編碼：數(shù)字出現(xiàn)的順序就是工件的順序，數(shù)字幾就是第幾道工序。第一次出現(xiàn)數(shù)字“1”代表第一個(gè)工件的第一道工序，第二次出現(xiàn)數(shù)字“1”代表第一個(gè)工件的第二道工序，數(shù)字“2”第3次出現(xiàn)為第二個(gè)工件的第三道工序。

3.3 遺傳算子

3.3.1 選擇

選擇算子的第一步是先確定1個(gè)數(shù)組，數(shù)組的位數(shù)就是機(jī)器的總數(shù)量，數(shù)組的順序和機(jī)器順序?qū)?yīng)，數(shù)組上每個(gè)數(shù)字代表對應(yīng)機(jī)器上的加工時(shí)長的數(shù)值。詳細(xì)步驟如下。步驟1：確定1個(gè)整型數(shù)組，數(shù)組的長度就是機(jī)器總數(shù)m，依次為機(jī)器編號順序，數(shù)組對應(yīng)機(jī)器[M1，M2，…，Mm]上的總負(fù)荷。然后初始化數(shù)組，數(shù)組中每個(gè)元素的值初始化為0。再任選擇一臺工件的第一道工序，開始。

步驟2：在當(dāng)前工序的可選加工機(jī)器集中，選擇加工機(jī)器所需要的加工時(shí)間和數(shù)組中相應(yīng)機(jī)器位置的時(shí)間數(shù)值相加，但是不更新數(shù)組。

步驟3：在相加后的時(shí)間中，選取對應(yīng)數(shù)值最小的機(jī)器為當(dāng)前工序的加工機(jī)器，將選中機(jī)器在可選機(jī)器集中的順序號設(shè)置為按工序排列的機(jī)器染色體編碼部分對應(yīng)基因上的數(shù)。

步驟4：將當(dāng)前被選擇的加工機(jī)器的加工時(shí)間加到數(shù)組中相應(yīng)位置機(jī)器的加工負(fù)荷中，同時(shí)更新數(shù)組作為下一次選擇的依據(jù)。

步驟5：繼續(xù)選擇該工件的下一工序，不斷重復(fù)步驟2~步驟4，直到該工件的所有工序的加工機(jī)器被選擇完，然后停止循環(huán)。

步驟6：從工件集中除去已被選擇的工件，從剩下的工件集中隨機(jī)選擇1個(gè)工件，同時(shí)選擇當(dāng)前工件的第一道工序，不斷重復(fù)步驟2~步驟5，直到工件集中的所有工件都被選擇。

3.3.2 交叉

交叉是遺傳算法的核心操作，它可以決定遺傳算法的全局搜索能力。在作業(yè)車間調(diào)度問題中設(shè)計(jì)交叉算子中需要留意是子代對父代優(yōu)良特征的繼承性。同時(shí)，使子代具有可行性。常用的交叉算子有JOX、SXX、SPX和PPX等，但是基于工序編碼的交叉算子POX（precedence operation crossover）可以保證所有工件在父代和子代中出現(xiàn)的次數(shù)相同，并保持任意工件工序之間的順序約束關(guān)系[8]，既具有優(yōu)秀的繼承父代優(yōu)良特征的特性，同時(shí)其子代均為可行解，因此該文選用POX交叉算子，如圖2所示。

假設(shè)父代m×n染色體父代1和父代2，POX產(chǎn)生子代1和子代2，POX交叉的具體流程如下：1） 把工件集{1，2，3，…，n}劃分為2個(gè)非空子集J1{2，3}和J2{1，4}。2） 復(fù)制父代1包括在J1{2，3}的工件到子代1，父代1包括在J2{1，4}的工件到子代2，保留它們的位置。3） 復(fù)制父代2包括在J2{1，4}的工件到子代1，父代2包括在J1{2，3}的工件到子代2，保留它們的順序。

其中，POX為基于工序編碼的交叉算子；J1為工件1；J2為工件2，父代和子代染色體由工件集{1，2，3，4，5，6}組成。

圖2展示4×6調(diào)度問題的2個(gè)父代交叉過程。2個(gè)父代1、父代2交叉生成子代1染色體基因?yàn)閇3124231422]，子代2染色體基因?yàn)閇4132621426]。經(jīng)此得出優(yōu)先操作算子，保留了工件J1和工件J2在機(jī)器上的位置，子代繼承父代每臺機(jī)器上工件次序。

圖2 基于工序編碼的交叉算子POX

3.3.3 變異

在遺傳算法中，變異算子可以保持群體的多樣性。這里的變異操作，是針對單個(gè)染色體的不同基因序號進(jìn)行交換。變異可以使算法跳出局部最優(yōu)解，不同變異方式對算法能否求得全局最優(yōu)解有很大的影響。使用位置變異法作為變異算子，即從染色體中隨機(jī)產(chǎn)生2個(gè)位置并交換這2個(gè)位置的值。

4 示例仿真

以4個(gè)工件、6臺機(jī)器為例，各工件每道工序可選機(jī)器對應(yīng)的生產(chǎn)時(shí)間見表1。該實(shí)例從J1到J4共有4個(gè)工件，其中J1、J2各有2道工序，J3、J4各有3道工序，h為具體工序，表中數(shù)值表示各工序在機(jī)器M1到M6上的加工時(shí)間。

表1 4×6實(shí)例表

甘特圖是通過條狀圖來顯示項(xiàng)目進(jìn)度和其他時(shí)間相關(guān)信息的常用項(xiàng)目管理圖表，以上案例仿真結(jié)果均使用甘特圖來直觀展現(xiàn)作業(yè)車間調(diào)度問題的優(yōu)化結(jié)果，如圖3所示。

圖3 仿真甘特圖

其中，J1為最早下單工件，J4為最晚下單工件，J2為加急訂單，工件轉(zhuǎn)運(yùn)時(shí)間遠(yuǎn)小于各工序加工時(shí)間，忽略不計(jì)。

4.1 原有經(jīng)驗(yàn)管理模式仿真

原有經(jīng)驗(yàn)管理模式情況下如公式（7）所示。

根據(jù)EDD規(guī)則，優(yōu)先生產(chǎn)J2；其余工件根據(jù)FCFS法則，按照J(rèn)1、J3和J4的順序加工。工件加工順序?yàn)镴2、J1、J3和J4，班組選擇順序?yàn)镸5、M1、M3和M4。

有經(jīng)驗(yàn)的管理者可以根據(jù)經(jīng)驗(yàn)很快安排出加工時(shí)間5 4 15 17，制造跨度（makespan）=17；無相關(guān)經(jīng)驗(yàn)的管理者依照PDR規(guī)則排出加工時(shí)間為5 4 16 19，makespan=19。

該案例為4工件、6機(jī)器調(diào)度案例，機(jī)器數(shù)小于工件數(shù)，即同一時(shí)刻可由多個(gè)空閑設(shè)備可供選擇。而在實(shí)際生產(chǎn)中工件數(shù)往往遠(yuǎn)大于機(jī)器數(shù)，其調(diào)度負(fù)責(zé)程度更高，基于PDR規(guī)則的調(diào)度策略的精確度將會進(jìn)一步下降，同時(shí)不同管理者使用PDR規(guī)則得出的不同makespan也暴露PDR策略調(diào)度方案中對人的依賴較大，在復(fù)雜調(diào)度方案中往往只能依靠有豐富經(jīng)驗(yàn)的管理者才能得出較優(yōu)方案。在實(shí)際生產(chǎn)中，使用該策略顯然不利于公司產(chǎn)能擴(kuò)大。

4.2 使用計(jì)算機(jī)輔助管理模式仿真

建立優(yōu)先級。

將以上優(yōu)先級信息預(yù)先置于Z企業(yè)ERP生產(chǎn)管理工具箱中。

ERP中生產(chǎn)輔助工具需要先輸入各工件對應(yīng)的設(shè)備優(yōu)先級，在設(shè)備空閑情況下按照設(shè)備優(yōu)先級從高到低順序排列，遇到相同優(yōu)先級時(shí)按照設(shè)備序號排列。由于輔助功能的局限性，因此一般安排同一工件僅由同一臺設(shè)備完成。使用該方案仿真結(jié)果如圖4所示，每臺設(shè)備的所有工序均在同一臺機(jī)器加工，makespan=16。

圖4 使用計(jì)算機(jī)輔助管理模式的仿真甘特圖

使用ERP中生產(chǎn)輔助工具進(jìn)行生產(chǎn)調(diào)度在一定程度上規(guī)避了傳統(tǒng)方案中對有經(jīng)驗(yàn)管理者的過度依賴，在工件數(shù)不多的情況下可以更快捷地指定較為合適的調(diào)度方案。但是該方案的弊端依然明顯，在遇到工件數(shù)多的情況下，調(diào)度方案就會出現(xiàn)異常，makespan甚至可能高于傳統(tǒng)方案，此時(shí)依然需要有經(jīng)驗(yàn)管理者的介入。

4.3 GA-JSP方案管理模式仿真

設(shè)置子代數(shù)量為200，在第0代時(shí)就可得到最優(yōu)結(jié)果，makespan=15。

利用遺傳算法后優(yōu)化出的結(jié)果如圖5所示，在圖5（b）中可以看出最優(yōu)解很快收斂得出最終makespan=15，優(yōu)化結(jié)果略優(yōu)于有豐富經(jīng)驗(yàn)的管理者制定的傳統(tǒng)方案和ERP輔助決策后的方案，遠(yuǎn)優(yōu)于無經(jīng)驗(yàn)管理者制定的傳統(tǒng)調(diào)度方案。同時(shí)，該仿真僅用在4×6調(diào)度問題中，在調(diào)度方案更復(fù)雜的情況下，遺傳算法解決這類問題的優(yōu)勢將更明顯。

圖5 GA-JSP的仿真甘特圖

5 結(jié)語

針對Z企業(yè)配電箱作業(yè)調(diào)度采用的管理調(diào)度模式進(jìn)行優(yōu)化，通過引入遺傳算法的JSP模型，解決了原有調(diào)度模式下，面對較大訂單量時(shí)傳統(tǒng)調(diào)度模式效率過低的問題，優(yōu)化了擁有不同經(jīng)驗(yàn)水平管理者對調(diào)度效率的影響，提高了調(diào)度策略在復(fù)雜環(huán)境下的適應(yīng)性。在Z企業(yè)后續(xù)面臨生產(chǎn)調(diào)度難題時(shí)提供了更高效的解決方案，同時(shí)針對這類管理者對作業(yè)車間調(diào)度產(chǎn)生較大影響的問題提供了新的解決思路。