Job-shop调度问题的大尺度增强搜索基础方法及混合算法研究

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.

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

本课题通过研究作业车间调度问题（简称JSP问题）移动更多数目工序，并且融合问题领域知识的大尺度增强搜索方法，突破邻域结构搜索方法的制约局限性，以进一步提升JSP智能算法的求解性能。圆满完成了预期目标，具体如下：.1) 建立了与JSP领域知识紧密结合的路径重连搜索方法，基于正向无延迟和反向无延迟调度，设计路径重连过程中的起始解和导向解，以及基于邻域结构的路径解产生策略，提高其有效性，从而实现大尺度增强搜索。.2) 拓展了仅针对2工件JSP情形的障碍图模型，研究了针对多工件JSP情形的障碍图建模方法，特别是快速有效的障碍图模型路径规划算法，进一步丰富了JSP调度理论成果，为新的求解方法提供理论支撑和指导。.3) 构建了基于障碍图模型导向的移动工件搜索方法，探究JSP障碍图模型中的路径规划对最终调度完工时间的影响机理，以及提出两种有效的多工序联动邻域结构，并解决死锁、新解快速评价等相关关键技术，实现大尺度增强搜索。.4) 实现融合邻域结构、路径重连、移动工件搜索高效协同的综合尺度搜索，混合智能算法，设计开发了JSP高效求解算法，通过对JSP问题国际基准算例进行测试，结果表明，所提算法的性能达到了目前已发表文献中算法的前沿水平，为提高车间生产效率提供了有力方法支撑。