張春燕

（無錫科技職業(yè)學(xué)院，江蘇 無錫 214028）

基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度

張春燕

（無錫科技職業(yè)學(xué)院，江蘇 無錫 214028）

為了提高車間或者工業(yè)生產(chǎn)速度和質(zhì)量，需要對(duì)生產(chǎn)中復(fù)雜作業(yè)流程調(diào)度進(jìn)行研究。當(dāng)前算法利用調(diào)度靜態(tài)求解法和動(dòng)態(tài)優(yōu)化法實(shí)現(xiàn)復(fù)雜作業(yè)流程的調(diào)度。該算法沒有相關(guān)策略的制定，也沒有高效的理論作為支撐，導(dǎo)致該算法存在調(diào)度效率低，資源的利用率和環(huán)境適應(yīng)能力較差等問題。為此，提出基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度。該算法先對(duì)復(fù)雜作業(yè)流程調(diào)度問題進(jìn)行描述，針對(duì)調(diào)度問題描述，利用改進(jìn)遺傳進(jìn)化算法對(duì)車間作業(yè)調(diào)度問題進(jìn)行解決，將問題描述中的數(shù)學(xué)規(guī)劃模型建立在規(guī)定的定義上。然后構(gòu)建合適的編碼實(shí)現(xiàn)改進(jìn)遺傳進(jìn)化算法正常運(yùn)行，過程中按一定要求對(duì)JSSP染色體進(jìn)行編碼，選擇初始種群，并對(duì)適應(yīng)度函數(shù)進(jìn)行計(jì)算，引入交叉算子和變異算子擴(kuò)大尋優(yōu)范圍。最后利用無延遲作業(yè)計(jì)劃解決死鎖狀況，并通過調(diào)度過程流程圖和作業(yè)調(diào)度整體結(jié)構(gòu)流程圖實(shí)現(xiàn)調(diào)度。實(shí)驗(yàn)結(jié)果表明，本文所提算法充分利用了現(xiàn)有資源實(shí)現(xiàn)了復(fù)雜作業(yè)流程的高效調(diào)度，同時(shí)也具有比較好的適應(yīng)能力和靈活性。

遺傳進(jìn)化算法；復(fù)雜作業(yè)流程；調(diào)度

0 引言

車間復(fù)雜作業(yè)流程的調(diào)度，是完成車間資源優(yōu)化配置比較有效的手段[1]。制造業(yè)作為國家實(shí)體經(jīng)濟(jì)重要的組成部分，當(dāng)前面臨著市場的殘酷競爭，制造型企業(yè)發(fā)展中出現(xiàn)了嚴(yán)峻考驗(yàn)，比如資源瀕臨枯竭、勞動(dòng)力成本的不斷增加、客戶對(duì)產(chǎn)品質(zhì)量的要求陸續(xù)提升等[2]。如何考慮產(chǎn)品質(zhì)量、服務(wù)、時(shí)間以及成本等因素，提高品牌聲譽(yù)，得到客戶的青睞，成為了制造型企業(yè)著重考慮的方面[3]。近些年來，中國的制造業(yè)平均水平有了很大的提高，不過在生產(chǎn)的效率以及生產(chǎn)現(xiàn)代化的水平上，與發(fā)達(dá)國家相比還有一定差距。由于復(fù)雜作業(yè)的調(diào)度是提升產(chǎn)品加工效率和實(shí)現(xiàn)制造型企業(yè)現(xiàn)代化發(fā)展的前提與基礎(chǔ)，怎樣實(shí)現(xiàn)實(shí)用又高效的復(fù)雜作業(yè)調(diào)度，成為了先進(jìn)生產(chǎn)模式的首要問題之一[4]。車間作業(yè)的流程調(diào)度是目前調(diào)度領(lǐng)域中最繁瑣和最困難的問題之一，所以采用當(dāng)前的復(fù)雜作業(yè)流程調(diào)度算法，無法實(shí)現(xiàn)物料、機(jī)器和時(shí)間等相關(guān)資源的正確調(diào)度[5]。為了解決上述問題，本文提出了一種基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度，可完善當(dāng)前復(fù)雜作業(yè)流程的正確調(diào)度，提高了調(diào)度的速度，提升了產(chǎn)品生產(chǎn)效率[6]。生產(chǎn)車間的復(fù)雜作業(yè)流程調(diào)度在一定程度上決定了制造型企業(yè)的生存，這樣的重要性引起了人們的討論，和有關(guān)專家學(xué)者的廣泛關(guān)注與研究，以下介紹了幾種比較優(yōu)秀的調(diào)度算法[7]。

