基于遺傳算法的車間產(chǎn)線自動編排研究與實(shí)踐

呂永桂 金遠(yuǎn)帆 高平波 鐘波

摘要：本文設(shè)計并開發(fā)了一款面向服裝工廠的基于遺傳算法的高級計劃排程系統(tǒng)，針對傳統(tǒng)制造業(yè)如今面臨的訂單為多品種，個性化，小批量的現(xiàn)狀，可以輔助管理人員根據(jù)訂單，產(chǎn)線生產(chǎn)效率等因素快速而精準(zhǔn)的制定生產(chǎn)計劃，較大的提高了服裝企業(yè)對生產(chǎn)資源的利用率，減小了訂單延期的情況，使得企業(yè)擁有更強(qiáng)的競爭力。

關(guān)鍵詞：高級計劃排程;遺傳算法;自動編排

隨著電子商務(wù)在全球范圍內(nèi)持續(xù)繁榮，客戶的需求變得日趨個性化，如何針對客戶的個性化需求迅速制定精準(zhǔn)的生產(chǎn)計劃已經(jīng)成為了服裝加工制造企業(yè)不能不面對的問題。據(jù)相關(guān)統(tǒng)計，我國服裝產(chǎn)業(yè)中，中小企業(yè)數(shù)量占據(jù)服裝企業(yè)總數(shù)比例高達(dá)90%以上。對于多品種、小批量生產(chǎn)模式的企業(yè)，如何合理的安排生產(chǎn)計劃一直是一個難題。因?yàn)橛唵蔚钠贩N，所以排程時的計算量較大，而批量小又會導(dǎo)致頻繁換線。在既保持多品種，小批量的模式下，又能及時地滿足客戶快速變化的需求成為了檢驗(yàn)中小服裝企業(yè)競爭力的標(biāo)志。傳統(tǒng)的ERP（企業(yè)資源計劃）在為企業(yè)整合生產(chǎn)資源的同時，面對離散制造的生產(chǎn)狀況具有明顯的缺陷。

目前，生產(chǎn)過程中的自動排產(chǎn)技術(shù)在眾多離散生產(chǎn)領(lǐng)域得到了廣泛的應(yīng)用，但在服裝生產(chǎn)過程中鮮有運(yùn)用，本文給出了一種基于遺傳算法的優(yōu)化生產(chǎn)的排產(chǎn)解決方案。

1 服裝車間生產(chǎn)作業(yè)調(diào)度

作業(yè)車間調(diào)度問題（JSSP）可以描述如下：給定n個作業(yè)，每個作業(yè)包含必須在m臺機(jī)器上處理的幾個工序。每個工序使用m臺機(jī)器中的一臺以固定的時間進(jìn)行加工。每臺機(jī)器一次最多只能處理一個工序，并且一旦工序在給定機(jī)器上啟動處理，它就必須在該機(jī)器上不中斷的完成的處理。同一個作業(yè)的工序必須以給定順序進(jìn)行處理，調(diào)度開始時，所有工序都是空閑且可用的。最終所要求解的是最短的制造期，即計劃中最后一次操作的完成時間，同時安排的順序要考慮到工序先后順序的約束。

