摘要
目前用于解决排列流水车间调度问题的元启发式算法主要直接探索搜索空间。本研究提出了一种新的分解技术，与这些方法不同，该技术通过反复求解单机器子问题，并将其解扩展到所有机器上，从而最小化总完成时间。为此，所提出的算法采用一种新颖的往返法来解决单机器问题，再通过任务的重复调整将解扩展到所有机器上。该算法会不断改进当前解，直到某台机器的最优排列无法进一步改善所有机器的整体排列，进而逐步优化当前解并引导搜索方向以获得高质量解。为进一步提升结果，单机器求解策略得出的任何解都会经过局部搜索过程进行优化。此外，还提出了一种创新的三角机制来构建初始解，旨在为算法提供高质量的起点。计算实验的结果不仅证明了单机器往返法的有效性，还表明该算法在解决标准基准问题时既具有鲁棒性又非常高效。