文獻(xiàn)[8]算法中提出了工作流程調(diào)度的效率，是評(píng)價(jià)工作整體表現(xiàn)重要指標(biāo)之一。工作流程調(diào)度問題是 NP-hard問題，異構(gòu)式計(jì)算環(huán)境將該問題變得更為棘手，分層基因算法把啟發(fā)式算法和GA算法結(jié)合，根據(jù)GA算法優(yōu)化通過正向分層后的作業(yè)調(diào)度隊(duì)列，很顯著地減少了作業(yè)流程運(yùn)行時(shí)間，該算法利用作業(yè)分層的優(yōu)先級(jí)生成作業(yè)隊(duì)列，將隊(duì)列內(nèi)的同層作業(yè)在整體上當(dāng)作一位基因進(jìn)行處理，可有效規(guī)劃作業(yè)流程，但是耗時(shí)較長。文獻(xiàn)[9]算法提出調(diào)度規(guī)則是實(shí)際生產(chǎn)中車間作業(yè)調(diào)度有關(guān)問題重要解決方式，不過它通常只在指定調(diào)度條件下性能較好，條件發(fā)生變化時(shí)，需要實(shí)時(shí)進(jìn)行選擇和評(píng)價(jià)。實(shí)現(xiàn)調(diào)度規(guī)則實(shí)時(shí)選擇與評(píng)價(jià)方法的綜述，用來研究實(shí)際生產(chǎn)中車間實(shí)時(shí)調(diào)度問題。概述了調(diào)度規(guī)則發(fā)展、特點(diǎn)以及分類，對(duì)調(diào)度規(guī)則選擇與評(píng)價(jià)方法做出總結(jié)，全面介紹調(diào)度規(guī)則選擇方法，其中包含使用比較多的人工智能方法，給出了實(shí)驗(yàn)方法，實(shí)驗(yàn)證明該法對(duì)調(diào)度的選擇和評(píng)估進(jìn)行了深度研究，但是存在實(shí)際應(yīng)用效果較差的問題。文獻(xiàn)[10]算法中，在傳統(tǒng)的優(yōu)先級(jí)調(diào)度算法基礎(chǔ)上，提出利用動(dòng)態(tài)優(yōu)先級(jí)驅(qū)動(dòng)調(diào)度算法。該算法把復(fù)雜作業(yè)流程區(qū)分為四個(gè)等級(jí)，依次分配至已經(jīng)設(shè)置好的等待隊(duì)列中，等待隊(duì)列內(nèi)設(shè)置了不同優(yōu)先級(jí)閾值，對(duì)優(yōu)先級(jí)進(jìn)行動(dòng)態(tài)調(diào)整，達(dá)到閾值之后提升至就緒隊(duì)列中，并通過實(shí)驗(yàn)證明該算法縮短了高優(yōu)先級(jí)的作業(yè)流程響應(yīng)時(shí)間，但是調(diào)度正確性較差。

針對(duì)上述產(chǎn)生的問題，提出一種基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度，并利用實(shí)驗(yàn)證明，該算法可對(duì)復(fù)雜作業(yè)流程進(jìn)行高速穩(wěn)定地調(diào)度。

1 復(fù)雜作業(yè)流程調(diào)度問題描述

