遺傳算法求解低碳柔性車間生產(chǎn)調(diào)度問題

張國輝，黨世杰

(鄭州航空工業(yè)管理學(xué)院 管理工程學(xué)院, 鄭州 450015)

?

遺傳算法求解低碳柔性車間生產(chǎn)調(diào)度問題

張國輝，黨世杰

(鄭州航空工業(yè)管理學(xué)院 管理工程學(xué)院, 鄭州 450015)

低碳生產(chǎn)方式已成為當(dāng)前各國所認(rèn)可的生產(chǎn)方式，是可持續(xù)發(fā)展的必然要求。從滿足最大完工時(shí)間最小和生產(chǎn)碳排放量最小角度出發(fā)，構(gòu)建低碳車間調(diào)度模型。使用改進(jìn)的遺傳算法對(duì)有低碳需求的車間生產(chǎn)方式進(jìn)行求解，在求解過程中對(duì)初始解生成機(jī)制和遺傳算子進(jìn)行改進(jìn)，提高算法收斂速度。實(shí)驗(yàn)結(jié)果證明提出的改進(jìn)遺傳算法在求解車間低碳生產(chǎn)調(diào)度中是可行的。

低碳；遺傳算法；柔性作業(yè)車間調(diào)度；優(yōu)化

0 引言

先進(jìn)的制造方式能減少碳排放并節(jié)約能源，是可持續(xù)發(fā)展和低碳制造實(shí)施的關(guān)鍵環(huán)節(jié)。車間調(diào)度技術(shù)在保證產(chǎn)品質(zhì)量和控制生產(chǎn)成本的同時(shí)，能夠優(yōu)化加工方案，減少能源消耗量，降低制造過程中的碳排放。

柔性作業(yè)車間調(diào)度問題(Flexible Job Shop Scheduling Problem, FJSP)擴(kuò)展了傳統(tǒng)的作業(yè)車間調(diào)度問題，更貼近生產(chǎn)，然而，計(jì)算難度急劇增加，傳統(tǒng)的優(yōu)化方法已不能滿足求解的需要。許多學(xué)者使用智能算法求解柔性作業(yè)車間調(diào)度問題，例如：遺傳算法[1]、粒子群優(yōu)化算法[2]、偵查包圍搜索算法[3]以及蟻群算法[4]等。其中有部分學(xué)者將碳排放量作為優(yōu)化目標(biāo)之一，通過使用有效的調(diào)度方案減少能源消耗，增加企業(yè)效益。蔣增強(qiáng)等[5]在考慮設(shè)備狀態(tài)-能耗分布曲線的低碳策略基礎(chǔ)上，使用改進(jìn)的NSGA-II算法求解多目標(biāo)調(diào)度模型。Liu等[6]使用改進(jìn)的遺傳算法求解雙目標(biāo)柔性作業(yè)車間調(diào)度，減少了加工時(shí)的能源消耗并縮短了完工時(shí)間。Miguel等[7]依據(jù)加工速度和能耗的關(guān)系，建立了以能耗及最大完工時(shí)間為目標(biāo)的柔性車間調(diào)度模型。Tang等[8]使用遺傳模擬退火算法對(duì)小規(guī)模和大規(guī)模兩種問題進(jìn)行求解，得出了小規(guī)模問題比大規(guī)模問題的能效提升效果顯著的結(jié)論。

本文以某制造企業(yè)的一個(gè)生產(chǎn)加工車間為例，建立了以最大完工時(shí)間和碳排放量為目標(biāo)的柔性作業(yè)車間調(diào)度模型，最后利用改進(jìn)的遺傳算法進(jìn)行求解，驗(yàn)證了所提遺傳算法在求解有低碳需求的生產(chǎn)調(diào)度車間的可行性和有效性。

1 低碳排放目標(biāo)下柔性作業(yè)車間調(diào)度問題模型

為實(shí)現(xiàn)節(jié)能減排，降低碳排放，縮短最大完工時(shí)間，本文對(duì)低碳排放目標(biāo)下FJSP建立了數(shù)學(xué)模型。

為了便于描述FJSP，本文定義以下變量和參數(shù)：

n為工件總數(shù)；

m為機(jī)器總量；

h為機(jī)器序號(hào)，h= 1，2，3，…，m；

i為工件序號(hào)，i= 1，2，3，…，n；

Oij為第i個(gè)工件的第j道工序；

