基于Python的退火算法对车间调度问题求解分析及最适参数探究

约定不等于承诺〃 2024-04-07 12:08 58阅读 0赞

摘 要: 流水车间调度问题是一种用于解决调度问题的简化模型，在本文中，模拟退火算法被尝试用来解决这一问题，并设置温度衰减常数，起始温度，终止温度等多个超参数，探寻不同参数设置下算法的结果优劣。流水车间假设n 个工件要在 m 台机器上加工，每个工件需要依次经过 m 道工序，分别对应m台不同的机器，每个机器同时只能加工一个工件，每个工件只能由一台机器同时加工并且每个工件的特定工序所需的时间是固定的，预期在这样的前提下计算出完工的最短时间吗，如Fig.1所示例子。模拟退火\[1\]算法是一种基于蒙特卡洛思想设计的近似求解最优化问题的方法，主要应用热力学的理论，将可行解空间内每一个点想像成空气内的分子，分子的能量由温度决定，同时分子的能量也代表其稳定性。首先，在空间中随机选取一个点作为初始解，接下来求取这个点周围邻居粒子的能量，再根据温度和能量差计算阙值概率，以此来判断是否要使用新的解替换当前解。通过实验，我们在车间调度的十个用例上都得到了相对可观的结果，并初步得到了不同超参数设置对算法性能影响的初步假设。  
Fig.1 车间调度问题实例  
关键词: 车间调度问题，模拟退火算法，超参数调节  
1 引言  
a) 问题背景介绍：在如今工业化的生产背景之下，随着产品生产所需的工作流程，生产环节越来越复杂，规划出具有更强泛化能力和鲁棒性的生产调度方案变得至关重要。流水车间调度问题是很多实际流水线生产调度问题的简化模型，对于这一问题，如果使用传统的线性优化，很容易陷入局部最优解并且由于大多数的调度问题本身都是NP难问题，所以传统方法一般很难得到令人满意的答案。目前学者们正在尝试应用智能优化算法进行求解，其中，段海滨等人提出蚁群算法在这一问题上有良好的自适应性\[3\]，但是对于大规模的仿真情景还需要进一步研究，王万良等人将改进后的遗传算法作为求解手段,不但提高了收敛速度.而且在搜索过程中系统能够自动给定交叉概率和变异概率\[4\]，但是计算量较大，对于计算能力的要求过高。在本文中，我们使用模拟退火算法来对这一问题尝试求解。本文转载自http://www.biyezuopin.vip/onews.asp?id=15755

# # Press th1
    # green button in the gutter to run the script.
    import numpy as np
    from inputdata import *
    from simulated_annealing import *
    if __name__ == '__main__':
        maxn = 60
        maxm = 30
        T = np.zeros([maxn, maxm]) #存储每个工件在每个机器上的加工时间， T[i, j]表示第i个工件在第j个机器上所需的加工时间
        m = 0
        n = 0
        T, n, m = inputdata(T, n, m)   #输入数据
        #将所有的超参数的取值分别存放在列表中
        srate = [0.85, 0.80, 0.90, 0.95]
        sT1 = [10000, 5000, 8000, 15000, 20000]
        sT2 = [1, 5, 10, 20, 50]
        stime1 = [100, 50, 150, 200]
        stime2 = [100, 50, 150, 200]
    
    
        print("默认参数下，求得的解为：") #输出默认参数下的解
        simulated_annealing(T, m, n, 0.85, 10000, 1, 100, 100)
    
    
        print("实验1: 改变温度衰减系数\n")
        for i in range(0, 4):  #分别尝试温度衰减系数为0.80, 0.85, 0.90, 0.95
            rate = float(srate[i])
            simulated_annealing(T, m, n, rate, 10000, 1, 100, 100)
    
    
        print("实验2: 改变起始温度\n")
        for i in range(0, 5): #分别尝试起始温度为5000, 8000, 10000, 15000, 20000
            T1 = sT1[i]
            simulated_annealing(T, m, n, 0.85, T1, 1, 100, 100)
    
    
        print("实验3: 改变结束温度\n")
        for i in range(0, 5): #分别尝试终止温度为1, 5, 10, 20, 50
            T2 = sT2[i]
            simulated_annealing(T, m, n, 0.85, 10000, T2, 100, 100)
    
    
        print("实验4: 改变退火算法迭代总次数\n")
        for i in range(0, 4): #分别尝试退火算法迭代总次数为50， 100， 150， 200
            time1 = stime1[i]
            simulated_annealing(T, m, n, 0.85, 10000, 1, time1, 100)
    
    
        print("实验5: 改变单一温度下迭代总次数\n")
        for i in range(0, 4): #分别尝试单一温度迭代总次数为50， 100， 150， 200
            time2 = stime2[i]
            simulated_annealing(T, m, n, 0.85, 10000, 1, 100, time2)
    
    # See PyCharm help at https://www.jetbrains.com/help/pycharm/

![在这里插入图片描述][48962caf994844778594e08afd2f262b.png_pic_center]  
![在这里插入图片描述][52754b5098f74ce28bad0a4d9ddf3bb3.png_pic_center]  
![在这里插入图片描述][2020674b8ca34230a69f05f5b5cd16ab.png_pic_center]  
![在这里插入图片描述][ac7319e54a74451f9e4c74fbf67da855.png_pic_center]

[48962caf994844778594e08afd2f262b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/89edbe5984a541e0a1929e3e7dda4f11.png
[52754b5098f74ce28bad0a4d9ddf3bb3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/fd7eb096a4604a1aa713a40f594ffa2e.png
[2020674b8ca34230a69f05f5b5cd16ab.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/0e9a194593e94098bcb2ac591a37b568.png
[ac7319e54a74451f9e4c74fbf67da855.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3cc6190cc1374605b47c39e968b6514c.png