假設(shè)大規(guī)模復(fù)雜作業(yè)車間內(nèi)有n個(gè)工件，要在m臺(tái)設(shè)備上進(jìn)行加工，工件i內(nèi)包含道工序，i = 1… n 。各個(gè)工序間有工藝先后順序的約束，每臺(tái)設(shè)備j最多進(jìn)行一次加工，j=1…m，代表工件i于 j上的加工工序，,ijp 代表工序,ijO 加工時(shí)間，,ikt 代表工序,ijO 開工時(shí)間，其中調(diào)度任務(wù)為：在m臺(tái)設(shè)備上對(duì)n個(gè)工件進(jìn)行加工，對(duì)各個(gè)設(shè)備上的各工序加工順序和相關(guān)開工時(shí)間進(jìn)行確定，用來對(duì)各個(gè)工件拖期時(shí)間進(jìn)行最小化操作，并滿足以下約束條件：

全部工件工藝路線以及工序加工的時(shí)間保持不變，其中工序一旦開始，加工就不允許中斷，在同一時(shí)間各設(shè)備最多可加工一個(gè)工件，在同一時(shí)間各工件最多可在一臺(tái)設(shè)備進(jìn)行加工。根據(jù)上述參數(shù)和描述，得到復(fù)雜作業(yè)調(diào)度問題所對(duì)應(yīng)的數(shù)學(xué)規(guī)劃模型，也就是目標(biāo)函數(shù)：

式（1）是復(fù)雜作業(yè)流程調(diào)度問題目標(biāo)，也就是最小化的拖期時(shí)間之和。式（2）代表相同工件在不同工序間加工順序的約束，各工件在任意時(shí)間僅可在一臺(tái)設(shè)備上加工。式（3）與式（4）為相同設(shè)備上的不同工件間加工的順序約束，進(jìn)而保障各設(shè)備在任意時(shí)刻最多加工一個(gè)工件。式（5）保障各個(gè)工件須到車間之后才能開工。復(fù)雜作業(yè)流程調(diào)度問題大概為上述內(nèi)容，下面利用改進(jìn)遺傳進(jìn)化算法解決復(fù)雜作業(yè)流程調(diào)度問題。

2 基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度

2.1 關(guān)于作業(yè)調(diào)度的定義

針對(duì)調(diào)度問題描述，利用改進(jìn)遺傳進(jìn)化算法對(duì)車間作業(yè)調(diào)度問題（JSSP）進(jìn)行解決。車間作業(yè)調(diào)度的基本約束條件為進(jìn)行調(diào)度理論分析主要約束條件，可否解決JSSP基本的約束條件，滿足作業(yè)調(diào)度問題是作業(yè)調(diào)度問題研究的關(guān)鍵。為了更好地解決調(diào)度問題，將上述的數(shù)學(xué)規(guī)劃模型建立在以下定義上。

定義一：假設(shè)P表示n個(gè)工件集合，那么P能夠表達(dá)為式（6）：

定義二：假設(shè)M表示m臺(tái)設(shè)備的集合，那么M可表達(dá)為式（7）：

定義三：假設(shè)iP的工序數(shù)量為ik，iJP表示iP工件工序集合，那么iJP可表達(dá)為式（8）：

定義四：假設(shè) Pi中的工序到 Ji中的元素，在設(shè)備M中的加工次序是記為i（1）,i（2）,… i（ k），其中，那么設(shè)備加工的次序Q可表達(dá)為下式：

定義五：假設(shè)iM上加工工序的排列為iJM，其中0im＜＜，那么iJM可表達(dá)為式（10）：

式中，il代表在設(shè)備iM上的加工工序總數(shù)，代表設(shè)備M第i個(gè)加工零件工序的代號(hào)。

式中，iJM 表示第i臺(tái)設(shè)備上加工工序的排列陣。

定義七：有了設(shè)備加工的次序陣Q以及設(shè)備加工的工序排列陣JM，則可描述一個(gè)加工，不過缺少一個(gè)描述加工的時(shí)間矩陣，由此將加工時(shí)間矩陣定義為：