tijh為工序Oij在機(jī)器h上的加工時(shí)間；

Cmax為最大完工時(shí)間；

f(x)為決策者根據(jù)目標(biāo)權(quán)重選擇的生產(chǎn)方案；

E為碳排放量；

FJSP問題則可以描述為有m臺(tái)加工機(jī)器加工n個(gè)工件，每個(gè)工件有i個(gè)工序，每個(gè)工序可以在h臺(tái)可選機(jī)器上任選一臺(tái)進(jìn)行加工，最大完工時(shí)間和碳排放量因加工機(jī)器和工序順序的不同而不同，通過合理的調(diào)度方案可以有效的減少生產(chǎn)過程中的能源消耗和加工時(shí)間浪費(fèi)。

本文以最大完工時(shí)間和碳排放量為目標(biāo)，目標(biāo)函數(shù)如下：

(1)最大完工時(shí)間最小:

minCmax=min(max{Ci|i=1,2,…,n})

(1)

(2)碳排放量最小:

(2)

分別對(duì)兩個(gè)函數(shù)賦以權(quán)重α、β，得到：

minf(x)=α·Cmax+β·E

(3)

假設(shè)在FJSP問題中，存在一個(gè)可選方案集S，則方案集中的一個(gè)方案s投影到軸C和軸E后，分別乘以各自的權(quán)重，比較所有的方案，數(shù)值越大的方案對(duì)決策者的效用越低，故數(shù)值最小的f(x)的即是所選擇的方案，如圖1所示。

圖1 調(diào)度可選方案集

約束條件為：

(1)工序先后約束

tij≤ti(j+1)

(4)

(2)加工機(jī)器約束

(5)

(3)資源約束

tijh≤tglh∪Rijglh=1

(6)

2 改進(jìn)遺傳算法求解FJSP問題

2.1 編碼和解碼

兩段式編碼方式是為了解決FJSP問題的兩個(gè)子問題，工序染色體部分用來解決工序排序問題，機(jī)器染色體部分用來解決機(jī)器選擇問題。本文在編碼和解碼時(shí)使用張國輝等[9]所提出的方法來提高種群初始解的質(zhì)量，加快遺傳算法的收斂速度。

2.2 初始解的產(chǎn)生

本文采用兩段式編碼方式，工序染色體部分隨機(jī)產(chǎn)生，改進(jìn)了機(jī)器染色體部分生成機(jī)制。即在生成工序染色體后，在每道工序上隨機(jī)選擇兩個(gè)加工機(jī)器，然后在[0,1]區(qū)間上產(chǎn)生一個(gè)隨機(jī)數(shù)λ，若λ>0.8，選擇加工時(shí)間較短的機(jī)器，其他情況則選擇加工時(shí)間較長的機(jī)器作為該工序的加工機(jī)器。

2.3 遺傳操作

遺傳操作主要包括選擇操作、交叉操作、變異操作。選擇操作使用錦標(biāo)賽選擇方法，該方法隨機(jī)性強(qiáng)，有利于篩選出適應(yīng)性強(qiáng)的個(gè)體。針對(duì)工序染色體和機(jī)器染色體使用不同的交叉方式，在進(jìn)行交叉操作和變異操作時(shí)分別根據(jù)每段染色體的特點(diǎn)進(jìn)行相應(yīng)的操作。

(1)機(jī)器染色體交叉操作

在機(jī)器染色體交叉操作時(shí)使用MPX[10]交叉方式，隨機(jī)產(chǎn)生一條染色體且與機(jī)器染色體長度相同，該染色體上的基因只能是0和1。對(duì)比該染色體和機(jī)器染色體，若該隨機(jī)染色體為0的位置則保留父代染色體上相應(yīng)的基因，否則交換父代染色體的位置，經(jīng)過變換后產(chǎn)生兩條新的合法子代染色體。

(2)工序染色體交叉操作

在該操作中使用張超勇等[11]提出的POX交叉操作。將所有的工件分為兩個(gè)集合，記為工件集1和工件集2，生成兩個(gè)長度與原染色體相同的空白子代染色體，然后在第一個(gè)子代染色體的位置保留工件集1對(duì)應(yīng)的基因，在第二個(gè)子代染色體中保留集合2的位置，依照剩余染色體保留它們的順序填充到子代染色體。

(3)機(jī)器染色體變異操作

