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

来源：计算机集成制造系统杂志2014年第1期北京时间：

作者：胡觉亮，王学士，董建明

单位：浙江理工大学理学院

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

关键词：平行异顺序作业调度|整数规划模型|Jackson算法|禁忌搜索

基金资助：国家自然科学基金资助项目(11071220,11001242,11201428)；浙江省自然科学基金资助项目(LY13A010015)