用Python實作基于遺傳算法（GA）求解混合流水工廠中的房間排程問題（HFSP）

之前一直研究的是柔性作業工廠中的房間排程問題，研究彙總如下：

用python實作基于遺傳算法求解柔性作業工廠中的房間排程問題代碼實作（包括标準算例準換、編碼、解碼、交叉、變異的詳細講述） 

用python實作基于蟻群算法求解帶準備時間的雙資源限制柔性作業工廠中的房間排程問題

用Python實作帶運輸時間準備時間的MSOS染色體解碼(FJSP)

Tensorflow2.0|基于深度強化學習（DQN）實作動态柔性作業工廠中的房間排程問題（DFJSP）

用Python實作論文《考慮裝卸的柔性作業工廠中的房間雙資源排程問題》的降準解碼算法

今天，來講述并一下HFSP問題,并給出相應的代碼實作。

1 問題描述

        混合流水工廠中的房間（又稱柔性流水工廠中的房間）在流水工廠中的房間的基礎上，在所有或部分階段引入多台可選擇的并行機器，提高了工廠中的房間地生産能力和柔性，是工廠中的房間排程領域研究的熱點之一。HFSP問題可以描述為：n 個工件在(c≥２)個階段上進行連續加工,階段i有mi(mi ≥１;i＝１,２,...,c)台機器,且至少存在一個階段有多台機 器.HFSP需要根據各階段上工件的加工順序和機器配置設定,來優化某項或多項性能名額.圖１為HFSP工廠中的房間布局圖.

         HFSP與其他問題的差別：

         擴充HFSP的分類與定義：

HFSP常用的目标函數：

（1）完工時間

（2）流經時間

（3）工件延遲

（4）工作負荷

（5）總能耗

       ... ...

本文的目标函數為：最小化完工時間

2 算法

         遺傳算法對于入門是非常有好的，其他類似進化算法幾乎都是在此基礎上演變的，當你懂得遺傳算法的邏輯和思路以後，上手其他算法就很快了，是以還是本文還是決定用遺傳算法來求解。

2.1 初始化

2.1.1 編碼

        目前大多數求解 ＨＦＳＰ的算法都采用的是基于工件排 列的編碼方法，即用 犖 個工件排成順序隊列，工件在隊列 中的位置标明工件第一道工序的加工順序。鑒于後續階段 工件的加工受上一階段影響較大，也采用此方法，後續階段 則根據前一階段工件加工完成時間采用非降序排列的方式 進行編碼。舉例說明，例如５個工件的編碼 為（４，２，５，１， ３），此編碼标明在第一加工階段，工件４先加工，緊接着工 件２加工、其次是５、再是１、最後是工件３加工。若它們在 第一階段加工完成到達第二階段的順序依次為２、５、４、１、３， 則在 第 二 階 段 的 編 碼 為 （２，５，４，１，３），後 續 階 段 的 編 碼 同理。

 2.1.2 解碼

        對于上述編方法，采用如下解碼算法可以構造一個排程方案 ：

        步驟 1   對每個工件每道工序的所有可用機器計算目前工序的開始時間、完成時間 、加工時間和目前機器負載。計算工序的開始時間時，需要比較該工件上道工序的完成時間 (TP)和該機器 所加工的上道工序的完成時間(TM)。若TM≥TP，且在該機器上TP與TM之間存在大于該工序加工 時間的空隙，則可将該工序插入空隙内，開始時間為空隙中前一道工序的結束時間；若TM<TP，則開始時間為TP。

        步驟2     選擇機器。優取原則為：優先選取完成時間最小的機器；若完成時間相同，則選取目前機器負載最小的機器；若機器負載也都相同，則随機選取機器。即優先級為完成時間>機器負載 。

        步驟3  判斷是否所有工件的所有工序都已進行機器選擇。若已選擇 ，則結束循環，輸出排程方案；否則，傳回步驟1.

交叉方式：POX

變異：打亂互換

3 代碼

3.1 Instance

import random
random.seed(32)

#State:階段，即工件有幾道工序，Job:工件數，Machine['type':list],對應各階段的并行機數量
def Generate(State,Job,Machine):
    PT=[]
    for i in range(State):
        Si=[]       #第i各加工階段
        for j in range(Machine[i]):
            S0=[random.randint(1,20) for k in range(Job)]
            Si.append(S0)
        PT.append(Si)
    return PT