機(jī)器染色體變異時(shí)，在機(jī)器染色體隨機(jī)選擇一個(gè)基因，然后從對(duì)應(yīng)工序上的加工機(jī)器集中再隨機(jī)選擇一臺(tái)其他的加工機(jī)器并作為該工序的加工機(jī)器，這種變異方式能夠保證變異后的機(jī)器染色體仍是合法解。

(4)工序染色體變異操作

當(dāng)進(jìn)行工序染色體變異時(shí)，隨機(jī)選擇兩個(gè)不為同一工件的工序，交換兩者的位置后得到一條新的染色體。根據(jù)工序染色體編碼的特點(diǎn)，該變異操作避免產(chǎn)生非法解，同時(shí)增加了種群多樣性。

2.4 計(jì)算流程

改進(jìn)后的遺傳算法計(jì)算流程可以描述為：

步驟1：參數(shù)設(shè)置。設(shè)定種群規(guī)模、交叉概率、變異概率等參數(shù);

步驟2：種群初始化。利用提出的初始化方法對(duì)種群進(jìn)行初始化，產(chǎn)生新種群;

步驟3：評(píng)價(jià)種群中的每個(gè)染色體個(gè)體的適應(yīng)度值，若滿足結(jié)束條件，則輸出最優(yōu)解并結(jié)束運(yùn)行，否則進(jìn)入步驟4;

步驟4：更新種群。對(duì)種群個(gè)體執(zhí)行錦標(biāo)賽選擇，對(duì)滿足條件的染色體個(gè)體執(zhí)行交叉操作和變異操作，得到新種群;

步驟5：返回步驟3。

3 實(shí)例仿真實(shí)驗(yàn)

某制造車間生產(chǎn)過程可以簡化為一個(gè)8個(gè)工件在7臺(tái)機(jī)器上加工的柔性作業(yè)車間調(diào)度問題。在對(duì)車間生產(chǎn)進(jìn)行調(diào)度時(shí)，方案的決策者希望生產(chǎn)過程中完工時(shí)間和車間碳排放兩個(gè)目標(biāo)都得以優(yōu)化。該制造車間的加工數(shù)據(jù)如表1所示，表中第1列表示工件號(hào)，第2列表示每個(gè)工件的工序，第3～7列表示可選擇的加工機(jī)器，有數(shù)字的代表對(duì)應(yīng)的機(jī)器可以被選擇，例如工序O11不可以在機(jī)器M1上加工，可以在機(jī)器M2上加工，且加工時(shí)間為16，碳排放量為1.7。

表1 加工車間簡化后的FJSP問題

算法采用Visual Studio 2012編程，運(yùn)行環(huán)境為P4 CPU，主頻2.3GHz，內(nèi)存2G的個(gè)人計(jì)算機(jī)。其中多目標(biāo)遺傳算法的主要參數(shù)設(shè)置如下：種群規(guī)模P=200，交叉概率Pc=0.8，變異概率Pm=0.05。使用改進(jìn)的遺傳算法求解該FJSP實(shí)例，得到的結(jié)果如表2所示。表2中，分別對(duì)三種情況下的完工時(shí)間和碳排放量之間的權(quán)重進(jìn)行優(yōu)化求解，這幾個(gè)解之間是非支配解的關(guān)系。當(dāng)完工時(shí)間的權(quán)重比較大時(shí)，獲得調(diào)度方案完工時(shí)間最小，然而碳排放量明顯高；當(dāng)完工時(shí)間的權(quán)重比較小時(shí)，獲得調(diào)度方案碳排放量最低，而完工時(shí)間會(huì)比較長。

表2 不同權(quán)重下的目標(biāo)值

在選取方案時(shí)，根據(jù)決策者對(duì)實(shí)際情況的了解，選取一個(gè)調(diào)度方案為其執(zhí)行方案。本文給出了當(dāng)目標(biāo)權(quán)重相同時(shí)的甘特圖，如圖2所示，其中最大完工時(shí)間是66，生產(chǎn)碳排放量是677.4，右上角的數(shù)字代表該工序在機(jī)器上加工時(shí)的碳排放量。如圖2所示的在機(jī)器M1上有兩個(gè)加工工序O31、O22，它們的加工時(shí)間分別為18、17，對(duì)應(yīng)的碳排量分別為39.6、44.2。

圖2 調(diào)度甘特圖

4 結(jié)論

