Job-shop调度问题（简称JSP）是现实许多生产和服务调度问题的数学模型，具有很强的应用背景。邻域结构真正将JSP求解算法的盲目搜索变得更加科学有效，然而，由于移动工序的尺度数目太少，其搜索能力受到一定制约。本课题从路径重连和移动工件视角，开展移动更多数目工序的大尺度增强搜索方法研究。首先，融合JSP领域知识，扩展研究常规路径重连搜索方法，并解决死锁和快速近似评价问题，实现对JSP求解的专业性和高效性；然后，研究基于障碍图模型导向的移动工件搜索技术，构建JSP的障碍图建模方法，探究障碍图中的路径规划对完工时间的影响机理，科学指导工件的移动，并解决相关关键技术；最后，融合上述两种大尺度搜索方法，以及邻域结构，实现多尺度协同综合搜索，设计求解JSP的混合智能算法。本课题研究成果有望成为继邻域结构之后，作为构造JSP高效调度算法新的共性关键技术，具有重要的基础意义和应用价值。

Job-shop scheduling problem (JSP) is the mathematical model of many production and service scheduling problems, which has strong application background. Neighborhood structure really makes the blind search of JSP solving algorithm more scientific and effective. Unfortunately, the searching ability of neighborhood structure is restricted due to the small number of moving operations. This project studies the large-scale enhanced search method of moving more operations from the perspective of path relinking and moving jobs. Firstly, the conventional path relinking method combining with JSP domain knowledge is discussed, also the problems of deadlock and fast approximation evaluation are solved, and to realize the specialty and efficiency for solving JSP. Then, the moving job search technology based on obstacle graph model is studied. The JSP obstacle modeling method is constructed. The mechanism of the effect of path planning in the obstacle graph on the completion time is explored, and to guide the movement of the jobs more scientifically. The relevant key technologies of moving job search are achieved. Finally, multi-scale collaborative comprehensive search is realized by combining the two large-scale search technologies and neighborhood structure, and to be used for designing the JSP hybrid intelligent algorithm. The results of this project are expected to become new common key technologies for constructing efficient JSP scheduling algorithm after the neighborhood structure, which have important basic significance and application value.