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

# 退火算法对车间调度问题求解分析及最适参数探究 作者姓名 陈浩权(学号: 1120191160) **摘 要:** 流水车间调度问题是一种用于解决调度问题的简化模型，在本文中，模拟退火算法被尝试用来解决这一问题，并设置温度衰减常数，起始温度，终止温度等多个超参数，探寻不同参数设置下算法的结果优劣。流水车间假设 n 个工件要在 m 台机器上加工，每个工件需要依次经过 m 道工序，分别对应 m 台不同的机器，每个机器同时只能加工一个工件，每个工件只能由一台机器同时加工并且每个工件的特定工序所需的时间是固定的，预期在这样的前提下计算出完工的最短时间吗，如 Fig.1 所示例子。模拟退火[1]算法是一种基于蒙特卡洛思想设计的近似求解最优化问题的方法，主要应用热力学的理论，将可行解空间内每一个点想像成空气内的分子，分子的能量由温度决定，同时分子的能量也代表其稳定性。首先，在空间中随机选取一个点作为初始解，接下来求取这个点周围邻居粒子的能量，再根据温度和能量差计算阙值概率，以此来判断是否要使用新的解替换当前解。通过实验，我们在车间调度的十个用例上都得到了相对可观的结果，并初步得到了不同超参数设置对算法性能影响的初步假设。  Fig.1 车间调度问题实例 关键词: 车间调度问题，模拟退火算法，超参数调节 ## 一、引言 问题背景介绍：在如今工业化的生产背景之下，随着产品生产所需的工作流程，生产环节越来越复杂，规划出具有更强泛化能力和鲁棒性的生产调度方案变得至关重要。流水车间调度问题是很多实际流水线生产调度问题的简化模型，对于这一问题，如果使用传统的线性优化，很容易陷入局部最优解并且由于大多数的调度问题本身都是 NP 难问题，所以传统方法一般很难得到令人满意的答案。目前学者们正在尝试应用智能优化算法进行求解，其中，段海滨等人提出蚁群算法在这一问题上有良好的自适应性[3]，但是对于大规模的仿真情景还需要进一步研究，王万良等人将改进后的遗传算法作为求解手段,不但提高了收敛速度.而且在搜索过程中系统能够自动给定交叉概率和变异概率[4]，但是计算量较大，对于计算能力的要求过高。在本文中，我们使用模拟退火算法来对这一问题尝试求解。 关于车间调度问题，有以下已知条件： 有 n 个工件需要在 m 台机器上流水加工，各个工件在各个机器上的加工时间（共 n * m 个数字） 每个工件均在 0 时刻释放 每个机器同时只能加工一个工件 一个工件不能同时在不同的机器上加工，每个工件的加工顺序相同，从第一台机器至最后一台机器 数学语言描述： Table.1 符号表 | 符号 | 含义 | | ------ | ------------------------------------------------ | | m | 拥有的机器台数 | | n | 需加工的工件个数 | | Te | 算法开始时的初始速度 | | Temin | 算法的温度下限 | | Tn*m | Tij 表示第 i 个工件需要在第 j 个机器上加工的时间 | | Sn*m | Sij 第 i 个工件在第 j 个机器上开始加工的时间 | | Ansm*n | Ansij 表示第 i 个机器加工完第 j 个工件的时间 | 根据已知条件 2，可得约束条件(1)：Si1 >= 0, i=1,2,3…n 根据已知条件 3，可得约束条件(2)：Sjk+Tjk <= Sik or Sjk >= Sik+Tik, i=1, 2, …, n, j=1, …, i1, i+1, …, n, k=1, 2, …, m. 也就是说，任取工件 i 和工件 j, 在工件 i 进行第 k 道工序的时候，要么 j 已经进行完毕这道工序，要么工件 i 执行完这道工序后 j 还没有开始执行（一台机器同时只能加工一个工件） 根据已知条件 4，可得约束条件(3)：Sij >= Si(j1) + Ti(j1), i=1,2,…,n, j=2,…,m. 则整个优化问题可以用如下数学语言表示： ```c++ Min (max (SiM+TiM)), i=1, 2, …, n. //优化目标 st: ``` ：Si1 >= 0, i=1,2,3…n //约束条件 (1) ：Sjk + Tjk <= Sik or Sjk >= Sik + Tik, i= 1, 2, …, n, j=1, …, i1, i+1, …, n, k=1, 2, …, m /约束条件 (2) ：Sij >= Si(j1) + Ti(j1), i=1, 2, …, n, j=2, …, m. //约束条件 (3) 但是，在这里我们只考虑简化之后的现代流水车间调度问题，也就是工件的加工顺序在每个工序上都是一样的。所以最终我们可以使用动态规划的方法，得到转移方程，用于求解在确定加工顺序下的最小加工时间(order0 表示我们选择的加工顺序): ```c++ = 1, S[i, j] = S[i, j-1] + T[order0[j]][i] != 1, S[i, j] =max(S[i - 1, j], S[i, j - 1]) + T[order0[j]][i] ``` 解决方法介绍及结果总结 本文所使用的算法为模拟退火算法，模拟退火算法是 1983 年由 Kirkpatrick 等人提出，用于解决局部最优解的问题。本算法是通过模拟真实世界中的分子和原子的物理规律而进行设计的，在物理学中，粒子所具有的能量和其所处的温度往往成正比关系，温度越高，分子能量越大，分子越不稳定，能量越低，分子能量越小，分子越稳定。退火这一名词在物理学中的意思是给固体加热再冷却，随着温度缓慢下降，固体中的原子按照一定形状排列，形成高密度、低能量的有规则晶体，对应于算法中的全局最优解。在此问题中，我们将可行解空间中的每一个点都作为一个分子，并且规定分子的能量只有温度有关，温度越高，分子越不稳定，也就越容易越变到一个相对更稳定的状态，我们将此分子对应解的质量作为其稳定程度，解的质量越高，分子越稳定。 本实验的关键步骤如下 ① 选取解空间中任意一个点作为初始解，选取合适的 Te, Temin，降温过程 ② 比较当前解周围的点的解的质量，如果质量更好，则替换当前解，否则以一定的概率替换当前解 ③ 在每个温度下执行多次，寻找当前温度下的最优解 ④ 随温度衰减，不断进行这一过程，直到温度降低为最低温度限，得出结果 ⑤ 更改 Te, Temin，降温过程，重新求解，进行比较，得到当前的最优解。 ⑥ 多次执行过程 ①~⑤，通过比较得到最优解和最优的超参数 本文通过模拟退火算法求解车间调度问题，经测试在十个用例上都得到了可观的结果。并且本文继续探寻了不同的参数设置对退火算法性能的影响，初步得到了结论并进行了简单的分析。 本文后续部分组织如下。第 2 节详细陈述使用的方法，第 3 节报告实验结果，第 4 节对讨论本文的方法并总结全文。 ## 二、算法设计 设计思路及算法介绍 本算法的思路为，先在解空间中任取一个点作为当前解，接下来选取当前解周围的点计算周围解的质量，如果周围点的解的质量较高，则选取新解替代当前解，否则根据温度和能量差得出阈值，并以此阈值为概率决定是否接受新解，如此迭代直到温度降低到最低温度。 模拟退火算法的官方定义为：模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，