基于遺傳算法的多工序多機器調(diào)度優(yōu)化研究

摘 ?要： 隨著人民生活質(zhì)量的提高，消費者對定制化生產(chǎn)提出了更高的要求，此外，在新的經(jīng)濟環(huán)境下，降本增效對于提升制造企業(yè)的發(fā)展能力具有重要的意義，基于此，本文提出了基于遺傳算法的多工序多機器調(diào)度優(yōu)化研究。首先，設計了基于完工時間最小化的多工序多機器加工約束的生產(chǎn)調(diào)度優(yōu)化模型;其次，采用遺傳算法設計了求解上述生產(chǎn)調(diào)度優(yōu)化模型的算法;最后，通過案例驗證了本文構建的優(yōu)化模型及設計的優(yōu)化算法，并繪制了以最小化完工時間為優(yōu)化目標的生產(chǎn)調(diào)度甘特圖。研究結果表明，本文構建的模型及設計的算法具有一定的實用性，可指導企業(yè)制定較優(yōu)的生產(chǎn)調(diào)度方案。

關鍵詞： 制造企業(yè);生產(chǎn)調(diào)度;遺傳算法;完工時間

中圖分類號： TP39 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.06.027

本文著錄格式：周福來. 基于遺傳算法的多工序多機器調(diào)度優(yōu)化研究[J]. 軟件，2019，40（6）：123126

【Abstract】： With the improvement of people's living quality， consumers put forward higher requirements for customized production. In addition， in the new economic environment， reducing costs and increasing efficiency is of great significance to enhance the development ability of manufacturing enterprises. Based on this， this paper proposes a multi-process and multi-machine Scheduling Optimization Research Based on genetic algorithm. Firstly， a production scheduling optimization model with multi-process and multi-machine constraints based on minimum completion time is designed; secondly， the genetic algorithm is used to design the algorithm for solving the above production scheduling optimization model; finally， the optimization model and the optimization algorithm designed in this paper are verified by a case study， and the production scheduling Gantt with the objective of minimizing completion time is drawn. Graph. The results show that the model and algorithm constructed in this paper have certain practicability and can guide enterprises to formulate better production scheduling schemes.

【Key words】： Manufacturing enterprises： Production scheduling; Genetic algorithm; Completion time

0 ?引言

制造業(yè)在國民經(jīng)濟的發(fā)展過程中起著重要的作用，特別是在經(jīng)濟進入新常態(tài)下，我國的經(jīng)濟發(fā)展速度也進入了全新的發(fā)展階段，為提升我國經(jīng)濟發(fā)展質(zhì)量，國家政府先后制定了一系列的利好政策。對于生產(chǎn)制造企業(yè)而言，如何降低生產(chǎn)制造成本對于適應新的經(jīng)濟發(fā)展宏觀環(huán)境具有重要的積極作用，然而，在生產(chǎn)制造過程中，對企業(yè)或行業(yè)提高生產(chǎn)效率和效益是至關重要的[1-2]，由于生產(chǎn)調(diào)度計劃安排不當會給企業(yè)造成不必要的浪費，此外還容易出現(xiàn)因不能及時交付客戶產(chǎn)品而引發(fā)的市場競爭力有所下降等問題，因此，再此背景下研究生產(chǎn)調(diào)度優(yōu)化問題具有重要的現(xiàn)實意義。

針對生產(chǎn)制造過程中的調(diào)度問題，近年來國內(nèi)外相關研究學者展開了大量的研究工作，并取得了一系列的研究成果。李占丞研究了以包含訂貨、采購、庫存以及拖期懲罰成本的期望總成本最小化為目標[3-4]，Jurgen Branke.對各種調(diào)度問題進行廣泛的分類，并回顧這些問題類的重要理論發(fā)展，將現(xiàn)有的理論與生產(chǎn)調(diào)度實踐進行對比研究[5-6]，Xiao， Lei結合一系列系統(tǒng)的群預防性維護和生產(chǎn)調(diào)度，建立了聯(lián)合優(yōu)化模型，提出了一種聯(lián)合優(yōu)化模型[7-8]，在生產(chǎn)調(diào)度系統(tǒng)（PSS）與集成制造環(huán)境中的其他單元（決策者和軟件系統(tǒng)）合作的背景下，研究了重新調(diào)度問題[9-10]，Carpentier S在考慮地質(zhì)不確定性的情況下，提出了一種隨機整數(shù)規(guī)劃模型，以優(yōu)化地下采礦作業(yè)的長期調(diào)度為研究目標展開了研究[11]，閆雪麗基于狀態(tài)設備網(wǎng)絡和特定事件點概念，建立非線性的連續(xù)時間間歇生產(chǎn)調(diào)度模型[12]，顏靜針對多品種小批量生產(chǎn)為求快速響應訂單生產(chǎn)所造成的生產(chǎn)中“半成品庫存高、成品訂單準時交貨率低”的問題，建立了以準時交貨為目標的前推后拉式綜合生產(chǎn)調(diào)度系統(tǒng)[13]，謝思聰在對比分析預制構件生產(chǎn)與一般制造業(yè)區(qū)別的基礎上提出預制構件廠生產(chǎn)參數(shù)的量化途徑[14]，Joly M討論了在一家致力于開發(fā)和實施先進煉油廠生產(chǎn)調(diào)度（RPS）技術（即Petrobras的RPS系統(tǒng)）的能源公司中全面實施的一項開創(chuàng)性但大膽的企業(yè)級項目所獲得的關鍵經(jīng)驗[15]。

