Computer Science – Artificial Intelligence
Scientific paper
2011-09-27
Computer Science
Artificial Intelligence
Principles and Practice of Constraint Programming - CP 2011, Perugia : Italy (2011)
Scientific paper
10.1007/978-3-642-23786-7
Recently, a variety of constraint programming and Boolean satisfiability approaches to scheduling problems have been introduced. They have in common the use of relatively simple propagation mechanisms and an adaptive way to focus on the most constrained part of the problem. In some cases, these methods compare favorably to more classical constraint programming methods relying on propagation algorithms for global unary or cumulative resource constraints and dedicated search heuristics. In particular, we described an approach that combines restarting, with a generic adaptive heuristic and solution guided branching on a simple model based on a decomposition of disjunctive constraints. In this paper, we introduce an adaptation of this technique for an important subclass of job shop scheduling problems (JSPs), where the objective function involves minimization of earliness/tardiness costs. We further show that our technique can be improved by adding domain specific information for one variant of the JSP (involving time lag constraints). In particular we introduce a dedicated greedy heuristic, and an improved model for the case where the maximal time lag is 0 (also referred to as no-wait JSPs).
Grimes Diarmuid
Hebrard Emmanuel
No associations
LandOfFree
Models and Strategies for Variants of the Job Shop Scheduling Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Models and Strategies for Variants of the Job Shop Scheduling Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Models and Strategies for Variants of the Job Shop Scheduling Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-63158