上述矩陣中每個(gè)元素均和矩陣JM內(nèi)的元素對(duì)應(yīng)。根據(jù)上述七個(gè)定義，和1中的數(shù)學(xué)規(guī)劃模型以及基本約束條件，對(duì)車間作業(yè)調(diào)度遺傳編碼進(jìn)行研究。

2.2 改進(jìn)遺傳進(jìn)化算法編碼

依據(jù)作業(yè)調(diào)度的定義，對(duì)改進(jìn)遺傳進(jìn)化算法編碼進(jìn)行分析，構(gòu)建合適的編碼是實(shí)現(xiàn)改進(jìn)遺傳進(jìn)化算法正常運(yùn)行的重要前提，根據(jù)JSSP數(shù)學(xué)規(guī)劃模型可知，JSSP的解可表示為所有設(shè)備的工序排列矩陣JM，因此JSSP染色體的編碼可否表達(dá)JSSP的一個(gè)有效解，其關(guān)鍵就在于可否直接或者間接表示為設(shè)備工序的排列矩陣JSSP。綜上，JSSP染色體的編碼需做到以下幾點(diǎn)：

1. JSSP的染色體編碼應(yīng)是有序編碼串。只有有序，才能將JSSP染色體的編碼，唯一地映象成一個(gè)設(shè)備工序排列矩陣JM；

2. JSSP染色體的編碼串應(yīng)包括零件加工時(shí)的所有特征，也就是哪一個(gè)工件第幾個(gè)工序，在哪一臺(tái)設(shè)備上加工。只有這樣JSSP染色體的編碼串才可以唯一地映象成一個(gè)設(shè)備工序的排列矩陣JM；

3. JSSP染色體的編碼應(yīng)盡可能地精簡，只有精簡才有利于改進(jìn)遺傳進(jìn)化算法操作的效率。

根據(jù)上述 JSSP染色體的編碼需做到的 3點(diǎn)要求，給出了JSSP染色體編碼的方式。就是單一編碼方式，將所有工件工序進(jìn)行統(tǒng)一的編號(hào)，則文中的調(diào)度問題利用如下方式進(jìn)行表示：

在研究JSSP染色體之后，接下來開始選取初始的種群，隨機(jī)生成A個(gè)位數(shù)，成為nk的染色體串初始的種群，每個(gè)染色體串利用以上方式表示，盡量保持各個(gè)基因間相互獨(dú)立。

為了使改進(jìn)遺傳進(jìn)化算法對(duì)適應(yīng)度比較高的個(gè)體，有更多生存機(jī)會(huì)，利用對(duì)目標(biāo)函數(shù)標(biāo)度，獲得適應(yīng)度函數(shù)其中α和β為常數(shù)。

由于遺傳進(jìn)化一般為雙親繁殖，所以利用這一特點(diǎn)，引入交叉算子，各代的各個(gè)體按照一定交叉概率，交換部分基因，生產(chǎn)新基因組合，用來使各解可以有機(jī)會(huì)對(duì)其優(yōu)秀基因進(jìn)行交流，能夠得到比父代更佳的解結(jié)構(gòu)，也就是最優(yōu)解。

為了使改進(jìn)遺傳進(jìn)化算法，并很好地應(yīng)用于作業(yè)流程調(diào)度中，在交叉算子的基礎(chǔ)上引入了變異算子。變異算子對(duì)各個(gè)體每一位按照一定概率生成新的變化，生成新的基因型，可以進(jìn)一步擴(kuò)大尋優(yōu)范圍，進(jìn)而利于保障算法全局的最優(yōu)性。

2.3 復(fù)雜作業(yè)流程調(diào)度的實(shí)現(xiàn)

