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

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

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

中圖分類號(hào)： TP39 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.06.027

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

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

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

1 ?問(wèn)題描述及模型建立

2 ?算法設(shè)計(jì)

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

2.1 ?編碼設(shè)計(jì)

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

2.2 ?適應(yīng)度函數(shù)值設(shè)計(jì)

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

2.3 ?進(jìn)化選擇設(shè)計(jì)

2.4 ?交叉操作設(shè)計(jì)

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

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

3 ?案例分析

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

不同零部件的不同工序在不同機(jī)器上加工的時(shí)間不同，其中，每一個(gè)零部件對(duì)應(yīng)的不同工序在不同機(jī)器上的加工時(shí)間表如表2所示。

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

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

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

4 ?結(jié)論

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

參考文獻(xiàn)

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

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

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

[4] 楊繼偉. 視頻云源站的資源調(diào)度系統(tǒng)設(shè)計(jì)與實(shí)現(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] 張春燕. 基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(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)設(shè)計(jì)[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ā)設(shè)計(jì)與實(shí)現(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)設(shè)備網(wǎng)絡(luò)的改進(jìn)間歇生產(chǎn)調(diào)度模型[J]. 化工學(xué)報(bào)， 2018.

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

[14] 謝思聰， 陳小波. 基于多層編碼遺傳算法的兩階段裝配式建筑預(yù)制構(gòu)件生產(chǎn)調(diào)度優(yōu)化[J]. 工程管理學(xué)報(bào)， 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）.