A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem
A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem
复制标题
DOI：
10.1016/j.cor.2017.09.017
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Y. Nagata;I. Ono
中科院分区：
文献类型：
--
作者：
Y. Nagata;I. Ono
提出了一种基于局部搜索的部分解空间作业车间调度问题的求解方法。该方法迭代求解一系列约束满足问题（CSP），其中当前的约束满足问题被定义为原始的车间作业计划，并附加了一个约束，即最大完工时间小于通过求解前一个约束满足问题获得的调度时间。为了获得当前CSP的解决方案，在局部解空间中执行基于局部搜索的过程，其中当前解决方案被表示为局部调度。该邻域由一组部分时间表组成，其最大完工时间小于通过求解以前的CSP得到的最好的完全时间表。存在的附加约束的最大完工时间限制可能的本地移动，以满足必要的条件，以改善最好的到目前为止完成的时间表。这些动作有效地枚举使用动态规划为基础的算法，我们在本文中提出。我们还提出了一个有效的策略，选择下一个部分的解决方案，从附近，扰动过程，禁忌搜索过程，所有这些都嵌入到基本框架，以提高性能。
This paper presents a local search-based method that works in partial solution space for solving the job shop scheduling problem (JSP). The proposed method iteratively solves a series of constraint satisfaction problems (CSPs), where the current CSP is defined as the original JSP with an additional constraint that the makespan is smaller than that of the schedule obtained by solving the previous CSP. To obtain a solution to the current CSP, a local search-based procedure is performed in a partial solution space where the current solution is represented as a partial schedule. The neighborhood consists of a set of partial schedules whose makespan is less than that of the best-so-far complete schedule obtained by solving the previous CSP. The existence of the additional constraint on the makespan restricts possible local moves to those that satisfy necessary conditions to improve the best-so-far complete schedule. These moves are efficiently enumerated by using a dynamic programming-based algorithm we present in this paper. We also present an effective strategy of selecting next partial solution from the neighborhood, perturbation procedure, and tabu-search procedure, all of which are embedded into the basic framework to enhance the performance.