雖然國內(nèi)外相關研究學者針對生產(chǎn)調(diào)度問題近年來展開的深入的研究，也取得了一系列的研究成果，但是，在算法層次研究方面依舊存在著不足，諸如現(xiàn)有研究算法較難滿足不同零部件不同工序可以在不同設備上進行加工的并行生產(chǎn)調(diào)度問題，而該問題的解決對于提升生產(chǎn)制造企業(yè)響應客戶個性化的需求具有重要的意義，因此，本文從計算機編程的角度，以現(xiàn)代生產(chǎn)制造企業(yè)的生產(chǎn)調(diào)度為研究對象，研究了基于遺傳算法的多工序多機器約束的生產(chǎn)調(diào)度優(yōu)化問題。

1 ?問題描述及模型建立

2 ?算法設計

由于遺傳算法在求解生產(chǎn)調(diào)度問題時具有求解速度快的優(yōu)勢，因此，本文采用編程技術進行編碼，利用遺傳算法進行求解上述優(yōu)化問題，其中，編碼設計、適應度函數(shù)、進化選擇及交叉操作描述如下。

2.1 ?編碼設計

本文采用整數(shù)的編碼形式對染色體個體進行編碼，其中每一條由整數(shù)組合而成的染色體表示求解生產(chǎn)制造過程中調(diào)度問題對應的一個可行解。其中在采用整數(shù)編碼的染色體上邊，前半段表示零部件以此經(jīng)過生產(chǎn)線時所對應的加工順序，后半段則表示不同的零部件的加工工序所對應的生產(chǎn)設備，即某一零部件的某到工序?qū)谠撛O備上完成加工。假設某一個體的編碼形式為[2 3 4 5 6 7 8 1 2 3 4 5 6 7]，則該染色體有包括了兩個信息，第一個信息為零部件的加工工序，即以此加工零部件2、零部件3、零部件4、零部件5……直到加工零部件8;第二個信息為所加工零部件對應設備，即這些零部件依次在設備1、設備2、設備3……設備7上邊完成加工。

2.2 ?適應度函數(shù)值設計

由于本文求解的目標函數(shù)是如何合理地安排加工工序，使得總的生產(chǎn)加工完工時間最小化，因此，本文將目標函數(shù)值即完工時間作為適應度函數(shù)值，對種群進化及進行選擇，其中適應度函數(shù)如公式（2）所示。

2.3 ?進化選擇設計

2.4 ?交叉操作設計

在使用遺傳算法求解生產(chǎn)調(diào)度優(yōu)化問題時，其核心是模擬生物界的自然種群進化規(guī)律，實現(xiàn)種群的優(yōu)勝劣汰進化，因此，進化操作在整個求解最優(yōu)調(diào)度方案中起著關鍵性的作用，本文設計兩點隨機交叉法來實現(xiàn)整個種群的進化操作，其中，個體交叉操作過程示意圖如圖1所示。

在交叉操作過程中，首先，在一對染色體上隨機選擇兩點作為交叉點;其次將這兩條染色體對應的交叉點位置的基因片段進行交叉，例如圖1中第一條染色體的交叉點為2，3，第二條染色體的交叉點為3，1，則經(jīng)過交叉操作之后，第一條染色體的基因?qū)⒆兂蔀?，1，與此同時，第二條染色體對應的基因?qū)⒆優(yōu)?，3。然后，對多余的工序以及對應工序的加工機器進行調(diào)整，最終產(chǎn)生新的個體，即表示新的可行解產(chǎn)生。

3 ?案例分析

生產(chǎn)調(diào)度屬于生產(chǎn)制造過程中的關鍵性技術問題，一個好的生產(chǎn)調(diào)度方案可以為企業(yè)有效降低加工成本，在本部分，本文將選擇一個案例來說明本文設計的優(yōu)化求解模型及算法在求解生產(chǎn)調(diào)度問題時具有一定的可行性與優(yōu)勢。現(xiàn)有10臺機器負責加工6個零部件，每個零部件需要經(jīng)過6道加工工序才能完成整個加工過程，某些零部件的不同加工工序可以選擇在不同的機器上進行加工。其中，不同零部件加工工序可選的機器信息如表1所示。

不同零部件的不同工序在不同機器上加工的時間不同，其中，每一個零部件對應的不同工序在不同機器上的加工時間表如表2所示。

