作业车间调度优化算法

题目来源

题目来源于葛英飞《智能制造技术基础》书中175页的题目，基余分配率的作业车间调度优化算法。书中这部分有程序流程图，但是没有代码，课后闲暇之余通过Python对其进行了简单的实现，部分代码比较粗糙，仅仅实现了功能，未对其结构进行优化，供郑州科技学院智能制造专业各位同学参考。

代码实现

import numpy as np

def 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_sy



part_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()

原文地址：https://blog.csdn.net/qq_26657001/article/details/142977444

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！