《算法设计与分析》综合设计与实现
作业车间调度问题
| 学生姓名： | 张立辉 |
| 学生学号： | 1814010130 |
| 学生班级： | 软件18-1 |
| 学生专业： | 软件工程 |
| 指导老师： | 张淑丽 |
哈尔滨理工大学软件与微电子学院
一、作业车间调度问题描述
作业车间调度问题（Job Shop Scheduling, JSP）是最经典的几个NP-hard问题之一。其应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线等。
JSP问题描述：一个加工系统有M台机器，要求加工N个作业，其中，作业i包含工序数为Li。令 ，则L为任务集的总工序数。其中，各工序的加工时间已确定，并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序，约束条件被满足的同时，使性能指标得到优化。
作业车间调度需要考虑如下约束:
Cons1：每道工序在指定的机器上加工，且必须在其前一道工序加工完成后才能开始加工；
Cons2：某一时刻1台机器只能加工1个作业；
Cons3：每个作业只能在1台机器上加工1次；
Cons4：各作业的工序顺序和加工时间已知，不随加工排序的改变而改变。
二、作业车间调度问题的数学模型
在本课程的综合设计与实现环节中，我们将作业车间调度问题的优化目标设为最大完工时间最小：令(i,j)表示作业i的第j个工序。Sij和Tij分别表示(i,j)的加工起始时刻和加工时间。Zijk表示(i,j)是否在第k台机器上加工：如果(i,j)在第k台机器上加工，Zijk=1；否则，Zijk=0。Ck为第k台机器的完工时间，则问题的数学模型如下：
公式(1)为目标函数，使最迟完工的机器尽早完成，即加工时间最短；公式(2)表示1个作业只能在加工完成前一道工序后才可以加工后一道工序；公式(3)表示1个作业的第1道工序的起始加工时刻大于或等于0；公式(4)表示在1台机床上不会同时加工1个以上的作业。
三、问题实例
下面给出作业车间调度问题的一个实例，其中每个工序上标注有一对数值（m,p），其中，m表示当前工序必须在第m台机器上进行加工，p表示第m台机器加工当前工序所需要的加工时间。（注：机器和作业的编号从0开始）
jop0=[(0,3),(1,2),(2,2)]
jop1=[(0,2),(2,1),(1,4)]
jop2=[(1,4),(2,3)]
在这个例子中，作业jop0有3道工序：它的第1道工序上标注有(0,3)，其表示第1道工序必须在第0台机器上进行加工，且需要3个单位的加工时间；它的第2道工序上标注有(1,2)，其表示第2道工序必须在第1台机器上进行加工，且需要2个单位的加工时间；余下的同理。总的来说，这个实例中共有8道工序。
该问题的一个可行解是L=8道工序开始时间的一个排列，且满足问题的约束。下图给出了一个可行解（注：该解不是最优解）的示例：
在上图中，我们能看到每个作业的工序按照问题给定的顺序进行了加工，且相互之间没有时间区间重叠。这个可行解的结果是12，即三个作业均被加工完成的时间。
请各位同学针对该实例完成后续的工作内容
四、算法设计思想
1、遗传算法：
遗传算法（Genetic Algorithm，GA）是一种模拟自然选择和生物进化过程的智能优化算法。在自然界中，自从达尔文提出“优胜劣汰，适者生存”物种进化理论之后，研究学者对生物进化的过程进行了长久而又深远的研究。物种通过母代的繁衍形成新的下一代个体，新一代个体中，大多数个体由于发生染色体交叉过程会与母代类似，少数个体由于发生了变异则与母代不同。大自然作为自然选择的执行者，在生存资源和外界环境的变化、个体不断进行竞争的过程中，将适应能力强的个体留下，而淘汰适应能力差的个体，这种自然选择的过程为人类提供了一种全新的解决问题的方式。
1965年，John H. Holland首次引用了生物的进化机制来解决问题，他的学生在论文中也首次提出“遗传算法”的概念。1975年， Holland概括性总结论述了遗传算法。几十年来，越来越多的研究学者加入到遗传算法的研究中，并取得了丰富的研究成果。随着研究的深入，遗传算法以其操作简单、容易实现等优点，逐渐应用于各个领域，不仅在函数优化、组合优化等方面有所建树，同时在应用层面如机器学习、生产调度、自动控制、图像处理、数据挖掘等方面也有很广泛的应用。
基本思想：
生物的进化是通过染色体来实现的，染色体上有着许多控制生物性状的基因，这些基因会在遗传过程中随着染色体的交叉进行重新组合，同时会以一定概率发生变异。遗传算法的基本思路与此类似，可以将待优化问题的求解看作生物努力适应环境的过程，问题的解对应生物种群中的个体，算法的搜索便是种群一代代进化最终形成稳定物种的过程。
2、遗传算法的结构框架可以简述如下：
1、初始化：依据每个种群的特征随机生成第一代种群的全部个体；
2、求个体适应度：计算每个个体的适应度；
3、选择过程：依据一定的选择规范，选出一部分优秀个体参与交叉和变异操作；
4、交叉过程：群体中两两配对，交换部分染色体基因，完成交叉操作；
5、变异过程：随机改变个体中的部分基因，来实现变异操作；
6、终止判断：若新一代种群满足终止条件，停止算法迭代，记录此时的最优解为问题的最优解；否则，迭代次数加1，返回步骤2；
流程图：
五、伪代码
/*
* Pc：交叉发生的概率
* Pm：变异发生的概率
* M：种群规模
* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
do
{
计算种群Pop中每一个体的适应度F(i)。
初始化空种群newPop
do
{
根据适应度以比例选择算法从种群Pop中选出2个个体
if ( random ( 0 , 1 ) < Pc )
{
对2个个体按交叉概率Pc执行交叉操作
}
if ( random ( 0 , 1 ) < Pm )
{
对2个个体按变异概率Pm执行变异操作
}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )六、程序代码及运行结果
程序代码：
import numpy as np
import matplotlib.pyplot as plt
import random
import itertools
# 全局初始化
def Global_initialization(T0, O, GS, MS, n, M, OS_list, OS):
# print('全局初始化')
# print(M)
Machine_time = np.zeros(M, dtype=int) # 机器时间初始化
for i in range(GS):
random.shuffle(OS_list) # 生成工序排序部分
OS[i] = np.array(OS_list)
GJ_list = []
for GJ_Num in range(n): # 工件集
GJ_list.append(GJ_Num)
random.shuffle(GJ_list)
for g in GJ_list: # 随机选择工件集的第一个工件,从工件集中剔除这个工件
h = np.array(O[g]) # 第一个工件含有的工序
for j in range(len(h)): # 从工件的第一个工序开始选择机器
D = np.array(h[j])
List_Machine_weizhi = []
for k in range(len(D)): # 每道工序可使用的机器以及机器的加工时间
Useing_Machine = D[k]
if Useing_Machine == 999: # 确定可加工该工序的机器
continue
else:
List_Machine_weizhi.append(k)
Machine_Select = []
for Machine_add in List_Machine_weizhi: # 将这道工序的可用机器时间和以前积累的机器时间相加
Machine_time[Machine_add] = Machine_time[Machine_add] + D[
Machine_add] # 比较可用机器的时间加上以前累计的机器时间的时间值，并选出时间最小
Machine_Select.append(Machine_time[Machine_add])
Min_time = min(Machine_Select)
Machine_Index_add = Machine_Select.index(Min_time)
MS[i][g * M + j] = Machine_Index_add + 1
CHS1 = np.hstack((MS, OS))
return CHS1
# 局部选择
def Local_choice(T0, O, LS, MS, n, M, OS_list, OS):
# print('局部选择')
for i in range(LS):
random.shuffle(OS_list) # 生成工序排序部分
OS_gongxu = OS_list
OS[i] = np.array(OS_gongxu)
GJ_list = []
for GJ_Num in range(n): # 工件集
GJ_list.append(GJ_Num)
A = 0
for gon in GJ_list:
Machine_time = np.zeros(M) # 机器时间初始化
g = gon # 随机选择工件集的第一个工件 #从工件集中剔除这个工件
h = np.array(O[g]) # 第一个工件及其对应工序的加工时间
for j in range(len(h)): # 从工件的第一个工序开始选择机器
D = np.array(h[j])
List_Machine_weizhi = []
for k in range(len(D)): # 每道工序可使用的机器以及机器的加工时间
Useing_Machine = D[k]
if Useing_Machine == 999: # 确定可加工该工序的机器
continue
else:
List_Machine_weizhi.append(k)
Machine_Select = []
for Machine_add in List_Machine_weizhi: # 将这道工序的可用机器时间和以前积累的机器时间相加
Machine_time[Machine_add] = Machine_time[Machine_add] + D[
Machine_add] # 比较可用机器的时间加上以前累计的机器时间的时间值，并选出时间最小
Machine_Select.append(Machine_time[Machine_add])
Machine_Index_add = Machine_Select.index(min(Machine_Select))
MS[i][g * M + j] = MS[i][g * M + j] + Machine_Index_add + 1
A += 1
CHS1 = np.hstack((MS, OS))
return CHS1
# 随机选择
def Random_choice(T0, O, RS, MS, n, M, OS_list, OS):
# print('随机选择')
for i in range(RS):
random.shuffle(OS_list) # 生成工序排序部分
OS_gongxu = OS_list
OS[i] = np.array(OS_gongxu)
GJ_list = []
for GJ_Num in range(n): # 工件集
GJ_list.append(GJ_Num)
A = 0
for gon in GJ_list:
Machine_time = np.zeros(M) # 机器时间初始化
g = gon # 随机选择工件集的第一个工件 #从工件集中剔除这个工件
h = np.array(O[g]) # 第一个工件及其对应工序的加工时间
for j in range(len(h)): # 从工件的第一个工序开始选择机器
D = np.array(h[j])
List_Machine_weizhi = []
for k in range(len(D)): # 每道工序可使用的机器以及机器的加工时间
Useing_Machine = D[k]
if Useing_Machine == 999: # 确定可加工该工序的机器
continue
else:
List_Machine_weizhi.append(k)
Machine_Select = []
for Machine_add in List_Machine_weizhi: # 将这道工序的可用机器时间和以前积累的机器时间相加
Machine_time[Machine_add] = Machine_time[Machine_add] + D[
Machine_add] # 比较可用机器的时间加上以前累计的机器时间的时间值，并选出时间最小
Machine_Select.append(Machine_time[Machine_add])
Machine_Index_add = Machine_Select.index(random.choice(Machine_Select))
MS[i][A] = MS[i][A] + Machine_Index_add + 1
A += 1
CHS1 = np.hstack((MS, OS))
return CHS1
# 染色体解码
# JM与T的关系是一一对应的
def Chromosome_decoding(CHS, O, T0, n, Max_Onum, M0):
# print('染色体解码')
JM = np.zeros((n, Max_Onum), dtype=int) # JM(j,h)表示工件Ji的工序Oh的机器号
T = np.zeros((n, Max_Onum), dtype=int) # T（j,h）表示工件Jj的工序Oh的加工时间
# 步骤1：对机器选择部分进行解码，从左到右依次读取并转换成机器顺序矩阵JM和时间顺序矩阵T
MS = CHS[0:T0]
OS = CHS[T0:T0 * 2]
GX_num = 0
# print(MS)
for J_j in MS: # 将机器选择部分转换成机器顺序矩阵和时间顺序矩阵
GX_num += 1
JM_j = int((GX_num - 1) / Max_Onum) # 机器顺序矩阵的横坐标
JM_h = int((GX_num - 1) % Max_Onum) # 机器顺序矩阵的纵坐标
O_j = np.array(O[JM_j][JM_h])
# print(len(O_j))
Mac_using = []
Mac_time = []
for Mac_num in range(len(O_j)): # 寻找MS对应部分的机器时间和机器顺序
if O_j[Mac_num] != 999:
Mac_using.append(Mac_num)
Mac_time.append(O_j[Mac_num])
else:
continue
# print(JM_j,JM_h,J_j)
JM[JM_j][JM_h] += Mac_using[J_j - 1] # 机器顺序矩阵
T[JM_j][JM_h] += Mac_time[J_j - 1] # 时间顺序矩阵
# 步骤2：按照步骤1对应的T和JM依次得到每个工件工序对应的加工机器和加工时间
# print(M0,T0)
Start_time = np.zeros((M0, T0), dtype=int) # 机器开始加工的时间
End_time = np.zeros((M0, T0), dtype=int) # 机器结束加工的时间
Opearation = np.zeros((M0, T0), dtype=int)
Counter_List = []
T_count = 0
for OS_j in OS: # 通过机器顺序矩阵和时间顺序矩阵的到工序的加工机器和加工时间
T_count += 1
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[OS_j - 1][M_i_h - 1] # 这道工序的加工时间
M_n_list = []
for M_n in End_time[M_i]: # 确定工序为机器M_i的第几道加工工序
if M_n != 0:
M_n_list.append(M_n)
# 工件O_jh是机器M_i的第一道加工工序，直接从机器M_i的零时刻进行加工
if M_i_h == 1 and len(M_n_list) == 0:
Start_time[M_i][T_count - 1] = 0
End_time[M_i][T_count - 1] += P_ij
Opearation[M_i][T_count - 1] = OS_j
# 工序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]
SD_count = 0
SD_c = 0
for SD_i in OS:
SD_count += 1
if SD_i == OS_j:
SD_c += 1
if SD_c == M_i_h - 1:
break
S = End_time[SD_Machine][SD_count - 1]
Start_time[M_i][T_count - 1] = S
End_time[M_i][T_count - 1] = S + P_ij
Opearation[M_i][T_count - 1] = OS_j
elif len(M_n_list) != 0 and M_i_h == 1:
List_start_0 = []
List_end_0 = []
List_index_0 = []
for L_i in range(len(End_time[M_i])):
if End_time[M_i][L_i] != 0:
List_start_0.append(Start_time[M_i][L_i])
List_end_0.append(End_time[M_i][L_i])
List_index_0.append(L_i)
disp = zip(List_index_0, List_end_0)
disp_1 = zip(List_index_0, List_start_0)
Disp_1 = dict(disp)
Disp_2 = dict(disp_1)
A = sorted(Disp_1.items(), key=lambda item: item[1])
B = sorted(Disp_2.items(), key=lambda item: item[1])
D_1 = dict(A)
D_2 = dict(B)
List_start = []
List_end = []
List_index = []
for k in D_1:
List_end.append(D_1[k])
List_index.append(k)
for k_1 in D_2:
List_start.append(D_2[k_1])
Lst = []
Lst_index = []
for L_j in range(len(List_end) - 1):
if List_start[L_j + 1] - List_end[L_j] >= P_ij:
Lst.append(List_start[L_j + 1] - List_end[L_j])
Lst_index.append(List_index[L_j])
if len(Lst) != 0:
L_m_list = []
for L_m in Lst:
L_m_list.append(L_m)
if L_m >= P_ij:
L_P = Lst_index[Lst.index(L_m)]
Start_time[M_i][T_count - 1] = End_time[M_i][L_P]
break
while len(L_m_list) == len(Lst):
Start_time[M_i][T_count - 1] = max(End_time[M_i])
break
else:
Start_time[M_i][T_count - 1] = max(End_time[M_i])
End_time[M_i][T_count - 1] = Start_time[M_i][T_count - 1] + P_ij
Opearation[M_i][T_count - 1] = OS_j
# 加工工序不是机器和工件的第一道工序
else:
SC_Machine = JM[OS_j - 1][M_i_h - 2] # 这个工件上一道工序的使用机器
CO_er = 0
CON_er = 0
for Max_i in OS:
CO_er += 1
if Max_i == OS_j:
CON_er += 1
if CON_er == M_i_h - 1:
break
SC_endtime = End_time[SC_Machine][CO_er - 1] # 这个工件的上一道工序的结束时间
SD_S = []
SD_E = []
SD_index = []
for SD_i in range(len(End_time[M_i])):
if End_time[M_i][SD_i] != 0:
SD_E.append(End_time[M_i][SD_i])
SD_S.append(Start_time[M_i][SD_i])
SD_index.append(SD_i)
disp_2 = zip(SD_index, SD_E)
disp_3 = zip(SD_index, SD_S)
Disp_3 = dict(disp_2)
Disp_4 = dict(disp_3)
C_1 = sorted(Disp_3.items(), key=lambda item: item[1])
D_4 = sorted(Disp_4.items(), key=lambda item: item[1])
D_5 = dict(C_1)
D_6 = dict(D_4)
List_start_1 = []
List_end_1 = []
List_index_1 = []
for k_2 in D_5:
List_end_1.append(D_5[k_2])
List_index_1.append(k_2)
for k_3 in D_6:
List_start_1.append(D_6[k_3])
Lst_1 = []
Lst_index_1 = []
for L_j_1 in range(len(List_end_1) - 1):
if List_start_1[L_j_1 + 1] - List_end_1[L_j_1] >= P_ij:
Lst_1.append(List_start_1[L_j_1 + 1] - List_end_1[L_j_1])
Lst_index_1.append(List_index_1[L_j_1])
if len(Lst_1) != 0:
L_M_1_list = []
for L_M_1 in Lst_1:
L_M_1_list.append(L_M_1)
if L_M_1 >= P_ij:
List_Count_1 = Lst_index_1[Lst_1.index(L_M_1)]
L_M = List_index_1[List_index_1.index(List_Count_1) + 1]
if End_time[M_i][List_Count_1] >= SC_endtime or Start_time[M_i][L_M] - SC_endtime >= P_ij:
Start_time[M_i][T_count - 1] = End_time[M_i][List_Count_1]
break
while len(L_M_1_list) == len(Lst_1):
if max(End_time[M_i]) >= SC_endtime:
Start_time[M_i][T_count - 1] = max(End_time[M_i])
else:
Start_time[M_i][T_count - 1] = SC_endtime
break
else:
if max(End_time[M_i]) >= SC_endtime:
Start_time[M_i][T_count - 1] = max(End_time[M_i])
else:
Start_time[M_i][T_count - 1] = SC_endtime
End_time[M_i][T_count - 1] = Start_time[M_i][T_count - 1] + P_ij
Opearation[M_i][T_count - 1] = OS_j
return Start_time, End_time, Opearation
# 交叉操作
# 机器选择部分
def Crossover_Machine(T0, T_r, CHS1, CHS2):
# print('机器选择')
r = random.randint(0, T0) # 在区间[遗传算法,T0]内产生一个整数r
random.shuffle(T_r)
R = T_r[0:r] # 按照随机数r产生r个互不相等的整数
# 将父代的染色体复制到子代中去，保持他们的顺序和位置
C_1 = CHS2
C_2 = CHS1
for i in R:
K = CHS1[i]
K_2 = CHS2[i]
C_1[i] = K
C_2[i] = K_2
return C_1, C_2
# 工序排序部分
def Crossover_Operation(O_set, CHS1, CHS2, T0, N):
# print('交叉操作')
r = random.randint(1, T0)
random.shuffle(O_set)
O_1 = O_set[0:r] # 将工件集划分为Jobset1和Jobset2
O_2 = O_set[r:N]
C_1 = np.zeros(T0, dtype=int)
C_2 = np.zeros(T0, dtype=int)
Count_i = 0
Count = 0
C_index1 = []
C_index2 = []
for j in CHS1: # 复制父代染色体P1、P2中包含工件集Jobset1/Jobset2中的工件复制到C1/C2中，保持他们的顺序
Count_i += 1
for i in O_1:
if j == i:
C_1[Count_i - 1] = j
for j_1 in CHS2:
Count += 1
for i_1 in O_2:
if j_1 == i_1:
C_2[Count - 1] = j_1
Count_2 = 0
for j_2 in CHS1:
Count_2 += 1
for i_2 in O_2:
if j_2 == i_2:
C_index1.append(Count_2 - 1)
Count_3 = 0
for j_3 in CHS2:
Count_3 += 1
for i_3 in O_1:
if j_3 == i_3:
C_index2.append(Count_3 - 1)
new_CHS1 = np.delete(CHS1, C_index1)
new_CHS2 = np.delete(CHS2, C_index2)
Count_4 = 0
for k in range(len(CHS1)):
if C_1[k] == 0:
C_1[k] = new_CHS2[Count_4]
Count_4 += 1
Count_5 = 0
for k_1 in range(len(CHS2)):
if C_2[k_1] == 0:
C_2[k_1] = new_CHS1[Count_5]
Count_5 += 1
return C_1, C_2
# 变异操作
# 机器变异部分
def Variation_Machine(Tr, O, MS, T0, Max_Onum):
# print('机器变异')
# 机器选择部分
r = random.randint(1, T0 - 1) # 在变异染色体中选择r个位置
random.shuffle(Tr)
T_r = Tr[0:r]
for i in T_r:
O_i = int(i / Max_Onum)
O_j = i % Max_Onum
Machine_using = O[O_i][O_j]
Machine_index = []
for j in Machine_using:
if j != 9999:
Machine_index.append(j)
Min = Machine_index[0]
Min_index = 0
for j_1 in range(len(Machine_index)):
if Machine_index[j_1] < Min:
Min = Machine_index[j_1]
Min_index = j_1
else:
Min = Min
Min_index = Min_index
MS[i] = Min_index + 1
return MS
# 变异操作
# 工序变异部分
def Variation_Operation(Tr, OS, MS):
# print('变异操作')
r = random.randint(2, 6) # 在变异染色体中选择r个位置
random.shuffle(Tr)
T_r = Tr[0:r]
O_ky = []
for i in range(len(OS)):
for j in range(len(T_r)):
if i == T_r[j]:
O_ky.append(OS[i])
# print(O_ky)
A = np.array(list(itertools.permutations(O_ky, r)))
CHS_T = []
for k in range(len(A)):
H = A[k]
for k_1 in range(len(T_r)):
I_1 = T_r[k_1]
I_2 = H[k_1]
OS[I_1] = I_2
CHS = MS + OS
CHS_T.append(list(CHS))
M = np.array(CHS_T)
W = fitness(M, k + 1)
Fit_index = []
for i_1 in range(k + 1):
Fit_index.append(i_1)
disp = zip(Fit_index, W)
Disp = dict(disp)
B_1 = sorted(Disp.items(), key=lambda item: item[1])
B = dict(B_1)
B_0 = list(B.keys())
B0 = B_0[0]
return CHS_T[B0]
# 选择操作
def Select(Fit_value, POP_SIZE):
# print('选择操作')
Fit_index = []
for i in range(POP_SIZE):
Fit_index.append(i)
# print(Fit_index,Fit_value)
disp = zip(Fit_index, Fit_value)
Disp = dict(disp)
A = sorted(Disp.items(), key=lambda item: item[1])
D = dict(A)
Pop_leave = int(POP_SIZE * 0.6)
CHS_index = []
for j, (k, v) in enumerate(D.items()):
if j in range(0, Pop_leave):
CHS_index.append(k)
return CHS_index
# 画甘特图
def gatt(End_time, Start_time, CHS, T0, N):
# print('画甘特图')
Start = []
End = []
# print(T0, N)
M = ['aqua', 'orchid', 'lightpink', 'aquamarine', 'maroon', 'red', 'blue', 'yellow', 'orange', 'green',
'palevioletred', 'royalblue']
for i in range(N):
for j in range(T0):
# print(i,j)
# print(End_time)
if End_time[i][j] != 0:
plt.barh(i, width=End_time[i][j] - Start_time[i][j], left=Start_time[i][j], color=M[CHS[j + T0] - 1],
edgecolor='white')
plt.text(x=Start_time[i][j] + 0.3, y=i, s=(CHS[j + T0] - 1, End_time[i, j]))
Start.append(Start_time[i][j])
End.append(End_time[i][j])
plt.yticks(np.arange(i + 1), np.arange(1, i + 2))
plt.show()
def main(T0_1, M0, N, Max_Onum, T_R, O_set1, OS_List, L):
# print('main')
GSP = 0.6 # 全局选择的GS概率
LSP = 0.3 # 局部选择的LS概率
RSP = 0.1 # 随机选择的RS概率
POP_SIZE = 1000 # 种群规模
Max_Itertions = 100 # 最大迭代次数=100
GS_1 = int(POP_SIZE * GSP) # 全局选择的个数
LS_1 = int(POP_SIZE * LSP) # 局部选择的个数
RS_1 = int(POP_SIZE * RSP) # 随机选择的个数
CSH = np.zeros([POP_SIZE, T0_1 * 2], dtype=int) # 初始化种群
GS_MS_1 = np.zeros([GS_1, T0_1], dtype=int) # 机器选择部分MS
GS_OS_1 = np.zeros([GS_1, T0_1], dtype=int) # 工序选择部分OS
LS_MS_1 = np.zeros([LS_1, T0_1], dtype=int) # 机器选择部分MS
LS_OS_1 = np.zeros([LS_1, T0_1], dtype=int) # 工序选择部分OS
RS_MS_1 = np.zeros([RS_1, T0_1], dtype=int) # 机器选择部分MS
RS_OS_1 = np.zeros([RS_1, T0_1], dtype=int) # 工序选择部分OS
O_L = np.array(L)
CHS0 = Global_initialization(T0_1, O_L, GS_1, GS_MS_1, N, M0, OS_List, GS_OS_1) # 全局选择部分染色体
CHS1 = Local_choice(T0_1, O_L, LS_1, LS_MS_1, N, M0, OS_List, LS_OS_1) # 局部训责部分染色体
CHS2 = Random_choice(T0_1, O_L, RS_1, RS_MS_1, N, M0, OS_List, RS_OS_1) # 随机选择部分染色体
C = np.vstack((CHS0, CHS1, CHS2)) # 将初始化染色体合并到一个矩阵
# print(C)
Fit = []
for i in range(len(C)): # 计算每个染色体个体的适应度
M = C[i]
A = Chromosome_decoding(M, O_L, T0_1, N, Max_Onum, M0)
F = np.max(A[1])
Fit.append(F)
Min = min(Fit)
while Max_Itertions > 0: # 设定结束的约束条件
Max_Itertions -= 1
S = Select(Fit, POP_SIZE)
C_I = []
for j in S:
C_I.append(C[j])
C_J = np.array(C_I)
P_c = random.uniform(0.6, 0.8) # 确定交叉概率
P_m = random.uniform(0.005, 0.006) # 确定变异概率
P_C = int(P_c * (len(S)))
P_M = int(P_m * (len(S)))
S_list = np.random.permutation(range(len(S)))
PC = S_list[0:P_C]
for k in range(0, len(PC), 2):
CHS_1 = C_J[PC[k]]
if k + 1 < len(PC):
CHS_2 = C_J[PC[k + 1]]
else:
break
MS_crossover = Crossover_Machine(T0_1, T_R, CHS_1[0:T0_1], CHS_2[0:T0_1])
OS_crossover = Crossover_Operation(O_set1, CHS_1[T0_1:T0_1 * 2], CHS_2[T0_1:T0_1 * 2], T0_1, N)
CHS_crossover_1 = np.hstack((MS_crossover[0], OS_crossover[0]))
CHS_crossover_2 = np.hstack((MS_crossover[1], OS_crossover[1]))
CHS_crossover = np.vstack((CHS_crossover_1, CHS_crossover_2))
C_J = np.vstack((C_J, CHS_crossover))
Fit_1 = []
for i_1 in range(len(C_J)): # 计算每个染色体个体的适应度
M_0 = C_J[i_1]
A = Chromosome_decoding(M_0, O_L, T0_1, N, Max_Onum, M0)
F = np.max(A[1])
Fit_1.append(F)
Min_1 = min(Fit_1)
if Min_1 < Min:
Min = Min_1
S_1 = Select(Fit_1, len(C_J))
Min_Index = S_1[0]
Min_CHS = C_J[Min_Index]
Chromo = Chromosome_decoding(Min_CHS, O_L, T0_1, N, Max_Onum, M0)
print("计算完成")
print('最优解为：', Min)
gatt(Chromo[1], Chromo[0], Min_CHS, T0_1, M0) # 画甘特图
def choose(n):
# print('choose')
# print(n)
if n == 9:
T0_1 = 9 # 染色体长度的一半
M0 = 3 # 机器数4
N = 3 # 工件数3
Max_Onum = 3 # 所有工件中，最大的工序数
T_R = [0, 1, 2, 3, 4, 5, 6, 7, 8]
O_set1 = [1, 2, 3]
OS_List = [1, 1, 1, 2, 2, 2, 3, 3, 3]
L = [[[3, 999, 999], [999, 2, 999], [999, 999, 2]],
[[2, 999, 999], [999, 999, 1], [999, 4, 999]],
[[999, 4, 999], [999, 999, 3], [0, 0, 0]],
]
# print(T0_1)
return T0_1, M0, N, Max_Onum, T_R, O_set1, OS_List, L
elif n == 32:
T0_1 = 32 # 染色体长度的一半
M0 = 4 # 机器数4
N = 8 # 工件数3
Max_Onum = 4 # 所有工件中，最大的工序数
T_R = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
29, 30, 31]
O_set1 = [0, 1, 2, 3, 4, 5, 6, 7]
OS_List = [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8]
L = [
[[4, 999, 999, 999], [999, 999, 4, 999], [999, 7, 999, 999], [999, 99, 3, 999]],
# 第一个工件及其对应的机器加工时间
[[999, 999, 3, 999], [4, 999, 999, 999], [9999, 4, 999, 999], [999, 999, 999, 2]],
# 第二个工件及其对应的机器加工时间
[[3, 999, 999, 999], [999, 999, 999, 4], [999, 999, 6, 999], [999, 3, 999, 999]], # 第3个，。。。。
[[999, 999, 2, 999], [999, 6, 999, 999], [4, 999, 999, 999], [999, 999, 999, 3]], # 第4个，。。。。
[[999, 999, 999, 4], [999, 5, 999, 999], [999, 999, 5, 999], [3, 999, 999, 999]],
[[999, 4, 999, 999], [999, 999, 999, 6], [5, 999, 999, 999], [999, 999, 4, 999]],
[[999, 2, 999, 999], [999, 999, 4, 999], [999, 999, 999, 5], [5, 999, 999, 999]],
[[999, 999, 999, 3], [3, 999, 999, 999], [999, 2, 999, 999], [999, 999, 5, 999]],
]
# print(T0_1)
return T0_1, M0, N, Max_Onum, T_R, O_set1, OS_List, L
else:
T0_1 = 100 # 染色体长度的一半
M0 = 10 # 机器数4
N = 10 # 工件数3
Max_Onum = 10 # 所有工件中，最大的工序数
T_R = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54,
55,
56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81,
82,
83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
O_set1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
OS_List = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
L = [[[999, 999, 5, 999, 999, 999, 999, 999, 999, 999], [20, 999, 999, 999, 999, 999, 999, 999, 999, 999],
[999, 25, 999, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 35, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 15, 999, 999, 999, 999], [999, 999, 999, 999, 35, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 30, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 35, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 999, 35, 999], [999, 999, 999, 999, 999, 999, 999, 999, 999, 20]],
[[999, 40, 999, 999, 999, 999, 999, 999, 999, 999], [999, 999, 30, 999, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 50, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 40, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 45, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 20, 999, 999],
[30, 999, 999, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 15, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 30], [999, 999, 999, 999, 999, 999, 999, 999, 35, 999]],
[[999, 999, 20, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 20, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 40, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 45, 999, 999],
[999, 45, 999, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 999, 40, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 15, 999, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 999, 999, 35],
[999, 999, 999, 999, 999, 999, 999, 999, 50, 999], [10, 999, 999, 999, 999, 999, 999, 999, 999, 999]],
[[999, 999, 999, 999, 999, 999, 30, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 30, 999, 999],
[999, 25, 999, 999, 999, 999, 999, 999, 999, 999], [25, 999, 999, 999, 999, 999, 999, 999, 999, 999],
[999, 999, 40, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 50, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 35], [999, 999, 999, 999, 999, 999, 999, 999, 15, 999],
[999, 999, 999, 999, 35, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 50, 999, 999, 999, 999]],
[[999, 999, 40, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 999, 15, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 30, 999, 999], [999, 20, 999, 999, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 5, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 999, 999, 5],
[999, 999, 999, 999, 999, 999, 999, 999, 35, 999], [999, 999, 999, 999, 999, 35, 999, 999, 999, 999],
[35, 999, 999, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 30, 999, 999, 999, 999, 999, 999]],
[[999, 10, 999, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 10, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 40, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 999, 50, 999],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 20], [999, 999, 999, 999, 999, 10, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 35, 999, 999], [40, 999, 999, 999, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 35, 999, 999, 999, 999, 999], [999, 999, 30, 999, 999, 999, 999, 999, 999, 999]],
[[999, 999, 999, 999, 35, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 30, 999, 999, 999, 999],
[999, 999, 35, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 999, 999, 30],
[999, 999, 999, 999, 999, 999, 999, 999, 10, 999], [999, 999, 999, 45, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 45, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 15, 999, 999],
[999, 15, 999, 999, 999, 999, 999, 999, 999, 999], [45, 999, 999, 999, 999, 999, 999, 999, 999, 999]],
[[999, 999, 999, 20, 999, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 999, 30, 999],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 50], [999, 999, 999, 999, 999, 20, 999, 999, 999, 999],
[999, 999, 20, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 999, 35, 999, 999, 999, 999, 999],
[30, 999, 999, 999, 999, 999, 999, 999, 999, 999], [999, 50, 999, 999, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 20, 999, 999], [999, 999, 999, 999, 999, 999, 30, 999, 999, 999]],
[[999, 999, 999, 999, 10, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 999, 999, 35],
[999, 999, 999, 999, 999, 999, 999, 999, 20, 999], [999, 999, 999, 999, 999, 30, 999, 999, 999, 999],
[999, 999, 999, 30, 999, 999, 999, 999, 999, 999], [30, 999, 999, 999, 999, 999, 999, 999, 999, 999],
[999, 45, 999, 999, 999, 999, 999, 999, 999, 999], [999, 999, 30, 999, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 45, 999, 999, 999], [999, 999, 999, 999, 999, 999, 999, 50, 999, 999]],
[[999, 999, 999, 999, 999, 40, 999, 999, 999, 999], [999, 10, 999, 999, 999, 999, 999, 999, 999, 999],
[30, 999, 999, 999, 999, 999, 999, 999, 999, 999], [999, 999, 999, 999, 35, 999, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 40, 999, 999], [999, 999, 15, 999, 999, 999, 999, 999, 999, 999],
[999, 999, 999, 35, 999, 999, 999, 999, 999, 999], [999, 999, 999, 999, 999, 999, 20, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 40], [999, 999, 999, 999, 999, 999, 999, 999, 20, 999]]
]
# print(T0_1)
return T0_1, M0, N, Max_Onum, T_R, O_set1, OS_List, L
if __name__ == '__main__':
n = int(input('请选择测试用例：9/32/100：'))
(T0_11, M01, N1, Max_Onum1, T_R1, O_set11, OS_List1, L1) = choose(n)
print("正在计算请稍候....")
main(T0_11, M01, N1, Max_Onum1, T_R1, O_set11, OS_List1, L1)运行结果：
测试用例1：（3*3用例）
甘特图1：
甘特图2：
甘特图3：
测试用例2：（4*8用例）
甘特图1：
甘特图2：
甘特图3：
测试用例3：（10*10用例）
甘特图：
七、总结
3*3用例最优解为：11，输出甘特图为最优解且不是唯一解，基本符合要求。
4*8用例最优解为：36，输出甘特图为最优解且不是唯一解，基本符合要求。
10*10用例最优解为：450，输出甘特图为最优解基本符合要求。
程序全部运行成功，反复修改代码，直到最终的运行出正确的结果，为保证实验结果尽量贴近准确值，种群规模设置为1000，种群迭代次数设置为100，导致10*10用例运行时运行时间较长，但最终能得到想要的输出结果，在这次学习过程中收获了许多。