动态到达工件的并行机批调度：遗传算法与蚁群优化对比

在现代工业生产环境中，特别是在半导体加工和金属热处理等精密制造业中，批处理机起着至关重要的作用。杜冰、周盛超、李小林和陈华平等人针对这一背景，研究了一种特殊的并发机环境下的工件动态到达批调度问题。这个问题的挑战在于工件的到达时间并非预先确定，而是随时间动态变化，同时工件的尺寸也各不相同，这就增加了调度的复杂性。 该问题被证明是NP-hard的，这意味着它属于计算复杂度较高的问题，寻找最优解通常需要耗费大量计算资源。为了评估解决此类问题的有效性，研究者提出了下界算法作为性能基准，用来衡量他们提出的启发式算法，如ERT-LPT规则。ERT-LPT是一种基于最早到达时间和最晚处理时间（Earliest Arrival Time and Latest Processing Time）的策略，旨在尽可能地平衡工件的等待时间和处理时间。 在此基础上，研究人员进一步采用了进化计算方法来求解问题，即遗传算法（Genetic Algorithm, GA）和蚂蚁群优化算法（Ant Colony Optimization, ACO）。这些算法的目标是最小化最大完工时间，也就是让所有工件在并行机上完成的时间尽可能一致，以提高整体生产效率。 通过实验对比，结果显示遗传算法在处理小型工件时表现出较好的性能，而蚂蚁群优化算法在面对大型工件时则更胜一筹。这表明，针对不同的工件规模，选择合适的算法对于优化动态到达批调度问题至关重要。此外，研究还展示了启发式算法BFLPT-ERTLPT（BE）与遗传算法和蚂蚁群优化算法之间的性能差异，表明后两者在解决复杂动态批调度问题时具有明显优势。 这项研究不仅提供了处理工件动态到达和尺寸差异的并行批调度问题的新方法，还为优化工业生产中的资源分配和调度提供了理论依据。其研究成果对提高生产效率、降低能耗和响应市场变化具有实际意义，并可能推动相关领域进一步的研究和实践发展。