New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
为排序问题（特别是作业车间调度）开发了结合运筹学启发式与人工智能局部搜索的启发式方法，通过定义新的解空间和邻域结构，可适用于任何调度目标，并以最小化完工时间为例验证了有效性。
In this paper search heuristics are developed for generic sequencing problems with emphasis on job shop scheduling. The proposed methods integrate problem specific heuristics common to Operations Research and local search approaches from Artificial Intelligence in order to obtain desirable properties from both. The applicability of local search to a wide range of problems, and the incorporation of problem-specific information are both properties of the proposed algorithms. Two methods are proposed, both of which are based on novel definitions of solution spaces and of neighborhoods in these spaces. Applications of the proposed methodology are developed for job shop scheduling problems, and can be easily applied with any scheduling objective. To demonstrate effectiveness, the method is tested on the job shop scheduling problem with the minimum makespan objective. Encouraging results are obtained.