以2.1和2.2中內(nèi)容為基礎(chǔ)，在實(shí)現(xiàn)調(diào)度之前，先對(duì)死鎖的概念進(jìn)行介紹。死鎖是在安排某工序加工時(shí)，這個(gè)工序前一道工序還沒有被安排進(jìn)行加工，進(jìn)而造成調(diào)度沒辦法繼續(xù)進(jìn)行的情況。死鎖的問題得以解決，則復(fù)雜作業(yè)流程的調(diào)度問題可以獲得最大優(yōu)化。

圖1 調(diào)度過程流程圖Fig.1 Flow chart of scheduling process

圖2 作業(yè)調(diào)度整體結(jié)構(gòu)流程圖Fig.2 The whole structure flow chart of job scheduling

由此采用無延遲作業(yè)計(jì)劃解決死鎖情況，使每代的個(gè)體代表的解均是近優(yōu)解，進(jìn)而加快迭代的過程收斂速度。這里只簡單介紹死鎖的解決方法，并不作詳細(xì)的探討。得到死鎖的解決辦法后，利用調(diào)度過程流程圖和作業(yè)調(diào)度整體結(jié)構(gòu)流程圖完成對(duì)調(diào)度的研究。

以上就是基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度全解[11][12]，根據(jù)流程圖實(shí)現(xiàn)調(diào)度的準(zhǔn)確高效操作。

3 實(shí)驗(yàn)結(jié)果與分析

為了證明基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度的有效性，需要進(jìn)行一次相關(guān)的實(shí)驗(yàn)與分析。在MATLAB R2015b環(huán)境下搭建復(fù)雜作業(yè)流程調(diào)度實(shí)驗(yàn)平臺(tái)，實(shí)驗(yàn)數(shù)據(jù)取自于JSP。

隨機(jī)生成10個(gè)大規(guī)模JSP算例，其中工件數(shù)集合是[100 150 200]，設(shè)備數(shù)量集合是[20 30 50]，各個(gè)工件操作過程中有5個(gè)工序，各個(gè)工序加工的時(shí)間服從[1 100]均勻分布。隨機(jī)在設(shè)備集合中選取設(shè)備進(jìn)行加工，各工序在加工設(shè)備上只加工一次。

選取100個(gè)工件，和20臺(tái)設(shè)備，利用不同的調(diào)度算法，測試不同算法的調(diào)度性能。表1為不同算法下100*20算例調(diào)度結(jié)果。

分析表1可知，本文算法的拖期時(shí)間和運(yùn)行時(shí)間均少于文獻(xiàn)所提算法。文獻(xiàn)[8]算法的拖期時(shí)間最長，該算法利用作業(yè)分層的優(yōu)先級(jí)生成作業(yè)隊(duì)列，將隊(duì)列內(nèi)的同層作業(yè)在整體上當(dāng)作一位基因進(jìn)行處理，在流程規(guī)劃的同時(shí)沒有指定最小拖期指標(biāo)，導(dǎo)致拖期時(shí)間長。文獻(xiàn)[9]算法調(diào)度運(yùn)行的時(shí)間最長，該算法概述了調(diào)度規(guī)則發(fā)展、特點(diǎn)以及分類，對(duì)調(diào)度規(guī)則選擇與評(píng)價(jià)方法做出總結(jié)，全面介紹調(diào)度規(guī)則選擇方法，沒有明確的約束條件，因此調(diào)度的運(yùn)行時(shí)間相比其它調(diào)度算法較長。本文算法對(duì)調(diào)度的基本約束條件和最小拖期函數(shù)進(jìn)行了研究和分析，建立了數(shù)學(xué)規(guī)劃模型，減少了調(diào)度運(yùn)行時(shí)間，同時(shí)也減少了拖期時(shí)間。上述實(shí)驗(yàn)證明了本文所提算法具有一定的可行性。圖3為不同算法加工時(shí)間（s）對(duì)比。

表1 不同算法調(diào)度性能對(duì)比（100*20）Table 1 Comparison of scheduling performance of different algorithms (100*20)

圖3 不同算法加工時(shí)間對(duì)比Fig.3 Comparison of processing time of different algorithms