本文采用編程技術編寫的遺傳算法代碼在Matlab軟件上對生產(chǎn)調(diào)度優(yōu)化問題進行求解，設置初始種群數(shù)為40，最大迭代次數(shù)為50次。通過Matlab軟件求解出了滿足加工時間最小化的生產(chǎn)調(diào)度方案，其中，最優(yōu)結果對應下的生產(chǎn)調(diào)度方案甘特圖如圖2所示。

圖2中，x軸表示加工時間，y軸表示加工機器。根據(jù)上圖可以清晰地看出不同零部件對應的不同工序的生產(chǎn)計劃調(diào)度安排，此外還可以看出不同加工機器對應的完工時間。在采用Matlab算法求解生產(chǎn)制造過程中的生產(chǎn)調(diào)度問題時，得到的進化迭代圖如圖3所示。

根據(jù)圖3可以看出在求解生產(chǎn)調(diào)度優(yōu)化問題過程中解的變化過程以及種群均值的變化過程，從圖3中可以看出，本文設計的算法能夠快速地在短時間內(nèi)尋找出以完工時間為優(yōu)化目標生產(chǎn)調(diào)度方案，且最早的完工時間為53，這說明了本文采用編程技術設計的優(yōu)化算法能夠較好地解決生產(chǎn)調(diào)度優(yōu)化問題。

4 ?結論

本文以制造企業(yè)中制定生產(chǎn)調(diào)度的問題為對象展開了研究，構建了以最小化完工時間為最優(yōu)的生產(chǎn)調(diào)度優(yōu)化模型，基于遺傳算法設計了求解該生產(chǎn)調(diào)度優(yōu)化模型的算法，并選擇案例對本文構建的模型及設計的算法進行了驗證，結果表明本文構建的生產(chǎn)調(diào)度優(yōu)化模型及設計的優(yōu)化模型求解算法具有一定的實用性。

參考文獻

[1] 徐俊剛， 戴國忠， 王宏安. 生產(chǎn)調(diào)度理論和方法研究綜述[J]. 計算機研究與發(fā)展， 2004， 41（2）： 257-267.

[2] 盧宏， 孫鵬. 鋼鐵企業(yè)基于無線傳感網(wǎng)的氧氣實時優(yōu)化調(diào)度[J]. 軟件， 2018， 39（5）： 129-133.

[3] 李占丞， 劉曉冰， 薄洪光. 面向生產(chǎn)調(diào)度的訂貨量分配問題研究[J]. 工業(yè)工程與管理， 2016（2）.

[4] 楊繼偉. 視頻云源站的資源調(diào)度系統(tǒng)設計與實現(xiàn)[J].軟件， 2018， 39（5）： 170-181.

[5] Jurgen Branke， Member， IEEE， et al. Automated Design of Production Scheduling Heuristics： A Review[J]. IEEE Transactions on Evolutionary Computation， 2015， 20（1）.

[6] 張春燕. 基于改進遺傳進化算法的復雜作業(yè)流程調(diào)度[J].軟件， 2017， 38（12）： 98-103.

[7] Xiao， Lei， Song， et al. Joint optimization of production scheduling and machine group preventive maintenance[J]. Reliability Engineering & System Safety， 2016， 146： 68-78.

[8] 李偉， 鄧紅濤， 陳紅莉， 韓峰. 面向飼料產(chǎn)品的物流車輛調(diào)度系統(tǒng)設計[J]. 軟件， 2016， 37（08）： 51-53.

[9] Kalinowski K， Grabowik C， Kempa W， et al. The role of the production scheduling system in rescheduling[J]. IOP Conference Series： Materials Science and Engineering， 2015， 95： 012140-.

[10] 彭超. 基于B/S模式下的煤礦生產(chǎn)調(diào)度系統(tǒng)開發(fā)設計與實現(xiàn)[J]. 軟件， 2011， 32（04）： 23-25.

[11] Carpentier S， Gamache M， Dimitrakopoulos R. Underground long-term mine production scheduling with integrated geological risk management[J]. Mining Technology， 2016， 125（2）： 93-102.

[12] 閆雪麗， 韓豫鑫， 顧幸生. 基于狀態(tài)設備網(wǎng)絡的改進間歇生產(chǎn)調(diào)度模型[J]. 化工學報， 2018.

[13] 顏靜， 朱伏平， 楊婉琳. 基于準時交貨的多品種小批量生產(chǎn)調(diào)度系統(tǒng)研究[J]. 機械， 2017（4）.

[14] 謝思聰， 陳小波. 基于多層編碼遺傳算法的兩階段裝配式建筑預制構件生產(chǎn)調(diào)度優(yōu)化[J]. 工程管理學報， 2018.

[15] Joly M， Miyake M Y. Lessons learned from developing and implementing refinery production scheduling technologies[J]. Frontiers of Engineering Management， 2017， 4（3）.