基于局部搜索策略的车间作业调度问题的算法研究

Algorithm Based on Local Search for the Arrangement of Job Shop Scheduling

为车间作业调度问题提供了一个快速、易于实现的近似算法.该算法基于局部搜索策略,采用特殊的邻域构造方法,即邻域的构造仅与关键路径上的工序相关.该算法找到了所测试的14个标准算例中12算例的最优解,而且在PII233的计算机上每个算例的计算时间不超过1s.

A fast and easy-implemented algorithm is presented in this article. The algorithm is based on local search strategy with a special neighborhood structure which is constructed through swapping the operations on the critical path. We find the best solutions to 12 instances among 14 instances tested, it takes no more than 1 second in computing an instance on a personal computer with a PII 233 CPU.