{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T06:14:03Z","timestamp":1777529643210,"version":"3.51.4"},"reference-count":88,"publisher":"Maximum Academic Press","issue":"3","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Knowledge Engineering Review"],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>During recent years, the development of new techniques for constraint satisfaction, planning, and scheduling has received increased attention, and substantial effort has been invested in trying to exploit such techniques to find solutions to real-life problems. In this paper, we present a survey on constraint satisfaction, planning, and scheduling from the Artificial Intelligence point of view. In particular, we present the main definitions and techniques, and discuss possible ways of integrating such techniques. We also analyze the role of constraint satisfaction in planning and scheduling, and hint at some open research issues related to planning, scheduling, and constraint satisfaction.<\/jats:p>","DOI":"10.1017\/s0269888910000202","type":"journal-article","created":{"date-parts":[[2010,8,23]],"date-time":"2010-08-23T09:25:48Z","timestamp":1282555548000},"page":"249-279","source":"Crossref","is-referenced-by-count":29,"title":["New trends in constraint satisfaction, planning, and scheduling: a survey"],"prefix":"10.48130","volume":"25","author":[{"given":"Roman","family":"Bart\u00e1k","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Miguel A.","family":"Salido","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Francesca","family":"Rossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"27968","published-online":{"date-parts":[[2010,9,1]]},"reference":[{"key":"S0269888910000202_ref86","first-page":"19","article-title":"Understanding line drawings of scenes with shadows","author":"Waltz","year":"1975","journal-title":"The Psychology of Computer Vision"},{"key":"S0269888910000202_ref80","doi-asserted-by":"publisher","DOI":"10.1080\/095281399146607"},{"key":"S0269888910000202_ref68","first-page":"30","volume-title":"Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS 2005)","author":"Ruml","year":"2005"},{"key":"S0269888910000202_ref66","doi-asserted-by":"publisher","DOI":"10.1080\/095281398146941"},{"key":"S0269888910000202_ref71","article-title":"Hybrid solving for CSP","volume":"16","author":"Sadeh","year":"2003","journal-title":"ALP newsletter"},{"key":"S0269888910000202_ref78","unstructured":"van Beek P. , Chen X. 1999. CPlan: a constraint programming approach to planning. In Proceedings of AAAI-99, AAAI Press, Menlo Park, 585\u2013590."},{"key":"S0269888910000202_ref70","first-page":"206","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","author":"Sacerdoti","year":"1990"},{"key":"S0269888910000202_ref79","volume-title":"Constraint Satisfaction in Logic Programming","author":"van Hentenryck","year":"1989"},{"key":"S0269888910000202_ref75","first-page":"888","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","author":"Tate","year":"1977"},{"key":"S0269888910000202_ref72","doi-asserted-by":"crossref","unstructured":"Salido M. A. 2007. Distributed CSPs: why it is assumed a variable per agent? In Abstraction, Reformulation, and Approximation, 7th International Symposium (SARA 2007), Lecture Notes in Artificial Intelligence 4612, 407\u2013408, Springer-Verlag, Whistler, Canada.","DOI":"10.1007\/978-3-540-73580-9_38"},{"key":"S0269888910000202_ref82","doi-asserted-by":"crossref","unstructured":"Vil\u00edm P. 2004. O(n log n) filtering algorithms for unary resource constraint. In Proceedings of CP-AI-OR, Nice, France.","DOI":"10.1007\/978-3-540-24664-0_23"},{"key":"S0269888910000202_ref84","doi-asserted-by":"crossref","unstructured":"Vu X. H. , O\u2019Sullivan B. 2007. Semiring-based constraint acquisition. In Proceedings of ICTAI 2007, IEEE Computer Society, Patras, Greece, 251\u2013258.","DOI":"10.1109\/ICTAI.2007.160"},{"key":"S0269888910000202_ref77","volume-title":"Foundation of Constraint Satisfaction","author":"Tsang","year":"1993"},{"key":"S0269888910000202_ref74","first-page":"139","volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI)","author":"Smith","year":"1993"},{"key":"S0269888910000202_ref81","first-page":"570","volume-title":"Proceedings of AAAI-04","author":"Vidal","year":"2004"},{"key":"S0269888910000202_ref55","first-page":"90","volume-title":"Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS 2003)","author":"McCluskey","year":"2003"},{"key":"S0269888910000202_ref26","doi-asserted-by":"crossref","unstructured":"Cousot P. , Cousot R. 1977. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conference Record of the Sixth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, Los Angeles, California, New York, 238\u2013252.","DOI":"10.1145\/512950.512973"},{"key":"S0269888910000202_ref14","first-page":"44","volume-title":"Planning, Scheduling and Constraint Satisfaction","author":"Bart\u00e1k","year":"2007"},{"key":"S0269888910000202_ref85","volume-title":"Generating Semantic Description from Drawings of Scenes with Shadows","author":"Waltz","year":"1972"},{"key":"S0269888910000202_ref21","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1613\/jair.1234","article-title":"CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements","volume":"21","author":"Boutilier","year":"2004","journal-title":"JAIR"},{"key":"S0269888910000202_ref20","first-page":"1","article-title":"Lazy incremental learning of control knowledge for efficiently obtaining quality plans","author":"Borrajo","year":"1996","journal-title":"AI Review Journal. Special Issue on Lazy Learning"},{"key":"S0269888910000202_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90379-4"},{"key":"S0269888910000202_ref69","first-page":"123","article-title":"Constraint satisfaction\u2014a survey","volume":"11","author":"Ruttkay","year":"1998","journal-title":"CWI Quarterly"},{"key":"S0269888910000202_ref50","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00362-4"},{"key":"S0269888910000202_ref44","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1613\/jair.1705","article-title":"The fast downward planning system","volume":"26","author":"Helmert","year":"2006","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S0269888910000202_ref48","unstructured":"Khatib L. , Morris P. H. , Morris R. A. , Rossi F. 2001. Temporal constraint reasoning with preferences, Pages 322\u2013327 of IJCAI, Morgan Kaufmann."},{"key":"S0269888910000202_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90002-6"},{"key":"S0269888910000202_ref6","unstructured":"Baptiste P. , Le Pape C. , Nuijten W. 1995. Constraint-based optimization and approximation for job-shop scheduling. In Proceedings of the AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, IJCAI-95, Montr\u00e9al, Canada."},{"key":"S0269888910000202_ref87","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_50"},{"key":"S0269888910000202_ref5","volume-title":"Proceedings of the Fifteenth Workshop of the U.K. Planning Special Interest Group (PLANSIG)","author":"Baptiste","year":"1996"},{"key":"S0269888910000202_ref13","first-page":"525","volume-title":"Proceedings of the 21st International Florida AI Research Society Conference (FLAIRS 2008)","author":"Bart\u00e1k","year":"2008"},{"key":"S0269888910000202_ref56","first-page":"1319","volume-title":"Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI 2008)","author":"McGann","year":"2008"},{"key":"S0269888910000202_ref67","volume-title":"Handbook of Constraint Programming","author":"Rossi","year":"2006"},{"key":"S0269888910000202_ref45","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1613\/jair.855","article-title":"The FF planning system: fast plan generation through heuristic search","volume":"14","author":"Hoffmann","year":"2001","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S0269888910000202_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322292"},{"key":"S0269888910000202_ref76","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00497-X"},{"key":"S0269888910000202_ref9","unstructured":"Bart\u00e1k R. 1998. On-line Guide to Constraint Programming. http:\/\/kti.mff.cuni.cz\/~bartak\/constraints\/index.html"},{"key":"S0269888910000202_ref65","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4074.001.0001","volume-title":"Knowledge in Action: Logical Foundation for Specifying and Implementing Dynamic Systems","author":"Reiter","year":"2001"},{"key":"S0269888910000202_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511615320"},{"key":"S0269888910000202_ref73","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2006.05.090"},{"key":"S0269888910000202_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"S0269888910000202_ref43","first-page":"362","volume-title":"Proceedings of World Academy of Science, Engineering and Techniology","volume":"25","author":"Hatamlou","year":"2007"},{"key":"S0269888910000202_ref4","first-page":"311","volume-title":"Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98)","author":"Bacchus","year":"1998"},{"key":"S0269888910000202_ref35","first-page":"294","volume-title":"Proceedings of the National Conference on Artificial Intelligence","author":"Frost","year":"1994"},{"key":"S0269888910000202_ref37","unstructured":"Gaschnig J. 1979. Performance measurement and analysis of certain search algorithms. Technical report CMU-CS-79-124, Carnegie-Mellon University."},{"key":"S0269888910000202_ref40","first-page":"516","article-title":"Backtrack programming","volume":"12","author":"Golomb","year":"1965","journal-title":"Communications of the ACM"},{"key":"S0269888910000202_ref54","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5625.001.0001","volume-title":"Programming with Constraints: An Introduction","author":"Marriott","year":"1998"},{"key":"S0269888910000202_ref16","first-page":"175","article-title":"Abstracting soft constraints: framework, properties, examples","volume":"139","author":"Bistarelli","year":"2002","journal-title":"AI Journal"},{"key":"S0269888910000202_ref60","volume-title":"Low-cost Addition of Preferences to DTPs and TCSPs","author":"Peintner","year":"2004"},{"key":"S0269888910000202_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/182.358434"},{"key":"S0269888910000202_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S1574-6526(06)80026-X"},{"key":"S0269888910000202_ref10","doi-asserted-by":"publisher","DOI":"10.4018\/978-1-59140-450-7.ch010"},{"key":"S0269888910000202_ref59","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2005.25"},{"key":"S0269888910000202_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/b95712"},{"key":"S0269888910000202_ref61","first-page":"103","volume-title":"Proceedings of the International Conference on Knowledge Representation and Reasoning (KR)","author":"Penberthy","year":"1992"},{"key":"S0269888910000202_ref62","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"Pinedo","year":"2002"},{"key":"S0269888910000202_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-1479-4"},{"key":"S0269888910000202_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(71)90010-5"},{"key":"S0269888910000202_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00047-1"},{"key":"S0269888910000202_ref1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.34.3.391"},{"key":"S0269888910000202_ref47","unstructured":"Kautz H. , Selman B. 1992. Planning as satisfiability. In Proceedings of ECAI, IOS Press, Amsterdam, 359\u2013363."},{"key":"S0269888910000202_ref27","volume-title":"Constraint Processing","author":"Dechter","year":"2003"},{"key":"S0269888910000202_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73580-9_7"},{"key":"S0269888910000202_ref52","unstructured":"Lhomme O. 1993. Consistency techniques for numeric CSPs. In Proceedings of 13th International Joint Conference on Artificial Intelligence, Chamb\u00e9ry, France, 232\u2013238."},{"key":"S0269888910000202_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/361219.361224"},{"key":"S0269888910000202_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90006-6"},{"key":"S0269888910000202_ref36","unstructured":"Gaschnig J. 1977. A general backtrack algorithm that eliminates most redundant tests. In Procceedings of the International Joint Conference on Artifical Intelligence (IJCAI). Cambridge, MA, USA."},{"key":"S0269888910000202_ref63","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.1993.tb00310.x"},{"key":"S0269888910000202_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.10.001"},{"key":"S0269888910000202_ref25","unstructured":"Chen L. , Pu P. 2004. Survey of Preference Elicitation Methods. Technical report IC\/200467. Swiss Federal Institute of Technology in Lausanne (EPFL)."},{"key":"S0269888910000202_ref34","doi-asserted-by":"crossref","unstructured":"Freuder E. C. , Likitvivatanavong C. , Manuela M. , Rossi F. , Wallace R. J . 2003. Computing explanations and implications in preference-based configurators. In Proceedings of CSCLP, Lecture Notes in Computer Science 2627, 76\u201392, Springer.","DOI":"10.1007\/3-540-36607-5_6"},{"key":"S0269888910000202_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S026988890700104X"},{"key":"S0269888910000202_ref46","unstructured":"Jackson J. R. 1955. Scheduling a Production Line to Minimize Maximum Tardiness. Research report 43. Management Science Research Project, University of California."},{"key":"S0269888910000202_ref39","volume-title":"Automated Planning: Theory and Practice","author":"Ghallab","year":"2004"},{"key":"S0269888910000202_ref49","first-page":"32","article-title":"Algorithms for constraint satisfaction problems: a survey","volume":"13","author":"Kumar","year":"1992","journal-title":"AI Magazine"},{"key":"S0269888910000202_ref53","first-page":"954","volume-title":"Proceedings of IJCAI","author":"Lopez","year":"2003"},{"key":"S0269888910000202_ref17","doi-asserted-by":"crossref","unstructured":"Bistarelli S. , Pini M. S. , Rossi F. , Venable K. B. 2006. Bipolar preference problems: framework, properties and solving techniques. Lecture Notes in Computer Science 4651, Pages 78\u201392 of CSCLP, Springer.","DOI":"10.1007\/978-3-540-73817-6_5"},{"key":"S0269888910000202_ref30","volume-title":"Proceedings of IJCAI-07 Workshop on Distributed Constraint Reasoning","author":"Ezzahir","year":"2007"},{"key":"S0269888910000202_ref42","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90051-X"},{"key":"S0269888910000202_ref58","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00068-X"},{"key":"S0269888910000202_ref88","first-page":"614","volume-title":"12th International Conference on Distributed Computing Systems (ICDCS-92)","author":"Yokoo","year":"1992"},{"key":"S0269888910000202_ref23","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.2005.00278.x"},{"key":"S0269888910000202_ref38","doi-asserted-by":"crossref","unstructured":"Gelain M. , Pini M. S. , Rossi F. , Venable K. B. 2007. Dealing with incomplete preferences in soft constraint problems. Lecture Notes in Computer Science 4741, Springer, Pages 286\u2013300 of CP.","DOI":"10.1007\/978-3-540-74970-7_22"},{"key":"S0269888910000202_ref51","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"Leung","year":"2004"},{"key":"S0269888910000202_ref57","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04131-4"},{"key":"S0269888910000202_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04550-3"},{"key":"S0269888910000202_ref64","doi-asserted-by":"publisher","DOI":"10.1007\/11564751_36"},{"key":"S0269888910000202_ref83","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-005-2814-0"}],"container-title":["The Knowledge Engineering Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0269888910000202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T14:43:57Z","timestamp":1767624237000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0269888910000202\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":88,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["S0269888910000202"],"URL":"https:\/\/doi.org\/10.1017\/s0269888910000202","relation":{},"ISSN":["0269-8889","1469-8005"],"issn-type":[{"value":"0269-8889","type":"print"},{"value":"1469-8005","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}