用J={0，1，....n，n+1）表示要調(diào)度的操作集，而M={1，....m）表示機(jī)器集，操作集沒有持續(xù)時間，代表初始和最終的操作，操作通過兩個約束互相關(guān)聯(lián)，首先，第一個約束令每個操作在需在所有前置操作Pj完成之后進(jìn)行調(diào)度，其次，當(dāng)且僅當(dāng)操作所需要的機(jī)器處于空閑狀態(tài)時，才可以調(diào)度該操作。用dj表示操作j在機(jī)器上所需要的持續(xù)處理時間。

用Fj表示操作完成的時間，（Fi，F(xiàn)m，...，F(xiàn)n+1）表示時間表，假設(shè)A（t）是在時間t時要處理的一組操作，如杲操作j需要機(jī)器m進(jìn)行加工，則令fj，m -1，否則令fj，m=0。

最終該問題可以用數(shù)學(xué)公式表示：

2 面向服裝產(chǎn)業(yè)自動排產(chǎn)的改進(jìn)遺傳算法

2.1問題建模

根據(jù)遺傳算法的步驟和服裝產(chǎn)業(yè)的特點(diǎn)對車間作業(yè)調(diào)度問題進(jìn)行數(shù)學(xué)建模。保存所需排程的訂單號和產(chǎn)線號，關(guān)聯(lián)訂單在對應(yīng)產(chǎn)線所需的生產(chǎn)時間，通過一維數(shù)組保存每個產(chǎn)線的最后生產(chǎn)時間，用另一個一維數(shù)組記錄每個訂單的開始作業(yè)時間和結(jié)束時間。

2.2 編碼和解碼

2.2.1編碼

采用符號編碼的方式，將訂單序號隨機(jī)生成OS系列，按訂單的序號作為MS的序號，順序在可選產(chǎn)線中隨機(jī)選擇產(chǎn)線，最終生成MS序列。

2.2.2解碼

從左到右遍歷OS序列，由OS序列確定訂單號，然后對應(yīng)MS處的值確定該訂單的生產(chǎn)產(chǎn)線，再由訂單號和產(chǎn)線號，獲得該訂單在該產(chǎn)線所需的生產(chǎn)時間。

2.3 初始化種群

在指定的訂單數(shù)量和產(chǎn)線數(shù)量下，由隨機(jī)生成對應(yīng)的OS和MS序列，組成一條染色體，對于不同的訂單數(shù)量，生成不同數(shù)目的種群。

2.4適應(yīng)度計算

2.4.1排程要求為總生產(chǎn)時間最短

依據(jù)解碼方案，將染色體解碼成可執(zhí)行的排程序列，統(tǒng)計各個產(chǎn)線的總生產(chǎn)時間，最大的值就是最大總生產(chǎn)時間。適應(yīng)度為最大總生產(chǎn)時間的倒數(shù)。

2.4.2排程要求為總寬裕時間最大

定義寬裕時間為訂單的預(yù)定交期和實(shí)際生產(chǎn)完成時間之差，則總寬裕度為：

2.5 選擇

采用精英保留法，并提出了一種分層交叉的方法，同時對父類進(jìn)行近親刪除。

2.5.1精英保留法

對于當(dāng)前種群適應(yīng)度前15%的個體，直接保留進(jìn)入下一代種群。

2.5.2 分層交叉法

采用分層策略提高收斂速度同時保留多樣性：

（1）精英之間的交叉增加收斂速度。

（2）精英（或中層）和底層的交叉增加搜索范圍和收斂精度，

如果兩個父類染色體的適應(yīng)度相同，且r>0.95*n，這兩個將被認(rèn)定為近親，隨機(jī)刪除一條染色體進(jìn)行重新選擇。

2.6交叉和變異

對于OS采用的順序交叉算子，以保證基因變化后的序列不存在重復(fù)訂單。由于MS設(shè)計的特殊性，單個基因的變化不會影響到其余基因的正常性和合法性。所以采用兩點(diǎn)交叉法，大大地降低了單個工序在多機(jī)器中選擇一個進(jìn)行處理的難度。

對OS采用逆轉(zhuǎn)變異算子，互換染色體中不同部位的基因，MS采用基本位變異算子，對隨機(jī)部位的基因在可選機(jī)器序列上重新生成隨機(jī)數(shù)。

2.7停止條件

當(dāng)n代未生成適應(yīng)度更高的個體或者達(dá)到給定的迭代次數(shù)時，停止算法。

3 系統(tǒng)軟件設(shè)計

本系統(tǒng)采用B/S模式，系統(tǒng)流程如圖1所示。APS系統(tǒng)被分為3個模塊，分別為數(shù)據(jù)存儲模塊，業(yè)務(wù)邏輯模塊以及圖形用戶界面模塊。數(shù)據(jù)存儲模塊主要由關(guān)系數(shù)據(jù)庫Mysql將產(chǎn)線、員工、遺傳參數(shù)模型、訂單信息、訂單產(chǎn)線產(chǎn)能以及最終排程記錄以表的形式進(jìn)行存儲。業(yè)務(wù)邏輯模塊除了將圖形界面模塊傳入的數(shù)據(jù)存入數(shù)據(jù)庫之外，還負(fù)責(zé)根據(jù)用戶輸入的加工任務(wù)信息以及遺傳參數(shù)模型和排程要求求得最終的排程結(jié)果，該邏輯模塊為系統(tǒng)核心，同時還負(fù)責(zé)對車間動態(tài)環(huán)境做出合適的調(diào)整，圖形用戶模塊負(fù)責(zé)用戶瀏覽器的頁面顯示，以清晰的操作頁面方便用戶使用，降低系統(tǒng)的使用難度。系統(tǒng)需要考慮實(shí)際生產(chǎn)情況中產(chǎn)線、員工的制約，同時還有訂單的交期以及車間中的動態(tài)狀況，最終將多個訂單和多個產(chǎn)線的排程任務(wù)生成一條可行的車間生產(chǎn)計劃，同時轉(zhuǎn)化為甘特圖在瀏覽器端進(jìn)行顯示。

本文設(shè)計的系統(tǒng)邏輯為：用戶使用瀏覽器通過前端為數(shù)據(jù)庫錄入訂單信息表，員工表，產(chǎn)線表，遺傳參數(shù)模型表，然后通過之前錄入的信息，計算訂單在對應(yīng)產(chǎn)線的產(chǎn)能以及所需生產(chǎn)時間來創(chuàng)建訂單產(chǎn)線產(chǎn)能表。最后，進(jìn)行生產(chǎn)排程時，前端以form表單的形式，將所需排程的訂單，產(chǎn)線，以及遺傳參數(shù)模型提交給服務(wù)器，服務(wù)器從數(shù)據(jù)庫讀取對應(yīng)訂單在產(chǎn)線的產(chǎn)能和生產(chǎn)時間，經(jīng)過相應(yīng)的數(shù)據(jù)處理后，使用遺傳算法進(jìn)行排程，然后將最佳的排程結(jié)果存入排程記錄表，同時根據(jù)排程結(jié)果，生產(chǎn)甘特圖，客戶通過瀏覽器讀取生成的甘特圖，可視化的了解排程結(jié)果。同時該系統(tǒng)還支持管理人員根據(jù)車間動態(tài)環(huán)境：如插單，撤單等進(jìn)行再排程。

4 自動排產(chǎn)軟件實(shí)踐

管理人員可以點(diǎn)擊右上角開始新建排程，默認(rèn)計劃所排程的產(chǎn)線都是空閑可立即生產(chǎn)的。打開的新建排程頁面如圖2所示，管理人員勾選所需排程的訂單，已完成的訂單和正在生產(chǎn)的訂單不在此處顯示，同時勾選所計劃將訂單安排的產(chǎn)線，然后選擇對應(yīng)的遺傳參數(shù)模型，以及排程要求，不同的排程要求對應(yīng)不同的適應(yīng)度計算規(guī)則（詳見2.3的適應(yīng)度計算），適應(yīng)度函數(shù)可以依據(jù)工廠的實(shí)際情況，進(jìn)行再調(diào)整。最后點(diǎn)擊確定，將數(shù)據(jù)以form的形式傳入服務(wù)器進(jìn)行計算。

當(dāng)車間已經(jīng)開始生產(chǎn)時，所遇到的問題屬于車間動態(tài)情況，如插單，撤單等情況，以插單例，管理人員可以點(diǎn)擊右上角的另一個按鈕新建插單，可以對未生產(chǎn)的訂單進(jìn)行重新模擬排程，此次模擬排程和新建排程相同，但程序會在所選產(chǎn)線上正在生產(chǎn)的訂單的計劃完成時間基礎(chǔ)上進(jìn)行后續(xù)排程，不影響產(chǎn)線上的正常工作。

當(dāng)模擬排程的排程狀態(tài)為完成后，除了點(diǎn)擊排程結(jié)果表可以查看具體的排程信息外，還可以點(diǎn)擊甘特圖按鈕來獲取本次排程所生成的甘特圖地址。將復(fù)制地址輸入文件夾對應(yīng)位置，即可打開本次排程所生成的總排程結(jié)果以及各個產(chǎn)線的各自排程結(jié)果，如圖3所示。隨后由圖4所示的甘特圖了解各個產(chǎn)線的排程結(jié)果。

當(dāng)管理人員通過甘特圖以及排程結(jié)果表了解此排程結(jié)果并對此次排程結(jié)果表示滿意，可以點(diǎn)擊編輯按鈕，如圖5所示，將此次草擬排程結(jié)果確定為實(shí)際生產(chǎn)排程，確定后該排程結(jié)果將從草擬APS排程頁面消失，只出現(xiàn)在實(shí)際APS排程中。同時，后臺也會自動將該排程結(jié)果中對應(yīng)訂單的訂單信息表中計劃排程產(chǎn)線，開始日期以及結(jié)束日期更新為該排程結(jié)果的值。

實(shí)際APS排程的記錄是實(shí)際車間生產(chǎn)的重要依據(jù)。該頁面相比于草擬APS排程，去掉了新建排程和新建插單按鈕，以及編輯按鈕，只做顯示和刪除功能，由于草擬APS排程會存在許多模擬訂單，所以為了方便管理人員查看，同時也為了頁面的整潔，將兩者分為兩個頁面顯示。每一條記錄的格式等同草擬APS排程，可以查看該條記錄的排程訂單，排程產(chǎn)線，排程結(jié)果表以及甘特圖。

5 結(jié)語

本文運(yùn)用改進(jìn)的遺傳算法，設(shè)計并開發(fā)了一款服裝智能工廠的自動排產(chǎn)系統(tǒng)，能實(shí)現(xiàn)在給定約束條件下的服裝生產(chǎn)產(chǎn)線的訂單自動編排.具有較好的效率。

參考文獻(xiàn)

[1]馬永杰，云文霞，遺傳算法研究進(jìn)展[J].計算機(jī)應(yīng)用研究，2012，29 （04）： 12 01-12 06+1210.

[2] HOLLAND，J. Adaptation in na tural

and artif icialsystems： an introductory analysis with application tobiology [J]. Control&Artificial Intelligence， 1975.

[3]余琦瑋，趙亮，潘雙夏，基于遺傳算法的柔性作業(yè)車間調(diào)度優(yōu)化[J].組合機(jī)床與自動化加工技術(shù)，2004 （04）：34-36.

[4]陶澤，張海濤.基于遺傳算法的Job-Shop調(diào)度問題研究[J].沈陽理工大學(xué)學(xué)報，2016，35 （02）：60-64.

[5]蔣麗雯，基于遺傳算法的車間作業(yè)調(diào)度問題研究[D].上海交通大學(xué)，2007.

[6]lmran A. Chaudhry， Abdul Munem Khan， Abid Ali Khan. AGenetic Algorithm for Flexible Job Shop Scheduling [J].Lecture Notes in Engineering&Computer ence， 2013，2204 （1）：2 995-3013.

作者簡介

呂永桂（1976一），男，江蘇省興化市人。博士，杭州電子科技大學(xué)機(jī)械學(xué)院副教授，碩導(dǎo)。研究方向?yàn)橹悄苤窃炫c物聯(lián)網(wǎng)。

金遠(yuǎn)帆（1995-），男，浙江省紹興市人。碩士學(xué)位，杭州電子科技大學(xué)機(jī)械學(xué)院碩士研究生。研究方向?yàn)橹悄苤窃臁?/p>

高平波（1980-），男，土家族，湖北省宜昌市人。碩士學(xué)位，杭州邁的智能科技有限公司首席科學(xué)家。研究方向?yàn)楣I(yè)互聯(lián)網(wǎng)。

鐘波（1987-），男，浙江省奉化市人。大學(xué)本科學(xué)歷，杭州邁的智能科技有限公司總經(jīng)理。研究方向?yàn)楣I(yè)互聯(lián)網(wǎng)。