用Python实现带运输时间准备时间的MSOS染色体解码(FJSP)
程序员文章站
2022-07-02 22:38:40
解码方式我以前的文章里写了用改进遗传算法实现FJSP问题的MSOS的编码方式以及以此编码方式的解码方式，这篇文章，我将以此为基础，描述带有运输时间、准备时间的如何解码。参考文献为：[An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints](https://doi.org/10.1016/j.swevo.2020.100664)案例先给一个4*5的...
解码方式
**我以前的文章里写了用改进遗传算法实现FJSP问题的MSOS的编码方式以及以此编码方式的解码方式，这篇文章，我将以此为基础，描述带有运输时间、准备时间的如何解码。参考文献为：[An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints](https://doi.org/10.1016/j.swevo.2020.100664)**
我以前的文章里写了用改进遗传算法实现FJSP问题的MSOS的编码方式以及以此编码方式的解码方式，这篇文章，我将以此为基础，描述带有运输时间、准备时间的如何解码。参考文献为：An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints
案例
先给一个4*5的案列，如下（为所给参考文献中的）：
step1
首先，将MS部分解码成3个矩阵，分别为：机器矩阵、运输时间矩阵、加工时间矩阵、准备时间矩阵，解码后结果如下图所示：
step2
对OS部分进行解码，解码过程如下（解码方式为全插入，即找所有可能的时间窗间隙，如果时间窗间隙大小适合，则插入），此处直接上文章中的步骤：
代码
主要解码代码如下（注：为非完全代码）：
#测试例子1
from Instance1 import Processing_time,Setup_time,Transpotation_time,M_num,O_Max_len,J_num
import numpy as np
import random
from GA import GA
import matplotlib.pyplot as plt
g=GA(J_num,O_Max_len,Processing_time,M_num)
# 染色体解码
#得到解码的几个矩阵：加工时间矩阵、准备时间矩阵、运输时间矩阵
def Decode_Matrix(CHS,Processing_time,Setup_time,Transpotation_time,M_num,O_Max_len,J_num):
Half_Chromosome_length=J_num*O_Max_len
# 初始化几个矩阵
JM = np.zeros((J_num, O_Max_len), dtype=int) # JM(j,h)表示工件Ji的工序Oh的机器号
T_P = np.zeros((J_num, O_Max_len), dtype=int) # T（j,h）表示工件Jj的工序Oh的加工时间
T_S = np.zeros((J_num, O_Max_len), dtype=int) # T（j,h）表示工件Jj的工序Oh的准备时间
T_T = np.zeros((J_num, O_Max_len), dtype=int) # T（j,h）表示工件Jj的工序Oh的运输时间
for i in range(len(CHS)):
MS = CHS[0:Half_Chromosome_length]
OS = CHS[Half_Chromosome_length:2 * Half_Chromosome_length]
GX_num = 0
#加工时间矩阵
for J_j in MS: # 将机器选择部分转换成机器顺序矩阵和时间顺序矩阵
GX_num += 1
JM_j = int((GX_num - 1) / O_Max_len) # 机器顺序矩阵的横坐标
JM_h = int((GX_num - 1) % O_Max_len) # 机器顺序矩阵的纵坐标
O_j = np.array(Processing_time[JM_j][JM_h])
Mac_using = []
Mac_time = []
for Mac_num in range(len(O_j)): # 寻找MS对应部分的机器时间和机器顺序
if O_j[Mac_num] != 9999:
Mac_using.append(Mac_num)
Mac_time.append(O_j[Mac_num])
else:
continue
JM[JM_j][JM_h] += Mac_using[J_j - 1] # 机器顺序矩阵
T_P[JM_j][JM_h] += Mac_time[J_j - 1] # 时间顺序矩阵
#准备时间矩阵和运输时间矩阵
for i in range(len(JM)):
last = None
for j in range(len(JM[i])):
T_S[i][j]=Processing_time[i][j][JM[i][j]]
now=JM[i][j]
if last==None:
T_T[i][0]=0
else:
T_T[i][j]=Transpotation_time[last][now]
last=now
# 步骤2：按照步骤1对应的T和JM依次得到每个工件工序对应的加工机器和加工时间
#加工时间位于第一位、准备时间位于第二位、运输时间位于第三位
Start_time = np.zeros((M_num, Half_Chromosome_length), dtype=int)
End_time = np.zeros((M_num, Half_Chromosome_length), dtype=int)
#准备时间
S_start=np.zeros((M_num, Half_Chromosome_length), dtype=int) # 机器结束加工的时间
S_end=np.zeros((M_num, Half_Chromosome_length), dtype=int) # 机器结束加工的时间
#运输时间
T_start=np.zeros((M_num, Half_Chromosome_length), dtype=int) # 机器结束加工的时间
T_end=np.zeros((M_num, Half_Chromosome_length), dtype=int) # 机器结束加工的时间
Counter_List = []
T_count = 0
for OS_j in OS: # 通过机器顺序矩阵和时间顺序矩阵的到工序的加工机器和加工时间
Counter_List.append(OS_j)
M_i_h = Counter_List.count(OS_j) # 该工件的第几道工序
M_i = JM[OS_j - 1][M_i_h - 1] # 这道工序使用的机器
P_ij = T_P[OS_j - 1][M_i_h - 1] # 这道工序的加工时间
S_ij=T_S[OS_j - 1][M_i_h - 1] # 这道工序的准备时间
T_ij=T_T[OS_j - 1][M_i_h - 1] # 这道工序的运输时间
OS_site = (OS_j - 1) * O_Max_len + M_i_h - 1
# 确定工序为机器的第几道加工工序
M_n_list = [[M_n, End_time[M_i][M_n]] for M_n in range(len(End_time[M_i])) if End_time[M_i][M_n] != 0]
# Oij为工件的第一道加工工序，且是机器M_i的第一道加工工序，直接从机器M_i的零时刻进行加工
if M_i_h == 1 and len(M_n_list) == 0:
S_start[M_i][OS_site]=0
S_end[M_i][OS_site] += S_ij
T_start[M_i][OS_site]=0
T_end[M_i][OS_site] = 0
Start_time[M_i][OS_site] = S_end[M_i][OS_site]
End_time[M_i][OS_site] = Start_time[M_i][OS_site]+P_ij
# 工序O_jh是机器M_i的第一道工序，不是工件的第一道工序，从上道工序完工时间处开始加工
elif len(M_n_list) == 0 and M_i_h > 1:
# 寻找该工件上一道工序的完工时间：
SD_Machine = JM[OS_j - 1][M_i_h - 2] # 上道工序的加工机器
S = End_time[SD_Machine][OS_site - 1] # 该工序上道工序完工时间
if SD_Machine!=M_i:
T_ij=Transpotation_time[SD_Machine][M_i]
T_start[M_i][OS_site] = S
T_end[M_i][OS_site] = T_start[M_i][OS_site] + T_ij
S_start[M_i][OS_site] = T_end[M_i][OS_site]
S_end[M_i][OS_site] = S_start[M_i][OS_site] + S_ij
else: #如果前后两道工序为同一道工序，后面的工序不需再有准备时间
T_ij=0
T_start[M_i][OS_site] = S
T_end[M_i][OS_site] = T_start[M_i][OS_site] + T_ij
S_start[M_i][OS_site] = T_end[M_i][OS_site]
S_end[M_i][OS_site] = S_start[M_i][OS_site]
Start_time[M_i][OS_site] = S_end[M_i][OS_site] #运输过来、准备完毕、即可进行该工序的加工
End_time[M_i][OS_site] = Start_time[M_i][OS_site] + P_ij
# 工序不是机器的第一道工序，是工件的第一道工序
elif len(M_n_list) != 0 and M_i_h == 1:
T_ij=0 #只要是第一道工序，即可不考虑运输时间 ######后续可加入考虑首道工序的运输时间，一个收发地######
T_start[M_i][OS_site]=0
T_end[M_i][OS_site]=0
Max_setup = np.max(S_end[M_i]) # 这道工序再该机器上最晚开始加工的时间
'''
先找一个空隙将准备工作做好
'''
#准备时间的最晚开始时间
S_start[M_i][OS_site]=Max_setup
Setup_gap_end = dict([[M_n, S_end[M_i][M_n]] for M_n in range(len(S_end[M_i])) if S_end[M_i][M_n] != 0])
Setup_gap_end = sorted(Setup_gap_end.items(), key=lambda item: item[1]) # 各个工序准备时间的结束时间
Setup_gap_Start = [[Setup_gap_end[key][0], S_start[M_i][Setup_gap_end[key][0]]] for key in
range(len(Setup_gap_end))] # 此机器上已加工工序各开始时间
if len(Setup_gap_end)>1: #具有多个时间空隙
for i in range(len(Setup_gap_end)-1):
if i ==0 and Setup_gap_Start[i][1]>=S_ij:
S_start[M_i][OS_site]=0
break
elif Setup_gap_Start[i+1][1]-Setup_gap_end[i][1]>=S_ij:
S_start[M_i][OS_site]=Setup_gap_end[i][1]
break
else: #只有一个空隙
if Setup_gap_Start[0][1]>S_ij:
S_start[M_i][OS_site]=0
S_end[M_i][OS_site]=S_start[M_i][OS_site]+S_ij
'''
工序插入机器加工时间间隙
'''
Max_Machine_time=np.max(End_time[M_i]) #这道工序再该机器上最晚开始加工的时间
Start_time[M_i][OS_site]=max(Max_Machine_time,S_end[M_i][OS_site])
M_n_list = dict(M_n_list)
M_n_list = sorted(M_n_list.items(), key=lambda item: item[1]) # 此机器上各已加工时间结束时间
M_n_Start = [[M_n_list[key][0], Start_time[M_i][M_n_list[key][0]]] for key in
range(len(M_n_list))] # 此机器上已加工工序各开始时间
if len(M_n_list) > 1: #有多个空隙的情况
for i_tem in range(len(M_n_list) - 1):
if i_tem == 0 and M_n_Start[i_tem][1]-S_end[M_i][OS_site]>=P_ij: #当空闲时间在第一个地方
Start_time[M_i][OS_site]=S_end[M_i][OS_site]
break
elif M_n_Start[i_tem + 1][1] - M_n_list[i_tem][1] >= P_ij: #当空闲时间位于加工工序之间
if M_n_list[i_tem][1]>=S_end[M_i][OS_site]:
Start_time[M_i][OS_site] = M_n_list[i_tem][1]
elif M_n_list[i_tem][1]<=S_end[M_i][OS_site] and M_n_Start[i_tem + 1][1]-S_end[M_i][OS_site]>=P_ij:
Start_time[M_i][OS_site] = S_end[M_i][OS_site]
break
else: #只有一个空隙的情况
if M_n_Start[0][1]-S_end[M_i][OS_site] >= P_ij:
Start_time[M_i][OS_site] = S_end[M_i][OS_site]
End_time[M_i][OS_site] = Start_time[M_i][OS_site] + P_ij
else: # 工序既不是机器的第一道工序，也不是工件的第一道工序
SD_Machine = JM[OS_j - 1][M_i_h - 2] # 该工件上道工序加工机器
if SD_Machine!=M_i:
T_ij=Transpotation_time[SD_Machine][M_i]
else:
T_ij=0
S_ij=0
S = End_time[SD_Machine][OS_site - 1] # 该工序上道工序完工时间
T_start[M_i][OS_site]=S
T_end[M_i][OS_site]=T_start[M_i][OS_site]+T_ij
'''
找到一个合适的时间空隙，将准备时间插入这个间隙
'''
#准备时间的最晚开始时间
Max_setup=np.max(S_end[M_i][OS_site])
S_start[M_i][OS_site] = max(Max_setup,T_end[M_i][OS_site])
Setup_gap_end = dict([[M_n, S_end[M_i][M_n]] for M_n in range(len(S_end[M_i])) if S_end[M_i][M_n] != 0])
Setup_gap_end = sorted(Setup_gap_end.items(), key=lambda item: item[1]) # 各个工序准备时间的结束时间
Setup_gap_Start = [[Setup_gap_end[key][0], S_start[M_i][Setup_gap_end[key][0]]] for key in
range(len(Setup_gap_end))] # 此机器上已加工工序各开始时间
if len(Setup_gap_end) > 1: # 具有多个时间空隙
for i in range(len(Setup_gap_end) - 1):
if i == 0 and Setup_gap_Start[i][1]-T_end[M_i][OS_site] >= S_ij:
S_start[M_i][OS_site] = T_end[M_i][OS_site]
break
elif Setup_gap_Start[i + 1][1] - Setup_gap_end[i][1] >= S_ij:
if Setup_gap_end[i][1]>=T_end[M_i][OS_site]:
S_start[M_i][OS_site]=Setup_gap_end[i][1]
elif Setup_gap_end[i][1]<T_end[M_i][OS_site] and Setup_gap_Start[i+1][1]-T_end[M_i][OS_site]>=S_ij:
S_start[M_i][OS_site] = T_end[M_i][OS_site]
break
else: # 只有一个空隙
if Setup_gap_Start[0][1]-T_end[M_i][OS_site] >= S_ij:
S_start[M_i][OS_site] = T_end[M_i][OS_site]
S_end[M_i][OS_site] = S_start[M_i][OS_site]+S_ij
'''
将工序插入机器加工的时间空隙
'''
Max_Machine_time=np.max(End_time[M_i])
Start_time[M_i][OS_site]=max(S_end[M_i][OS_site],Max_Machine_time)
M_n_list = dict(M_n_list)
M_n_list = sorted(M_n_list.items(), key=lambda item: item[1]) # 此机器上各已加工时间结束时间
M_n_Start = [[M_n_list[key][0], Start_time[M_i][M_n_list[key][0]]] for key in
range(len(M_n_list))] # 此机器上已加工工序各开始时间
if len(M_n_list) > 1:
for i_tem in range(len(M_n_list) - 1):
if M_n_Start[0][1] > S_end[M_i][OS_site] and M_n_Start[0][1] - S_end[M_i][OS_site] >= P_ij:
Start_time[M_i][OS_site] = S_end[M_i][OS_site]
break
if M_n_Start[i_tem + 1][1] - M_n_list[i_tem][1] >= P_ij and M_n_Start[i_tem + 1][1] > S_end[M_i][OS_site]:
if M_n_list[i_tem][1] > S_end[M_i][OS_site]:
Start_time[M_i][OS_site] = M_n_list[i_tem][1]
elif M_n_Start[i_tem + 1][1] - S_end[M_i][OS_site] >= P_ij:
Start_time[M_i][OS_site] = S_end[M_i][OS_site]
break
else:
if M_n_Start[0][1] > S_end[M_i][OS_site] and M_n_Start[0][1] - S_end[M_i][OS_site] >= P_ij:
Start_time[M_i][OS_site] = S_end[M_i][OS_site]
End_time[M_i][OS_site] = Start_time[M_i][OS_site] + P_ij
for i in range(len(End_time)):
for j in range(len(End_time[i])):
if End_time[i][j] - Start_time[i][j] == 0:
Start_time[i][j] = 0
End_time[i][j] = 0
S_end[i][j]=0
S_start[i][j]=0
T_start[i][j]=0
T_end[i][j]=0
return Start_time,End_time,S_start,S_end,T_start,T_end结果
注：此处结果仅作解码演示，并非最优调度结果
注：可能存在错误，欢迎骚扰！！
本文地址：https://blog.csdn.net/crazy_girl_me/article/details/110872487
上一篇： 网络聊天
下一篇： 27_python笔记-pandas