流水车间调度问题的拉格朗日松弛中的一种新的概率近似次梯度法

调度在企业制造系统中起着关键作用，因为它大大提高了效率和竞争力，这一点已被广泛接受。 流水车间调度问题是一种典型的问题，涉及许多实际问题。 由于流水车间调度问题是NP难题，因此在大规模情况下，在较短的CPU时间内获得令人满意的解决方案具有实际价值。 拉格朗日松弛（LR）是一种可以处理大规模可分离问题的方法。 通过LR方法，可以将一个复杂的问题分为几个较小的子问题，这些子问题更容易解决。 但是，存在一个关键挑战，即拉格朗日乘数可能会缓慢收敛。 本文提出了一种新的概率近似次梯度法（PASG），其中使用智能优化算法来获取适当的方向以改进拉格朗日乘数。 PASG方法可以合理地分配计算时间，并在有限的计算时间内获得令人满意的进度表。 随着计算时间的延长，获得最佳解的可能性收敛至1。PASG方法的有效性通过对大规模和长期水平问题的数值测试结果得到证明。