基于改進遺傳算法對車間調度問題的研究?

2020-05-15 05:19:36劉慶閣唐曉彬

計算機與數字工程 2020年2期

曲媛劉慶閣唐曉彬魏驍王碩

（中國船舶重工集團公司第七○三研究所哈爾濱 150060）

1 引言

近年來，隨著科技和行業要求逐步提升，車間調度問題逐漸成為現代制造企業關注的主要問題，同時也是生產制造領域研究的熱點問題之一［1］。車間調度問題屬于非確定性多項式難題，主要針對不同制造企業對生產車間、機器、人員、物流等調度不同，生產周期會隨之變長的問題［2～4］。隨著行業需求的不斷上升，人工排產調度不僅會增強生產成本、延長生產周期，而且會浪費制造企業的部分生產資源［5～6］。同時車間調度問題是計算機集成制造系統工程中的一個重要組成部分，它對企業的生產管理和控制系統有著重要的影響。在當今的競爭環境下，如何利用計算機技術實現生產調度計劃優化，快速調整資源配置，統籌安排生產進度，提高設備利用率已成為許多加工企業面臨的重大課題［7～8］。

遺傳算法是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法［9～11］。其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱并行性和更好的全局尋優能力；采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則［12～13］。遺傳算法的這些性質，已被人們廣泛地應用于組合優化、機器學習、信號處理、自適應控制和人工生命等領域，是現代有關智能計算中的關鍵技術［14］。

2 問題描述

有m個工作臺（5＜m＜10），有n項作業（n＞50），每項作業需要MTi時間（MTi為隨機數）完成，每項作業均在工作臺上完成，請采用優化方法實現這一優化作業方案。本文根據問題的復雜程度不同，給出以下約束條件：

1）每個工作臺對應一道工序；

2）每個作業使用每個工作臺不多于1次；

3）每個作業利用每個工作臺的順序可以不同；

4）No.2、3、4工作臺上所對應的工序加工順序必須滿足先后順序要求：2＞3＞4，后工序不能先于前工序，其他工序無順序要求；

5）任何作業沒有搶先加工的優先權，應服從生產順序調度安排；

6）作業加工過程中沒有新作業加入，也不能臨時取消作業的加工。

根據以上定義和約束條件，要研究的問題是：確定各項作業在各個工作臺的工作順序，給出優化方案，優化生產，得到滿足生產約束條件的較優生產時間。

3 建立模型及目標函數

車間調度問題的調度目的是確定各工作在不同工作臺的工作順序，得到滿足約束條件的較優生產時間，建立車間調度問題的目標函數表示如下：

最小化完工時間f：

式（1）中i表示每個作業i∈｛1，2，…，N｝，j表示每個工作臺j∈｛1，2，…，M｝，t_ij表示第i個工作在第j個工作臺上的工作時間，H_j表示第j個工作臺在開始生產后的未工作時間和，T_j表示第j個工作臺耗時多少結束生產。式（1）表示第j個工作臺的耗時等同于每個工作的工作時間和工作臺未工作的空閑時間的總和。式（2）表示車間調度問題的目標函數即最小化M個工作臺工作時長最大的工作臺的耗時。

由于上述有約束條件：

1）每個工作臺對應一道工序

2）每個作業使用每個工作臺不多于1次

所以有：

式（3）中l代表每道工序l∈｛1，2，…，M｝，由式（3）可知每個工作臺對應一道工序，則一個作業需在每個工作臺加工，且只加工一次。所以l=j且l，j∈｛1，2，…，M｝，j工作臺結束工作即所有工作的第j道工作已完成。M個工作臺均結束任務后即所有工作的M道工序均已完成，生產結束。

3）No.2、3、4工作臺上所對應的工序加工順序必須滿足先后順序要求：2＞3＞4，后工序不能先于前工序，其他工序無順序要求；

所以有：

式（4～5）中 Cij表示第i個工作在第j個機器上加工的開始時間即開始第j個工序的開始時間，式（4）表示，以剛開始生產的時間點為起始點，第i個工作在第2個機器上的開始時間加上第i個工作在第2個機器上的工作時間要小于第i個工作在第3個機器上的開始加工時間。同理，第i個工作在第3個機器上的開始時間加上第i個工作在第3個機器上的工作時間要小于第i個工作在第4個機器上的開始加工時間。

