作业车间调度优化算法
- 题目来源
- 代码实现
- 输出结果
题目来源
题目来源于葛英飞《智能制造技术基础》书中175页的题目,基余分配率的作业车间调度优化算法。书中这部分有程序流程图,但是没有代码,课后闲暇之余通过Python对其进行了简单的实现,部分代码比较粗糙,仅仅实现了功能,未对其结构进行优化,供郑州科技学院智能制造专业各位同学参考。
代码实现
import numpy as npdef shengyuhanshuzhi_cal(part_name):#剩余函数值计算函数part_name_sy=[]for i in range(len(part_name)):part_name_sy.append(1-sum(part_name[0:i+1])/sum(part_name))return part_name_sy
def gongxu_count_max(gongxu):#计算最大工序数目gongxu_count=[]for i in range(len(gongxu)):gongxu_count.append(len(gongxu[i]))return max(gongxu_count)+1
def shengyuhanshuzhi_table(gongxu_count_max,gongxu_sy):#工序剩余函数值转化为按工序顺序构建all_sy = []for i in range(gongxu_count_max):sy = []for j in range(len(gongxu_sy)):if i<len(gongxu_sy[j]):sy.append(gongxu_sy[j][i])else:sy.append(-1)all_sy.append(sy)return all_sypart_zhou=[4,7,3,3]
part_taotong=[4,4,2,2]
part_yagai=[3,3,5,4]
part_chilun=[2,5,2,6,3,2,1]
part_xiangti=[2,5,6,5]#零件各工序加工时间
time_table=[part_zhou,part_taotong,part_yagai,part_chilun,part_xiangti]part_zhou_ad=[4,11,14,17]
part_taotong_ad=[4,8,10,12]
part_yagai_ad=[3,6,11,15]
part_chilun_ad=[2,7,9,15,18,20,21]
part_xiangti_ad=[2,7,13,18]#各零件累计加工时间
time_ad_table=[part_zhou_ad,part_taotong_ad,part_yagai_ad,part_chilun_ad,part_xiangti_ad]part_zhou_mm=[0,1,2,3]
part_taotong_mm=[0,1,5,3]
part_yagai_mm=[0,1,3,4]
part_chilun_mm=[2,1,2,1,6,7,8]
part_xiangti_mm=[12,9,10,11]#各个工序对应的设备
mm_table=[part_zhou_mm,part_taotong_mm,part_yagai_mm,part_chilun_mm,part_xiangti_mm]part_zhou_sy=[]
part_taotong_sy=[]
part_yagai_sy=[]
part_chilun_sy=[]
part_xiangti_sy=[]#剩余函数值part_zhou_sy=shengyuhanshuzhi_cal(part_zhou)
part_taotong_sy=shengyuhanshuzhi_cal(part_taotong)
part_yagai_sy=shengyuhanshuzhi_cal(part_yagai)
part_chilun_sy=shengyuhanshuzhi_cal(part_chilun)
part_xiangti_sy=shengyuhanshuzhi_cal(part_xiangti)#计算剩余函数值gongxu_sy=[part_zhou_sy,part_taotong_sy,part_yagai_sy,part_chilun_sy,part_xiangti_sy]
gongxu_count_max=gongxu_count_max(gongxu_sy)
#print(gongxu_count_max)#计算工序最大数量ST_list=[]
T_list=[]
ED_list=[]
GONGXU_list=[]for i in range(13):ST_list.append([])T_list.append([])ED_list.append([0])GONGXU_list.append([])T_PART=[]
for i in range(5):T_PART.append([0])all_sy=shengyuhanshuzhi_table(gongxu_count_max,gongxu_sy)#
#print(all_sy)
for i in range(gongxu_count_max):#print(i)#print(ED_list, "\n", GONGXU_list, "\n")#print(T_PART)#print(i)#print(all_sy[i])#print(np.asfarray(all_sy[i]))#print(np.asfarray(all_sy[i]) * 0 + -1)#print((np.asfarray(all_sy[i]) != (np.asfarray(all_sy[i]) * 0 + -1)).any())while((np.asfarray(all_sy[i]) != (np.asfarray(all_sy[i])*0+-1)).any()):#第一工序安排完之前不结束#判断是否有价值函数重复工序n = 0#print(n)for k in range(len(all_sy[i])):# print(max(all_sy[i]), all_sy[i][k])if all_sy[i][k] == max(all_sy[i]) and all_sy[i][k] != -1:n = n + 1#print(n)#无重复:if n==1:for j in range(len(all_sy[i])):if all_sy[i][j]==max(all_sy[i]) and all_sy[i][j]!=-1:#print(all_sy[i][j])all_sy[i][j]=-1#print(all_sy[i])#print(ST_list[mm_table[j][i]]==[] and i==0)#print(mm_table[j][i])if ST_list[mm_table[j][i]]==[] and i==0:#print(mm_table[j][i])#print(ST_list[mm_table[j][i]])ST_list[mm_table[j][i]].append(0)#print(ST_list)#print(mm_table[j][i])T_list[mm_table[j][i]].append(time_table[j][i])ED_list[mm_table[j][i]].append(ST_list[mm_table[j][i]][-1]+time_table[j][i])T_PART[j][0] = T_PART[j][0] + time_table[j][i]GONGXU_list[mm_table[j][i]].append(str(j+1)+","+str(i+1))elif ED_list[mm_table[j][i]][-1] > T_PART[j][0]:#如果设备加工时间大于零件前面工序时间的和,那么开始时间为设备这道工序结束的时间#print(mm_table[j][i])ST_list[mm_table[j][i]].append(ED_list[mm_table[j][i]][-1])#print(time_table[j][i])T_list[mm_table[j][i]].append(time_table[j][i])T_PART[j][0] = ED_list[mm_table[j][i]][-1] + time_table[j][i]ED_list[mm_table[j][i]].append(ST_list[mm_table[j][i]][-1] + time_table[j][i])GONGXU_list[mm_table[j][i]].append(str(j+1) + "," + str(i+1))else :#如果设备加工时间小于零件前面工序时间的和,那么开始时间为零件前道工序结束时间#print(mm_table[j][i])#print(T_PART)ST_list[mm_table[j][i]].append(T_PART[j][0])T_list[mm_table[j][i]].append(time_table[j][i])T_PART[j][0] = T_PART[j][0] + time_table[j][i]ED_list[mm_table[j][i]].append(ST_list[mm_table[j][i]][-1] + time_table[j][i])GONGXU_list[mm_table[j][i]].append(str(j+1) + "," + str(i+1))# 有重复:if n>1:# 找到剩余函数值相同的零件part = []for k in range(len(all_sy[i])):if all_sy[i][k] == max(all_sy[i]) and all_sy[i][k] != -1:part.append(k)# 对剩余函数值相同的零件总加工时长最大是多少:part_time = []for k in range(len(part)):part_time.append(sum(time_table[part[k]]))part_time_max = max((part_time))#print(part_time_max)#print(i,j)#print(all_sy[i][j])#print(max(all_sy[i]))#print(all_sy[i])for j in range(len(all_sy[i])):if all_sy[i][j] == max(all_sy[i]) and all_sy[i][j] != -1 and sum(time_table[j]) == part_time_max:all_sy[i][j] = -1#print(all_sy[i])if ST_list[mm_table[j][i]] == [] and i == 0:ST_list[mm_table[j][i]].append(0)T_list[mm_table[j][i]].append(time_table[j][i])ED_list[mm_table[j][i]].append(ST_list[mm_table[j][i]][-1] + time_table[j][i])T_PART[j][0] = T_PART[j][0] + time_table[j][i]GONGXU_list[mm_table[j][i]].append(str(j+1) + "," + str(i+1))elif ED_list[mm_table[j][i]][-1] > T_PART[j][0]:# print(mm_table[j][i])ST_list[mm_table[j][i]].append(ED_list[mm_table[j][i]][-1])#print(time_table[j][i])T_list[mm_table[j][i]].append(time_table[j][i])T_PART[j][0] = ED_list[mm_table[j][i]][-1] + time_table[j][i]ED_list[mm_table[j][i]].append(ST_list[mm_table[j][i]][-1] + time_table[j][i])GONGXU_list[mm_table[j][i]].append(str(j+1) + "," + str(i+1))else:# print(mm_table[j][i])ST_list[mm_table[j][i]].append(T_PART[j][0])T_list[mm_table[j][i]].append(time_table[j][i])T_PART[j][0] = T_PART[j][0] + time_table[j][i]ED_list[mm_table[j][i]].append(ST_list[mm_table[j][i]][-1] + time_table[j][i])GONGXU_list[mm_table[j][i]].append(str(j + 1) + "," + str(i + 1))print("各个设备各工序开始时间:",ST_list)print("各个设备各工序结束时间:",ED_list)
print("各个设备各工序工作序列:",GONGXU_list)
输出结果
这里用列表表示每道工序的开始时间,结束时间,以及对应的工序,后续可用甘特图实现加以完善。
甘特图代码
plt.rcParams['font.sans-serif'] = ['SimHei'] # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号colors=['b','g','r','y','c','m','k']
color_map=[]
for i in range(len(GONGXU_list)):color_sub=[]for j in range(len(GONGXU_list[i])):color_sub.append(colors[int(GONGXU_list[i][j][0])])color_map.append(color_sub)plt.figure(figsize=(15,10),dpi=80)
for i in range(len(ST_list)):for j in range(len(ST_list[i])):plt.barh(-i-1,T_list[i][j],left=ST_list[i][j],color=color_map[i][j])plt.text(ST_list[i][j]+T_list[i][j]*0.5,-i-1,GONGXU_list[i][j],ha="center",va="center",size=15)
plt.yticks([-1,-2,-3,-5,-6,-7,-8,-9,-10,-11,-12,-13],[1,2,3,5,6,7,8,9,10,11,12,13])labels =[''] *5
for i in range(5):labels[i] = "工件%d" % (i + 1)
# 图例绘制
patches = [mpatches.Patch(color=colors[i], label="{:s}".format(labels[i])) for i in range(5)]
plt.legend(handles=patches, loc=4)
# XY轴标签
plt.xlabel("加工时间/s")
plt.ylabel("机器编号")plt.show()