期刊
INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING
卷 9075, 期 -, 页码 437-453出版社
SPRINGER-VERLAG BERLIN
DOI: 10.1007/978-3-319-18008-3_30
关键词
Constraint programming; Scheduling; Search; Job shop; Job shop with Operators; Flexible job shop; RCPSP; RCPSP/max; Multi-mode RCPSP; Multi-mode RCPSP/max; CPLEX; CP optimizer
This paper presents a new constraint programming search algorithm that is designed for a broad class of scheduling problems. Failure-directed Search (FDS) assumes that there is no (better) solution or that such a solution is very hard to find. Therefore, instead of looking for solution(s), it focuses on a systematic exploration of the search space, first eliminating assignments that are most likely to fail. It is a plan B strategy that is used once a less systematic plan A strategy here, Large Neighborhood Search (LNS) - is not able to improve current solution any more. LNS and FDS form the basis of the automatic search for scheduling problems in CP Optimizer, part of IBM ILOG CPLEX Optimization Studio. FDS and LNS+FDS (the default search in CP Optimizer) are tested on a range of scheduling benchmarks: Job Shop, Job Shop with Operators, Flexible Job Shop, RCPSP, RCPSP/max, Multi-mode RCPSP and Multi-mode RCPSP/max. Results show that the proposed search algorithm often improves best-known lower and upper bounds and closes many open instances.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据