4 改進遺傳算法

4.1 算法描述

本文提出了遺傳退火算法解決生產過程中的車間調度問題，解決不同的約束條件下的調度問題。對車間調度問題進行編碼，創建染色體和初始種群，進行選擇、交叉、變異等一系列操作，得到目標函數值即為適應度函數值。之后進行選擇，交叉，變異操作，再重復評價；在適應度值持續偏差不大后退出循環，輸出適應度最大的解［15～16］。

流程圖見圖1所示。

4.2 編碼與解碼

編碼：利用N個作業在M個工作臺工作構建染色體，一個染色體上基因數量為N×M，是由M個N基因組成。例如：N=3，M=2，則染色體可以為［1，2，3，1，2，3］。

圖1 改進遺傳算法流程圖

解碼：假設此次車間調度問題為N=3，M=2，3個工作的工作編號為1-3，將1-3每個編號均隨機生成2次作為一條染色體記作數組b［6］。假設j=b［i］，i代表要安排的第幾個任務i∈｛1，2，…，N×M｝，j代表第i個安排的任務為第j個工作，b［6］=［1，3，3，2，2，1］，從左至右依次判斷安排工作，b［1］=1則表示第一個要安排的工作為第1個工作，b［2］=3則表示第二個安排的工作為第3個工作。同理安排到b［5］時，b［1］到 b［4］中 i的數量為工作i已完成的工序數目。

4.3 初始化種群

首先隨機生成L條含N×M個基因的染色體構成初始種群，每條染色體代表一個個體，即車間分配任務的一種可行調度。

4.4 適應度計算

根據編碼方式得到j=b［i］判斷可進行當前j工作的工作臺；再從中判斷可用工作臺的運行進程，即之前工作運行結束的結束時間，將當前工作賦給結束時間最小的工作臺；重復上述操作將所有工作安排完成后，記錄各臺機器最終的結束時間，并找出其中結束時間最大的工作臺，將其結束時間進行變換后作為適應度值進行評價。假設有N=60個工作，M=8個工作臺，具體步驟如下：

1）建立e［i］［j］數組存儲工作臺在當前工作完成后各工作臺的工作進程；

2）從b［1］到b［480］順序判斷應放到哪個工作臺上，當j=b［i］］判斷可進行當前j工作的工作臺；

3）當 l=1，2，5，6，7，8時 e［l］［j］為空，即此時 j工作未完成的工序 l，或 l=3時 e［2］［j］不為空，即j工作的2工序已完成，當前可加工3工序，或l=4時e［3］［j］＞e［2］［j］，即 j工作的 3 工序已完成，當前可加工4工序；

4）將當前可加工的工序數存入c［］數組中，c［ii］數組存儲可進行當前工作的工作臺；

5）再計算當前可進行j工作的工作臺的運行進度，將當前工作賦給進度最小的工作臺l，并將該工作j的需工作時間a［j］加上上一時刻l工作臺的結束時間的記入e［l］［j］數組即為此時l工作臺的運行結束時間；

6）num變量存儲當前工作j已完成的工作臺數量，記入f［l］［h］數組（即j工作的完成工序順序）用于輸出；

7）編寫函數Comparetime（），用于將各工作臺的最終結束時間賦給g［ii］數組；

8）編寫函數evaluation（），用于評價遺傳算法，將種群中的染色體按適應度進行排序。

4.5 選擇操作

在遺傳算法中，通常從一個父代種群中選擇一部分遺傳給子代，為避免損失有效基因，所以提高適應度較大的個體被選擇的概率，從而提高算法的收斂效率，降低計算時長。本文采用傳統的輪盤賭的方式來選擇子代染色體，編寫函數selection（），用于選擇個體。

4.6 交叉操作

在遺傳算法中，交叉操作是為了在不發生優質基因損失的情況下產生新的個體，本文中通過交叉兩個父代個體產生兩個新的子代個體，由于編碼方式染色體b［i］中必須含有M個N工作，假設有N=60個工作，M=8個工作臺，即b［i］是由8個1～60的編號組成，任意交叉會破壞染色體結構，使染色體失效，所以本文編寫了函數cross（），用于進行遺傳算法中的交叉操作，交叉操作找出相同的數據段按照原有的順序進行兩段基因的交換到不同的染色體上。