由圖3可知，本文調(diào)度算法加工時(shí)間，明顯少于文獻(xiàn)算法加工時(shí)間。因?yàn)樵诶帽疚乃惴▽?shí)現(xiàn)調(diào)度過程中，構(gòu)建了合適的編碼，并對(duì)JSSP染色體的編碼提出了要求，利用雙親繁殖的特點(diǎn)引入交叉算子，在交叉算子基礎(chǔ)上，加入變異算子，優(yōu)化了本文算法調(diào)度精度，由于調(diào)度精度的增加，提高了設(shè)備加工的速度，減少了加工時(shí)間。下面是調(diào)度規(guī)模分別為100*50，150*30，150*20時(shí)，不同算法調(diào)度的負(fù)載均衡度[13]（%）對(duì)比。

通過對(duì)不同算法在不同規(guī)模下的負(fù)載均衡度對(duì)比結(jié)果可知[14]，負(fù)載均衡度越高代表調(diào)度的穩(wěn)定性越好，而表中本文算法的負(fù)載均衡度相比文獻(xiàn)算法的負(fù)載均衡度較高。進(jìn)一步說明了本文算法具有高度可實(shí)踐性和可擴(kuò)展性。

表2 不同算法調(diào)度的負(fù)載均衡度對(duì)比（100*50）Table 2 Comparison of load balancing of different algorithms scheduling (100*50)

表3 不同算法調(diào)度的負(fù)載均衡度對(duì)比（150*30）Table 3 Comparison of load balancing of different algorithms scheduling (150*30)

表4 不同算法調(diào)度的負(fù)載均衡度對(duì)比（150*20）Table 4 Comparison of load balancing of different algorithms scheduling (150*20)

4 結(jié)束語

文中的交叉算子和變異算子使調(diào)度程序可視化程度受到了影響，因此需要與生產(chǎn)企業(yè)的調(diào)度部門所制定的生產(chǎn)流程調(diào)度計(jì)劃進(jìn)行連接，從而可以直接應(yīng)用到生產(chǎn)中。

采用當(dāng)前算法對(duì)復(fù)雜作業(yè)流程進(jìn)行調(diào)度時(shí)，無法對(duì)作業(yè)流程進(jìn)行穩(wěn)定，高效地調(diào)度。而基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度可以實(shí)現(xiàn)作業(yè)流程的可靠調(diào)度，并利用實(shí)驗(yàn)證明，本文所提算法具有實(shí)際意義。

[1] 郭晴, 楊海霞, 劉永泰. 云計(jì)算環(huán)境下的復(fù)雜數(shù)據(jù)庫并行調(diào)度模型仿真[J]. 計(jì)算機(jī)仿真, 2015, 32(6): 360-363.

[2] 翟穎妮, 王軍強(qiáng), 褚崴, 等. 基于TOC理論的大規(guī)模作業(yè)車間調(diào)度問題研究[J]. 機(jī)械科學(xué)與技術(shù), 2015, 34(8):1222-1228.

[3] 閆俊剛, 邢立寧, 張忠山, 等. 具有雙重時(shí)間窗約束的作業(yè)車間調(diào)度算法[J]. 科學(xué)技術(shù)與工程, 2016, 16(26): 85-92.

[4] 劉迷, LiuMi. 云計(jì)算下虛擬信息資源大數(shù)據(jù)特征集成調(diào)度[J]. 科技通報(bào), 2015, 31(10): 199-201.

[5] 孫瓊瓊, 蔡琪. 文化框架下多群智能優(yōu)化算法的云作業(yè)調(diào)度[J]. 計(jì)算機(jī)測量與控制, 2015, 23(1): 273-276.

[6] 劉?？? 李集林, 張華健. 一種改進(jìn)的M-LWDF動(dòng)態(tài)業(yè)務(wù)調(diào)度方法[J]. 電子設(shè)計(jì)工程, 2016, 24(22): 26-29.

