期刊
COMPUTERS & OPERATIONS RESEARCH
卷 90, 期 -, 页码 60-71出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2017.09.017
关键词
Local search; Dynamic programming; Job shop scheduling; Metaheuristics
类别
资金
- Grants-in-Aid for Scientific Research [17K00342] Funding Source: KAKEN
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. (c) 2017 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据