通過對(duì)有低碳生產(chǎn)要求的柔性車間調(diào)度問題的描述，構(gòu)建以最大完工時(shí)間最小和碳排放量最小為目標(biāo)函數(shù)的調(diào)度模型。提出了改進(jìn)的遺傳算法以提高算法收斂速度，改進(jìn)了遺傳算法初始解生成機(jī)制和優(yōu)化了選擇、交叉、變異操作等。然后以企業(yè)車間生產(chǎn)實(shí)際案例為應(yīng)用背景進(jìn)行優(yōu)化，得到了不同權(quán)重下的調(diào)度方案。最后給出了兩個(gè)目標(biāo)權(quán)重相似的方案調(diào)度甘特圖，實(shí)驗(yàn)結(jié)果表明提出的改進(jìn)遺傳算法在求解車間低碳生產(chǎn)方式是可行的。

[1] 李運(yùn)霞, 杜娟, 孫王路. 基于多種群遺傳算法的路徑柔性車間調(diào)度問題[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2014(3): 152-155.

[2] 劉韻, 胡毅, 羅企, 等. 一種解決柔性車間作業(yè)調(diào)度問題的粒子群優(yōu)化算法[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2015(12): 144-147.

[3] 劉韻, 胡毅, 房超, 等. 解決柔性車間作業(yè)調(diào)度問題的偵查包圍搜索算法[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2015(11): 124-128.

[4] 武福, 張治娟. 一種求解柔性作業(yè)車間調(diào)度問題的混合智能算法[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2013(5): 130-133.

[5] 蔣增強(qiáng), 左樂. 低碳策略下的多目標(biāo)柔性作業(yè)車間調(diào)度[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2005, 21(4): 1023-1031.

[6] Liu Y, Tiwari A. An investigation into minimising total energy consumption and total completion time in a flexible job shop for recycling carbon fiber reinforced polymer[C]. The 22nd CIRP conference on Life Cycle Engineering, 2015, 29: 722-727.

[7] Salido M A, Escamilla J, Giret A, et al. A genetic algorithm for energy-efficiency in job-shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2015: 1-12.

[8] Tang D B, Dai M. Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering, 2015, 28(5): 1-8.

[9] 張國輝, 高亮, 李培根, 等. 改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J]. 機(jī)械工程學(xué)報(bào), 2009, 45(7): 145-151.

[10] 劉瓊, 張超勇, 饒運(yùn)清, 等. 改進(jìn)遺傳算法解決柔性作業(yè)車間調(diào)度問題[J]. 工業(yè)工程與管理, 2009, 14(2): 59-66.

[11] 張超勇, 饒運(yùn)清, 劉向軍, 等. 基于POX交叉的遺傳算法求解Job-Shop調(diào)度問題[J]. 中國機(jī)械工程, 2004, 15(23): 2149-2453.

(編輯 李秀敏)

Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem with Low Carbon

ZHANG Guo-hui，DANG Shi-jie

(School of Management Engineering, Zhengzhou University of Aeronautics, Zhengzhou 450015, China)

Low carbon production mode has become the current accepted production mode, it is also the inevitable requirement of sustainable development. Low carbon flexible job shop scheduling model is built to meet the target of minimum makespan and producing carbon emissions. An improved genetic algorithm is proposed to solve the workshop production mode with low carbon requirements, in the process of solving, the initial solution and genetic operator are improved to enhance the algorithm convergence speed. Finally, the experimental results show that the proposed improved genetic algorithm is feasible in solving low carbon production scheduling.

low carbon; genetic algorithm; flexible job shop scheduling; optimization

1001-2265(2016)11-0141-04

10.13462/j.cnki.mmtamt.2016.11.038

2015-12-29；

2016-01-27

國家自然科學(xué)基金(61203179); 河南省高?？萍紕?chuàng)新人才支持計(jì)劃資助(14HASTIT006); 河南省高等學(xué)校青年骨干教師資助計(jì)劃(2014GGJS-105); 航空科學(xué)基金(2014ZG55016);鄭州航院研究生教育創(chuàng)新計(jì)劃基金(2015CX009)；河南省軟科學(xué)項(xiàng)目(JYB2013034)

張國輝(1980—)，男，河南新鄉(xiāng)人，鄭州航空工業(yè)管理學(xué)院副教授，博士，研究方向?yàn)楣I(yè)工程，(E-mail)zgh09@zzia.edu.cn。

TH16;TG506

A