Job=20
State=5
Machine=[3,3,2,3,3]

PT=Generate(State,Job,Machine)
           

3.2 Scheduling 

import random
import matplotlib.pyplot as plt
from Instance import Job,State,Machine,PT
import numpy as np


class Item:
    def __init__(self):
        self.start=[]
        self.end=[]
        self._on=[]
        self.T=[]
        self.last_ot=0
        self.L=0

    def update(self,s,e,on,t):
        self.start.append(s)
        self.end.append(e)
        self._on.append(on)
        self.T.append(t)
        self.last_ot=e
        self.L+=t

class Scheduling:
    def __init__(self,J_num,Machine,State,PT):
        self.M=Machine
        self.J_num=J_num
        self.State=State
        self.PT=PT
        self.Create_Job()
        self.Create_Machine()
        self.fitness=0

    def Create_Job(self):
        self.Jobs=[]
        for i in range(self.J_num):
            J=Item()
            self.Jobs.append(J)

    def Create_Machine(self):
        self.Machines=[]
        for i in range(len(self.M)):    #突出機器的階段性，即各階段有哪些機器
            State_i=[]
            for j in range(self.M[i]):
                M=Item()
                State_i.append(M)
            self.Machines.append(State_i)

    #每個階段的解碼
    def Stage_Decode(self,CHS,Stage):
        for i in CHS:
            last_od=self.Jobs[i].last_ot
            last_Md=[self.Machines[Stage][M_i].last_ot for M_i in range(self.M[Stage])] #機器的完成時間
            last_ML = [self.Machines[Stage][M_i].L for M_i in range(self.M[Stage])]     #機器的負載
            M_time=[self.PT[Stage][M_i][i] for M_i in range(self.M[Stage])]             #機器對目前工序的加工時間
            O_et=[last_Md[_]+M_time[_] for _ in range(self.M[Stage])]
            if O_et.count(min(O_et))>1 and last_ML.count(last_ML)>1:
                Machine=random.randint(0,self.M[Stage])
            elif O_et.count(min(O_et))>1 and last_ML.count(last_ML)<1:
                Machine=last_ML.index(min(last_ML))
            else:
                Machine=O_et.index(min(O_et))
            s, e, t=max(last_od,last_Md[Machine]),max(last_od,last_Md[Machine])+M_time[Machine],M_time[Machine]
            self.Jobs[i].update(s, e,Machine, t)
            self.Machines[Stage][Machine].update(s, e,i, t)
            if e>self.fitness:
                self.fitness=e

    #解碼
    def Decode(self,CHS):
        for i in range(self.State):
            self.Stage_Decode(CHS,i)
            Job_end=[self.Jobs[i].last_ot for i in range(self.J_num)]
            CHS = sorted(range(len(Job_end)), key=lambda k: Job_end[k], reverse=False)

    #畫甘特圖
    def Gantt(self):
        fig = plt.figure()
        M = ['red', 'blue', 'yellow', 'orange', 'green', 'moccasin', 'purple', 'pink', 'navajowhite', 'Thistle',
             'Magenta', 'SlateBlue', 'RoyalBlue', 'Aqua', 'floralwhite', 'ghostwhite', 'goldenrod', 'mediumslateblue',
             'navajowhite','navy', 'sandybrown']
        M_num=0
        for i in range(len(self.M)):
            for j in range(self.M[i]):
                for k in range(len(self.Machines[i][j].start)):
                    Start_time=self.Machines[i][j].start[k]
                    End_time=self.Machines[i][j].end[k]
                    Job=self.Machines[i][j]._on[k]
                    plt.barh(M_num, width=End_time - Start_time, height=0.8, left=Start_time, \
                             color=M[Job], edgecolor='black')
                    plt.text(x=Start_time + ((End_time - Start_time) / 2 - 0.25), y=M_num - 0.2,
                             s=Job+1, size=15, fontproperties='Times New Roman')
                M_num += 1
        plt.yticks(np.arange(M_num + 1), np.arange(1, M_num + 2), size=20, fontproperties='Times New Roman')

        plt.ylabel("機器", size=20, fontproperties='SimSun')
        plt.xlabel("時間", size=20, fontproperties='SimSun')
        plt.tick_params(labelsize=20)
        plt.tick_params(direction='in')
        plt.show()
