作业车间调度问题的求解算法研究_王健伊.caj

作业车间调度问题是一个经典的 NP-Hard 类问题,自上世纪 50 年代开始,该类 调度问题越来越广泛地引起研究者的兴趣。该问题的精确求解算法能够保证找到问 题的最优解,但是需要指数级的计算时间,因此以启发式算法以及元启发式算法为 基础的近似求解算法逐渐成为研究的热点并取得了一些突破性的成果。 贪心类的启发式算法在求解作业车间调度问题时具有较快的计算速度,典型的算 法包括优先指派算法、贪心插入算法(INSA)等等。快速启发式算法 PD-INSA 将优 先指派算法与 INSA 算法的特点结合起来,该算法与 INSA 算法相比能够求得具有更 好优度的解。贪心类的算法在求解较为