平行异顺序作业调度问题的算法设计及分析

针对一类极小化加工费用和延期惩罚费用之和的新型平行异顺序作业调度问题,给出了问题的整数规划模型,证明了NP困难性。通过分析最优解具有的性质,提出一种改进的禁忌搜索算法。该算法一方面采用一种快速的初始解构造方法获得较好的初始解,另一方面通过设计禁忌表、引入关键表等方法给出一种改进的搜索策略,使得最优解的搜索过程在全局和局部搜索之间达到较好的平衡,从而提高算法的收敛速度。通过大量数值实验验证了算法的有效性。