Principles and practice of constraint programming -- CP 2011. 17th international conference, CP 2011, Perugia, Italy, September 12--16, 2011. Proceedings

DOI10.1007/978-3-642-23786-7MaRDI QIDQ637054zbMATH OpenOpenAlexFDO

Authors

Publication date 2 September 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.5920

Mathematics Subject Classification ID

Proceedings of conferences of miscellaneous specific interest (00B25) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: 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).

Recommendations

• Principles and practice of constraint programming. 19th international conference, CP 2013, Uppsala, Sweden, September 16--20, 2013. Proceedings
• Principles and practice of constraint programming. 21st international conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015. Proceedings
• Principles and practice of constraint programming -- CP 2007. 13th international conference, CP 2007, Providence, RI, USA, September 23--27, 2007. Proceedings
• Principles and practice of constraint programming -- CP 2005. 11th international conference, CP 2005, Sitges, Spain, October 1--5, 2005. Proceedings
• Principles and practice of constraint programming -- CP 2001. 7th international conference, Paphos, Cyprus, November 26 -- December 1, 2001. Proceedings
• Principles and practice of constraint programming. 20th international conference, CP 2014, Lyon, France, September 8--12, 2014. Proceedings
• Principles and practice of constraint programming -- CP 2010. 16th international conference, CP 2010, St. Andrews, Scotland, September 6--10, 2010. Proceedings
• Principles and practice of constraint programming. 18th international conference, CP 2012, Québec City, QC, Canada, October 8--12, 2012. Proceedings
• Principles and practice of constraint programming -- CP 2006. 12th international conference, CP 2006, Nantes, France, September 25--29, 2006. Proceedings

Cited in

(5)

• A global constraint for over-approximation of real-time streams
• The dial-A-ride problem with transfers
• Myrvold's results on orthogonal triples of 10 10 Latin squares: a SAT investigation
• Generating streamlining constraints with large language models
• Principles and practice of constraint programming -- CP 2009. 15th international conference, CP 2009, Lisbon, Portugal, September 20--24, 2009. Proceedings

This page was built for publication: Principles and practice of constraint programming -- CP 2011. 17th international conference, CP 2011, Perugia, Italy, September 12--16, 2011. Proceedings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q637054)