Job Shop 的工件序摄动分析算法

为了研究ＪｏｂＳｈｏｐ排序（ＪＳＰ）这样一类ＮＰ完备的组合优化问题，从离散事件仿真的角度分析了ＪｏｂＳｈｏｐ中工件序单步摄动和多步摄动出现时系统状态的变化规律，提出了一类求解ＪＳＰ问题的近似算法——工件序摄动分析算法（ＪＳＰＡ和ＪＳＥＰＡ），并研究了此类算法的应用模式。工件序摄动分析算法具有迭代性和构造性特点，兼顾ＪＳＰ问题求解的速度、精度和规模，能够对初始序点进行改进，获得较好的工件极小序（或最小序）。测试实验结果表明算法具有良好的整体性能。

Job sequence perturbation analysis algorithm for Job Shop scheduling problem

Job Shop scheduling problem (JSP) is an NP complete combinatorial optimization problem. A new kind of approximate algorithm, job sequence perturbation analysis algorithm, is proposed for analyzing JSP problem from the point of view of discrete event simulation. System behaviors are analyzed correspoding to one step and multi steps perturbed job sequence, and the rules of perturbation generation and propagation are given for these two kinds of perturbed job sequences. The new algorithm has the iterative and constructional characters, which can improve a job schedule's performance or generate a local optimal job schedule economically and quickly according to certain optimization rule. Two patterns for application of job sequence perturbation analysis algorithm are also suggested, and experimental results for 56 Job Shop instances indicate high quality of the new algorithm.