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

Abstract: For a new parallel Job Shop scheduling problem with the objective of minimizing the total cost for processing and the Job tardiness, both an integer programming model and an NP-hardness proof were provided. By analyzing 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 introducing 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 experiments were used to validate the effectiveness of the proposed algorithm.

Key words: parallel Job Shop scheduling|integer programming model|Jackson algorithm|tabu search