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

Algorithm design and analysis of parallel Job Shop scheduling

作　　者：胡觉亮[1] 王学士[1] 董建明[1] 

机构地区：[1]浙江理工大学理学院,浙江杭州310018

出　　处：《计算机集成制造系统》2014年第1期182-189,共8页Computer Integrated Manufacturing Systems

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

摘　　要：针对一类极小化加工费用和延期惩罚费用之和的新型平行异顺序作业调度问题,给出了问题的整数规划模型,证明了NP困难性。通过分析最优解具有的性质,提出一种改进的禁忌搜索算法。该算法一方面采用一种快速的初始解构造方法获得较好的初始解,另一方面通过设计禁忌表、引入关键表等方法给出一种改进的搜索策略,使得最优解的搜索过程在全局和局部搜索之间达到较好的平衡,从而提高算法的收敛速度。通过大量数值实验验证了算法的有效性。For a new parallel Job Shop scheduling problem with the objective of minimizing the total cost for process- ing and the Job tardiness, both an integer programming model and an NP-hardness proof were provided. By analy- zing the properties of the optimal solutions, an improved tabu search algorithm was proposed. The algorithm used a quick method to produce better initial solutions in one hand, and an improved searching method was given by intro- ducing the tabu table and the critical table on the other hand, which made a good trade-off between the global and the local search for optimal solutions and improved the convergence speed of the algorithm. The numerical experi- ments were used to validate the effectiveness of the proposed algorithm.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]