#
# Sch=Scheduling(J_num,Machine,State,PT)

           

3.3  GA

import random
import numpy as np
import copy
from Scheduling import Scheduling as Sch
from Instance import Job,State,Machine,PT
import matplotlib.pyplot as plt

class GA:
    def __init__(self,J_num,State,Machine,PT):
        self.State=State
        self.Machine=Machine
        self.PT=PT
        self.J_num=J_num
        self.Pm=0.2
        self.Pc=0.9
        self.Pop_size=100

    # 随機産生染色體
    def RCH(self):
        Chromo = [i for i in range(self.J_num)]
        random.shuffle(Chromo)
        return Chromo

    # 生成初始種群
    def CHS(self):
        CHS = []
        for i in range(self.Pop_size):
            CHS.append(self.RCH())
        return CHS

    #選擇
    def Select(self, Fit_value):
        Fit = []
        for i in range(len(Fit_value)):
            fit = 1 / Fit_value[i]
            Fit.append(fit)
        Fit = np.array(Fit)
        idx = np.random.choice(np.arange(len(Fit_value)), size=len(Fit_value), replace=True,
                               p=(Fit) / (Fit.sum()))
        return idx

    # 交叉
    def Crossover(self, CHS1, CHS2):
        T_r = [j for j in range(self.J_num)]
        r = random.randint(2, self.J_num)  # 在區間[1,T0]内産生一個整數r
        random.shuffle(T_r)
        R = T_r[0:r]  # 按照随機數r産生r個互不相等的整數
        # 将父代的染色體複制到子代中去，保持他們的順序和位置
        H1=[CHS1[_] for _ in R]
        H2=[CHS2[_] for _ in R]
        C1=[_ for _ in CHS1 if _ not in H2]
        C2=[_ for _ in CHS2 if _ not in H1]
        CHS1,CHS2=[],[]
        k,m=0,0
        for i in range(self.J_num):
            if i not in R:
                CHS1.append(C1[k])
                CHS2.append(C2[k])
                k+=1
            else:
                CHS1.append(H2[m])
                CHS2.append(H1[m])
                m+=1
        return CHS1, CHS2

    # 變異
    def Mutation(self, CHS):
        Tr = [i_num for i_num in range(self.J_num)]
        # 機器選擇部分
        r = random.randint(1, self.J_num)  # 在變異染色體中選擇r個位置
        random.shuffle(Tr)
        T_r = Tr[0:r]
        K=[]
        for i in T_r:
            K.append(CHS[i])
        random.shuffle(K)
        k=0
        for i in T_r:
            CHS[i]=K[k]
            k+=1
        return CHS

    def main(self):
        BF=[]
        x=[_ for _ in range(self.Pop_size+1)]
        C=self.CHS()
        Fit=[]
        for C_i in C:
            s=Sch(self.J_num,self.Machine,self.State,self.PT)
            s.Decode(C_i)
            Fit.append(s.fitness)
        best_C = None
        best_fit=min(Fit)
        BF.append(best_fit)
        for i in range(self.Pop_size):
            C_id=self.Select(Fit)
            C=[C[_] for _ in C_id]
            for Ci in range(len(C)):
                if random.random()<self.Pc:
                    _C=[C[Ci]]
                    CHS1,CHS2=self.Crossover(C[Ci],random.choice(C))
                    _C.extend([CHS1,CHS2])
                    Fi=[]
                    for ic in _C:
                        s = Sch(self.J_num, self.Machine, self.State, self.PT)
                        s.Decode(ic)
                        Fi.append(s.fitness)
                    C[Ci]=_C[Fi.index(min(Fi))]
                    Fit.append(min(Fi))
                elif random.random()<self.Pm:
                    CHS1=self.Mutation(C[Ci])
                    C[Ci]=CHS1
            Fit = []
            Sc=[]
            for C_i in C:
                s = Sch(self.J_num, self.Machine, self.State, self.PT)
                s.Decode(C_i)
                Sc.append(s)
                Fit.append(s.fitness)
            if min(Fit)<best_fit:
                best_fit=min(Fit)
                best_C=Sc[Fit.index(min(Fit))]
            BF.append(best_fit)
        plt.plot(x,BF)
        plt.show()
        best_C.Gantt()

if __name__=="__main__":
    g=GA(Job,State,Machine,PT)
    g.main()
           

4 實驗結果