【摘要】 对以Makespan最小为目标的Job Shop调度问题进行了研究。首先对Job Shop调度问题进行了描述,在此基础上建立了一种求解Job Shop调度问题的启发式优化算法———基于过滤定向搜索的算法,同时结合实例对算法的优化过程作了具体描述。最后通过不同规模的Benchmark实例对该算法进行了仿真评价,结果表明基于过滤定向搜索的算法搜索效率高,解的性能好,是一种有效的优化算法。更多还原

【Abstract】 The job shop scheduling problems are researched with the objective of minimum makespan. Firstly, based on the descriptions of job shop scheduling problems, a heuristic optimization algorithm for solving job shop scheduling problems——a filter based beam search algorithm, is presented. Then the optimization process of the algorithm is described in detail and illustrated by a numerical example. Finally, benchmarks of different scales are computed through the algorithm. Computational results show that the algorithm is efficient and the solution quality is high, the algorithm is competitive and promising for solving the job shop scheduling problems.更多还原