目录
1 引言 1
2 算法设计 3
3 实验 5
3.1 实验设置 5
3.2 实验结果 5
4 总结 8
参考文献: 8
摘  要: 流水车间调度问题是一种用于解决调度问题的简化模型，在本文中，模拟退火算法被尝试用来解决这一问题，并设置温度衰减常数，起始温度，终止温度等多个超参数，探寻不同参数设置下算法的结果优劣。流水车间假设n 个工件要在 m 台机器上加工，每个工件需要依次经过 m 道工序，分别对应m台不同的机器，每个机器同时只能加工一个工件，每个工件只能由一台机器同时加工并且每个工件的特定工序所需的时间是固定的，预期在这样的前提下计算出完工的最短时间吗，如Fig.1所示例子。模拟退火[1]算法是一种基于蒙特卡洛思想设计的近似求解最优化问题的方法，主要应用热力学的理论，将可行解空间内每一个点想像成空气内的分子，分子的能量由温度决定，同时分子的能量也代表其稳定性。首先，在空间中随机选取一个点作为初始解，接下来求取这个点周围邻居粒子的能量，再根据温度和能量差计算阙值概率，以此来判断是否要使用新的解替换当前解。通过实验，我们在车间调度的十个用例上都得到了相对可观的结果，并初步得到了不同超参数设置对算法性能影响的初步假设。
Fig.1 车间调度问题实例
关键词: 车间调度问题，模拟退火算法，超参数调节