论文部分内容阅读
Job-shop调度问题是生产调度领域的一个热点、难点，是许多实际生产调度问题的典型调度简化模型，是一类典型的NP-hard问题，对它的研究具有重要的理论意义和应用价值。
针对以最小化最大完工时间（Makespan）为目标的Job-shop问题，本文提出一种基于禁忌搜索（TS）和移动瓶颈过程（SB）的混合启发式算法HTS_SB。具体研究内容和成果如下：
（1）禁忌搜索的性能与初始解有密切关系，从优质解和劣质解出发进行的搜索有时在性能上的差别是相当可观的；针对这一特性，本文提出以移动瓶颈过程来产生优质的初始解，为HTS_SB算法的主体过程禁忌搜索奠定基础。
（2）邻域结构对禁忌搜索的性能影响很大，一个好的邻域结构应尽量避免对无用解的搜索，并要对搜索范围进行很好的控制，搜索范围太大或太小都会对搜索过程产生负面影响。鉴于此，本文在已提出的关于邻域结构的理论证明和结论的基础上，结合现有高效的邻域结构，提出一种新的邻域结构，同时采用动态的禁忌列表，提高算法的搜索能力，将邻域搜索算法的复杂度降低。
（3）对产生初始解的移动瓶颈过程主体Schrage算法进行改进，引入扰乱因子，打破Schrage算法原有的优先级顺序，将其从精确算法演变为近似算法，从而搜索更优的初始解。
（4）如在移动瓶颈过程中采用Carlier，则可能存在不可行解的问题。针对这个特点，对移动瓶颈算法进行修改，在对单机调度时用Schrage算法来代替Carlier算法，避免产生不可行解。
将HTS_SB算法应用于解决标准测试实例问题，实验结果表明：在以最小化Makespan为目标函数的Job-shop问题中，HTS_SB算法在CPU时间、平均相对误差（MRE）等方面都得到了较好的结果，是一种有效地解决Job-shop的算法。