在现代生产与作业管理领域，排程是一个重要的研究主题。排程涉及到如何合理分配有限的资源以完成特定的任务，以期达到预定的生产目标。然而，在实际操作过程中，由于各种不确定因素的存在，使得排程问题变得尤为复杂。特别是在制造业中，工件的加工时间由于机器状况、工人的技能水平以及物料质量等多种因素的影响，并不是固定不变的。这种加工时间的不确定性给传统的排程方法带来了巨大的挑战。
针对这一问题，许晓晴、崔文田等人提出了在不确定加工时间下，针对同型并行机的作业排程问题，并以工期（最大完工时间）作为目标来研究鲁棒排程方法。在他们的研究中，加工时间不是以精确的数值给出，而是以区间值来表示，这种方式避免了对未知概率分布的依赖，使模型更适用于缺乏历史数据或数据不完整的情况。
为了应对不确定加工时间带来的问题，许晓晴等采用了最小最大遗憾准则。这一准则的目标是在最坏情况下，使得系统表现出最小的遗憾值。遗憾值是指实际完成时间与理想状态（如最短可能时间）之间的差值。最小最大遗憾准则就是通过选择最优化策略，使得可能的最大遗憾值最小化。
研究中提出的问题被证明是NP-难问题，这类问题的特点是不存在多项式时间的精确解法，即使是对问题规模较小的实例进行求解，也可能在计算上非常困难。因此，为了简化问题并便于求解，许晓晴等给出了计算最大遗憾的公式，并证明了在不确定加工时间的区间内，最坏情况往往出现在区间的端点，即工件的加工时间要么是其区间的上限，要么是下限。
在提出鲁棒排程模型的基础上，研究者们设计了一种迭代松弛算法，这是一种求解优化问题的迭代方法。它通过逐步放松约束条件，不断接近最优解的过程。该算法不仅能够找到鲁棒排程的最优解，而且还分析了其计算量。通过分析算法的计算复杂度，可以评估解决问题的效率和可行性。
文章的关键词包括“同型并行机”、“加工时间不确定”、“最小最大遗憾”和“迭代松弛算法”。这些关键词准确概括了文章的核心内容。同型并行机是指多台性能相同、可以执行相同任务的机器，这在现实中指的是多台相同的加工中心、机床等。加工时间的不确定性则是指工件在这些机器上加工所需时间并不是一个确定值，而是有范围的估计。最小最大遗憾准则以及迭代松弛算法是解决不确定加工时间排程问题时采用的方法论和技术手段。
总结来说，许晓晴等人的工作为在不确定加工时间下同型并行机的鲁棒排程问题提供了一个新的视角和解决方案。他们不仅证明了该问题的复杂性，还提出了一个具体的算法来寻找最优解，并对其计算复杂度进行了分析。该研究不仅在理论上有重要意义，也对实际生产排程具有实际应用价值，特别是在缺乏历史数据、面临不确定因素时的生产排程中尤为重要。研究的未来方向可能包括算法的进一步优化、模型在不同类型问题中的适用性拓展以及对其他不确定因素处理方法的研究。
