Abstract: A multi-objective optimization method for Job-shop scheduling is proposed.In the method，an optimal Job-shop scheduling model is established.The objective of the model is to minimize the Average Flow Time（AFT） and overall completion time（makespan） of all workpieces.Aiming at the model，a taboo searching algorithm based on multi-stage hybrid mutation is proposed.To improve the convergence of the algorithm，inverse order mutation and gene segment swap mutation is used to find a good original solution，based on which gene swap mutation is used to find the approximate optimal solution.The algorithm is applied to ten benchmark Job-shop examples，and the result validates the correctness and effectiveness of the optimization method proposed in this paper.

Key words: Job-shop scheduling, taboo searching algorithm, multi-stage hybrid mutation

摘要： 提出了一类Job-shop多目标优化调度方法。构建了一个以工件平均流程时间最短、全部工件完工时间最短的Job-shop优化调度模型，并针对模型提出了一种分阶段混合变异的禁忌搜索算法。为增强算法收敛性，利用“逆序变异”和“基因段交换变异”找到了较好的初解，在此基础上利用“基因交换变异”继续搜索近优解。以10个算例验证了提出的Job-shop多目标优化调度方法的正确性和有效性。

关键词: Job-shop调度, 禁忌搜索算法, 分阶段混合变异