[7] 李斌. 面向計(jì)算思維的集裝箱碼頭裝卸作業(yè)調(diào)度[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2016, 16(3): 161-167.

[8] 謝濤, 董滔. 基于混合GA算法的工作流作業(yè)調(diào)度隊(duì)列優(yōu)化[J]. 計(jì)算機(jī)工程與應(yīng)用, 2016, 52(24): 85-90.

[9] 范華麗, 熊禾根, 蔣國璋,等. 動(dòng)態(tài)車間作業(yè)調(diào)度問題中調(diào)度規(guī)則算法研究綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(3):648-653.

[10] 李薛劍, 李凱. 一種基于動(dòng)態(tài)優(yōu)先級(jí)的RQ作業(yè)調(diào)度算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2017, 38(1): 124-128.

[11] 吳瓊, 紀(jì)志成, 吳定會(huì). 協(xié)同混合粒子群算法求解車間作業(yè)調(diào)度問題[J]. 計(jì)算機(jī)工程與應(yīng)用, 2016, 52(5): 266-270.

[12] 馬莉, 唐善成, 王靜, 趙安新. 云計(jì)算環(huán)境下的動(dòng)態(tài)反饋?zhàn)鳂I(yè)調(diào)度算法[J]. 西安交通大學(xué)學(xué)報(bào), 2014, 48(7): 77-82.

[13] 王鵬, 黃焱, 李坤, 郭又銘. 云計(jì)算集群相空間負(fù)載均衡度優(yōu)先調(diào)度算法研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(5):1095-1107.

[14] 翟穎妮, 王軍強(qiáng), 褚崴, 劉昌軍. 基于TOC理論的大規(guī)模作業(yè)車間調(diào)度問題研究[J]. 機(jī)械科學(xué)與技術(shù), 2015, 34(8):1222-1228.

Complex Job Scheduling Based on Improved Genetic Evolution Algorithm

ZHANG Chun-yan
(Wuxi Professional College of Science and Technology, Wuxi 214028)

In order to improve the production speed and quality of the workshop or industry, it is necessary to study the complicated operation process in production. The current algorithm USES the scheduling static solution method and the dynamic optimization method to implement the scheduling of complex job processes. The algorithm is not related to strategy formulation and no effective theory as the support, leading to low efficiency of the algorithm exists scheduling, resource utilization and environmental adaptation ability is poor. In this paper, the complex operation process scheduling based on improving genetic evolutionary algorithm is proposed. The algorithm for complex process scheduling problem is described first, in view of the scheduling problem description, using the improved genetic algorithm for solving job shop scheduling problem, described the problem of mathematical programming model based on the definition of the rules. And then build a suitable encoding to achieve improved genetic evolutionary algorithm run normally, process according to certain requirements for JSSP chromosome coding,choose the initial population, and the fitness function calculation, the introduction of crossover operator and mutation operator for expanding the scope of the optimization. Finally, the problem of deadlock condition was solved by using the non-delayed operation plan, and the scheduling of the whole structure flowchart was implemented by scheduling process flowchart and operation scheduling. The experimental results show that the proposed algorithm made full use of existing resources to achieve the efficient scheduling of complex process, at the same time also has a good adaptability and flexibility.

Genetic evolutionary algorithm; Complex operation process; Scheduling

國家自然科學(xué)基金(61300149)，江蘇高校品牌專業(yè)建設(shè)工程資助項(xiàng)目(Top-notch Academic Programs Project of Jiangsu Higher Education Institutions，TAPP)，江蘇省教育廳高校哲學(xué)社會(huì)科學(xué)研究指導(dǎo)項(xiàng)目(2016SJD880064)

張春燕(1982-)，女，江蘇南通人，講師，碩士，主要研究方向?yàn)槿斯ぶ悄芩惴ㄅc模式識(shí)別，計(jì)算機(jī)控制系統(tǒng)等方面。

TP18

A

10.3969/j.issn.1003-6970.2017.12.019

本文著錄格式：張春燕. 基于改進(jìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度[J]. 軟件，2017，38（12）：98-103