Парадигма программирования в ограничениях при решении задач составления расписаний: аналитический обзор
Ключевые слова:
составление расписаний, унарные ресурсы, кумулятивные ресурсы, методы составления расписаний, задача удовлетворения ограничений, распространение ограничений, программирование в ограничениях
Аннотация
В статье рассмотрен подход к решению задач составления расписаний на основе парадигмы программирования в ограничениях. Любой метод удовлетворения ограничений включает две обязательные части: a) компоненту, отвечающую за поиск; b) компоненту, осуществляющую вывод на ограничениях (распространение ограничений). При реализации первой компоненты обычно применяется определенный вариант поиска в глубину с возвратами с использованием эвристик для выбора преемника текущего узла в дереве поиска. Вторая компонента реализуется с применением механизма глобальных ограничений. Глобальные ограничения можно рассматривать как составные ограничения, представляющие собой набор более простых однотипных ограничений. Алгоритмы распространения глобальных ограничений, как правило, подкреплены соответствующими развитыми теориями, позволяющими организовывать высокопроизводительные вычисления. Технология программирования в ограничениях позволяет реализовывать общие методы решения сложных комбинаторных задач, а также дает возможность интегрировать с помощью механизма глобальных ограничений существующие методы теории исследования операций, направленные на решение узких классов задач. При решении задач составления расписаний основные ограничения могут быть типизированы следующим образом: ограничения на порядок выполнения операций, ограничения на унарные (дистрибутивные) ресурсы, ограничения на кумулятивные ресурсы. В настоящей работе произведен обзор основных классов задач составления расписаний и сделан акцент на типах ограничений, которые в них используются. Для решения упомянутых задач могут быть использованы методы удовлетворения ограничений общего назначения, однако более перспективным считается применение специализированных эвристик и глобальных ограничений. В работе произведен обзор наиболее популярных эвристик, используемых при решении задач составления расписаний, а также глобальных ограничений таких, как: глобальное ограничение на дизъюнктивные ресурсы, глобальное ограничение на кумулятивные ресурсы, глобальное ограничение на мощность множеств. В статье обсуждаются особенности реализации различных классов задач составления расписаний с использованием современных сред и библиотек программирования в ограничениях.
Скачивания
Данные скачивания пока не доступны.
Литература
1. Ghallab Malik, Nau Dana and Traverso Paolo. (2016) Automated Planning: Theory and Practice. Cambridge University Press.
2. Baptiste Ph., Le Pape C. and Nuijten W. (2001) Constraint-based scheduling: applying constraint programming to scheduling problems. Kluwer Academic Publishers.
3. Apt K. R. (2003) Principles of Constraint Programming. Cambridge University Press.
4. Dechter R. (2003) Constraint Processing. Morgan Kaufmann.
5. Tsang E. (1993) Foundation of Constraint Satisfaction. Academic Press.
6. Rossi F., Van Beek P. and Walsh T. (2006) Handbook of constraint programming. Elsevier.
7. Bartak R. (2005) Constraint Satisfaction for Planning and Scheduling. In Vlahavas, Vrakas (eds.): Intelligent Techniques for Planning. P. 320–353.
8. Roman Bartak, Miguel A. Salido and Francesca Rossi (2011) Constraint Satisfaction Techniques in Planning and Scheduling. Constraints. 16(3). P. 223–227. Available from: DOI
9. Lazarev A. A., Lemtyuzhnikova D. V. and Werner F. (2021) A metric approach for scheduling problems with minimizing the maximum penalty. Applied Mathematical Modelling. 89(2). P. 1163–1176. Available from: DOI
10. Antonova A. S. and Aksyonov K. A. (2020) Analysis of the methods for accounting the renewable and non-renewable resources in scheduling. Journal of Physics: Conference Series. 1694. 1. 012005. Available from: DOI
11. Baptiste P., Laborie P., Le Pape C. and Nuijten W. (2006) Constraint-Based Scheduling and Planning. Handbook of Constraint Programming. Amsterdam: Elsevier. P. 761–799. Available from: DOI
12. Ruttkay Z. (1998) Constraint Satisfaction – a Survey. CWI Quarterly. 11. P. 123–162.
13. Lhomme O. (1993) Consistency techniques for numeric CSPs. Proceedings of 13th International Joint Conference on Artificial Intelligence.
14. Bitner J. R. and Reingold E. M. (1975) Backtracking Programming Techniques. Communications of the ACM. 18. P. 651–655.
15. Gaschnig J. (1979) Performance measurement and analysis of certain search algorithms. Carnegie-Mellon University: Technical Report CMUCS. P. 79–124.
16. Prosser P. (1993) Hybrid Algorithm for the Constraint Satisfaction Problem. Computational Intelligence. 9. P. 268–299.
17. Gaschnig J. (1977) A general backtrack algorithm that eliminates most redundant tests. Procceedings of IJCAI.
18. Frost D. and Dechter R. (1994) Deadend driven learning. Procceedings of the National Conference on Artificial Intelligence. P. 294–300.
19. Haralick R. and Elliot G. (1980) Increasing Tree Efficiency for Constraint Satisfaction Problems. Artificial Intelligence. 14. P. 263–314.
20. Michalewicz Z. and Fogel D. B. (2000) How to Solve It: Modern Heuristics. SpringerVerlag.
21. Roman Barták (2008) Artificial Intelligence for Advanced Problem Solving.
22. Baptiste P., Le Pape C. and Nuijten W. (1995) Constraint-Based Optimization and Approximation for Job-Shop Scheduling. Proceedings of the AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, IJCAI-95.
23. Smith S. F. and Cheng Ch.-Ch. (1993) Slack-Based Heuristics For Constraint Satisfaction Scheduling. Proceedings of the National Conference on Artificial Intelligence (AAAI). P. 139–144.
24. Mackworth A. K. (1977) Consistency in networks of relations. Artificial Intelligence. 8(1). P. 99–118.
25. Baptiste P., Le Pape C. and Nuijten W. (2001) Constraint-Based Scheduling. Springer.
26. Baptiste P. and Le Pape C. (1996) Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. Proceedings of PLANSIG.
27. Vil ́ım P., Bartak R. and Cepek O. (2005) Extension of O(n log n) filtering algorithms for the unary resource constraint to optional activities. Constraints. 10(4). P. 403–425. Available from: DOI
28. Torres P. and Lopez P. (2000) On NotFirst/Not-Last conditions in disjunctive scheduling. European Journal of Operational Research. 127. P. 332–343.
29. Lazarev A. A. and Gafarov E. R. (2011) Teoriya raspisanij zadachi i algoritmy. [Problem scheduling theory and algorithms]. Moscow, Moscow State University named after M.V. Lomonosov. (In Russian).
30. Russel S. and Norvig P. (2010) Artificial Intelligence: A Modern Approach. 3rd edition. Prentice Hall.
31. The Job Shop Problem. Available from: URL
32. IBM CP LEX. Available from: URL
33. MiniZinc. Available from: URL [Accessed 01.06.2022].
34. Arkhipov D. I. and Lazarev A. A. and Tarasov G. V. (2017) Estimating Maximum Resource Load for Resource-Constrained Project Scheduling Problem. Proceedings of the 8th International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLI-
CATINS” (OPTIMA-2017). Moscow: CC RAS. 1987. P. 356–363.
35. Gimadi E. Kh., Goncharov E. N. and Shtepa A. A. (2021) A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances. Proceedings of the Institute of Mathematics and Mechanics UrO RAN. 27. 1. P. 22–36. Available from: DOI
36. Nattaf M., Artigues C. and Lopez P. (2017) Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions. Constraints. 22. P. 530–547. Available from: DOI
37. Kreter S., Schutt A. and Stuckey P. J. (2017) Using constraint programming for solving RCPSP/max-cal. Constraints. 22. P. 432–462. Available from: doi: DOI
38. Pleskunov M. A. (2014) Zadachi setevogo planirovaniya: uchebnoe posobie. [Tasks of network planning: a tutorial]. Yekaterinburg: Ural Publishing House university. (In Russian).
39. Henry Amankwah. (2011) Mathematical Optimization Models and Methods for Open-Pit Mining. LiU-Tryck, Linköping, Sweden.
40. Lerchs H. and Grossmann I. F. (1965) Optimum Design of Open-Pit Mines, Transactions. Canadian Institute of Mining and Metallurgy. LXVIII. P. 17–24.
41. Picard J.-C. and Smith B. T. (2004) Parametric Maximum Flows and the Calculation of Optimal Intermediate Contours in Open Pit Mine Design. INFOR Journal. 42. 2. P. 143–153. Available from: DOI
42. Pikies T., Kubale M. and Turowski K. (2022) Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms. Artificial intelligence. 309. 103711. Available from: DOI
43. Margaux Nattaf, Stéphane Dauzère-Pérès, Claude Yugma, Cheng-Hung Wu. (2019) Parallel Machine Scheduling with Time Constraints on Machine Qualifications. Computers and Operations Research, Elsevier. 107. P. 61–76. Available from: DOI
44. Hua Gong, Yuyan Zhang and Puyu Yuan. (2020) Scheduling on a Single Machine and Parallel Machines with Batch Deliveries and Potential Disruption. Complexity in Economics and Business, Article ID 6840471, Available from: DOI
45. Ek A., Garcia de la Banda M., Schutt A., Stuckey P. J. and Tack G. (2020) Modelling and Solving Online Optimisation Problems. Proceedings of the AAAI Conference on Artificial Intelligence. 34(02). P. 1477–1485. Available from: DOI
46. 1S: Avtomatizirovannoe sostavlenie raspisaniya. Vozmozhnosti produkta. [1C: Automated scheduling. Product features]. URL
47. R ́egin J. (1996) Generalized arc consistency for global cardinality constraint. Proceedings of the Thirteenth National Conference on Artificial Intelligence. Portland. P. 209–215.
48. Likhtarnikov L. M. (1996) Zadachi mudreczov.[Tasks of the Wise]. Moscow, Enlightenment, JSC. Study. lit. (In Russian).
49. Employee Scheduling. URL
50. Mushfiqur Rahman M., Binte Noor S. and Hasan Siddiqui F. (2020) Automated Large-scale Class Scheduling in MiniZinc. Proceedings of the 2nd International Conference on Sustainable Technologies for Industry 4.0 (STI). P. 1–6. Available from: DOI
51. Demirović E. and Stuckey P. J. (2018) Constraint Programming for High School Timetabling: A Scheduling-Based Model with Hot Starts. In: van Hoeve, WJ. (eds) Integration of Constraint Programming, Artificial Intelligence and Operations Research. CPAIOR 2018. Lecture Notes in Computer Science, Springer, Cham. 10848. Available from: DOI
52. Traveling Salesperson Problemhttps. Available from: URL
53. Joshi C. K., Cappart Q., Rousseau L. M. [et al.] (2022) Learning the travelling salesperson problem requires rethinking generalization. Constraints. 27. P. 70–98. Available from: DOI
54. Van Cauwelaert S. and Schaus P. (2017) Efficient filtering for the Resource-Cost AllDifferent constraint. Constraints. 22. P. 493–511. Available from: DOI
55. Koehler J., Bürgler J., Fontana U. [et al.] (2021) Cable tree wiring-benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints. Constraints. 26. P. 56–106. Available from: DOI
56. Fages J. G., Lorca X. and Rousseau L. M. (2016) The salesman and the tree: the importance of search in CP. Constraints. 21. P. 145–162. Available from: DOI
57. Nicolas Isoart. (2021) The traveling salesman problem in constraint programming. Data Structures and Algorithms [cs.DS]. Université Côte d’Azur.
58. Resource Constraints. URL
2. Baptiste Ph., Le Pape C. and Nuijten W. (2001) Constraint-based scheduling: applying constraint programming to scheduling problems. Kluwer Academic Publishers.
3. Apt K. R. (2003) Principles of Constraint Programming. Cambridge University Press.
4. Dechter R. (2003) Constraint Processing. Morgan Kaufmann.
5. Tsang E. (1993) Foundation of Constraint Satisfaction. Academic Press.
6. Rossi F., Van Beek P. and Walsh T. (2006) Handbook of constraint programming. Elsevier.
7. Bartak R. (2005) Constraint Satisfaction for Planning and Scheduling. In Vlahavas, Vrakas (eds.): Intelligent Techniques for Planning. P. 320–353.
8. Roman Bartak, Miguel A. Salido and Francesca Rossi (2011) Constraint Satisfaction Techniques in Planning and Scheduling. Constraints. 16(3). P. 223–227. Available from: DOI
9. Lazarev A. A., Lemtyuzhnikova D. V. and Werner F. (2021) A metric approach for scheduling problems with minimizing the maximum penalty. Applied Mathematical Modelling. 89(2). P. 1163–1176. Available from: DOI
10. Antonova A. S. and Aksyonov K. A. (2020) Analysis of the methods for accounting the renewable and non-renewable resources in scheduling. Journal of Physics: Conference Series. 1694. 1. 012005. Available from: DOI
11. Baptiste P., Laborie P., Le Pape C. and Nuijten W. (2006) Constraint-Based Scheduling and Planning. Handbook of Constraint Programming. Amsterdam: Elsevier. P. 761–799. Available from: DOI
12. Ruttkay Z. (1998) Constraint Satisfaction – a Survey. CWI Quarterly. 11. P. 123–162.
13. Lhomme O. (1993) Consistency techniques for numeric CSPs. Proceedings of 13th International Joint Conference on Artificial Intelligence.
14. Bitner J. R. and Reingold E. M. (1975) Backtracking Programming Techniques. Communications of the ACM. 18. P. 651–655.
15. Gaschnig J. (1979) Performance measurement and analysis of certain search algorithms. Carnegie-Mellon University: Technical Report CMUCS. P. 79–124.
16. Prosser P. (1993) Hybrid Algorithm for the Constraint Satisfaction Problem. Computational Intelligence. 9. P. 268–299.
17. Gaschnig J. (1977) A general backtrack algorithm that eliminates most redundant tests. Procceedings of IJCAI.
18. Frost D. and Dechter R. (1994) Deadend driven learning. Procceedings of the National Conference on Artificial Intelligence. P. 294–300.
19. Haralick R. and Elliot G. (1980) Increasing Tree Efficiency for Constraint Satisfaction Problems. Artificial Intelligence. 14. P. 263–314.
20. Michalewicz Z. and Fogel D. B. (2000) How to Solve It: Modern Heuristics. SpringerVerlag.
21. Roman Barták (2008) Artificial Intelligence for Advanced Problem Solving.
22. Baptiste P., Le Pape C. and Nuijten W. (1995) Constraint-Based Optimization and Approximation for Job-Shop Scheduling. Proceedings of the AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, IJCAI-95.
23. Smith S. F. and Cheng Ch.-Ch. (1993) Slack-Based Heuristics For Constraint Satisfaction Scheduling. Proceedings of the National Conference on Artificial Intelligence (AAAI). P. 139–144.
24. Mackworth A. K. (1977) Consistency in networks of relations. Artificial Intelligence. 8(1). P. 99–118.
25. Baptiste P., Le Pape C. and Nuijten W. (2001) Constraint-Based Scheduling. Springer.
26. Baptiste P. and Le Pape C. (1996) Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. Proceedings of PLANSIG.
27. Vil ́ım P., Bartak R. and Cepek O. (2005) Extension of O(n log n) filtering algorithms for the unary resource constraint to optional activities. Constraints. 10(4). P. 403–425. Available from: DOI
28. Torres P. and Lopez P. (2000) On NotFirst/Not-Last conditions in disjunctive scheduling. European Journal of Operational Research. 127. P. 332–343.
29. Lazarev A. A. and Gafarov E. R. (2011) Teoriya raspisanij zadachi i algoritmy. [Problem scheduling theory and algorithms]. Moscow, Moscow State University named after M.V. Lomonosov. (In Russian).
30. Russel S. and Norvig P. (2010) Artificial Intelligence: A Modern Approach. 3rd edition. Prentice Hall.
31. The Job Shop Problem. Available from: URL
32. IBM CP LEX. Available from: URL
33. MiniZinc. Available from: URL [Accessed 01.06.2022].
34. Arkhipov D. I. and Lazarev A. A. and Tarasov G. V. (2017) Estimating Maximum Resource Load for Resource-Constrained Project Scheduling Problem. Proceedings of the 8th International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLI-
CATINS” (OPTIMA-2017). Moscow: CC RAS. 1987. P. 356–363.
35. Gimadi E. Kh., Goncharov E. N. and Shtepa A. A. (2021) A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances. Proceedings of the Institute of Mathematics and Mechanics UrO RAN. 27. 1. P. 22–36. Available from: DOI
36. Nattaf M., Artigues C. and Lopez P. (2017) Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions. Constraints. 22. P. 530–547. Available from: DOI
37. Kreter S., Schutt A. and Stuckey P. J. (2017) Using constraint programming for solving RCPSP/max-cal. Constraints. 22. P. 432–462. Available from: doi: DOI
38. Pleskunov M. A. (2014) Zadachi setevogo planirovaniya: uchebnoe posobie. [Tasks of network planning: a tutorial]. Yekaterinburg: Ural Publishing House university. (In Russian).
39. Henry Amankwah. (2011) Mathematical Optimization Models and Methods for Open-Pit Mining. LiU-Tryck, Linköping, Sweden.
40. Lerchs H. and Grossmann I. F. (1965) Optimum Design of Open-Pit Mines, Transactions. Canadian Institute of Mining and Metallurgy. LXVIII. P. 17–24.
41. Picard J.-C. and Smith B. T. (2004) Parametric Maximum Flows and the Calculation of Optimal Intermediate Contours in Open Pit Mine Design. INFOR Journal. 42. 2. P. 143–153. Available from: DOI
42. Pikies T., Kubale M. and Turowski K. (2022) Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms. Artificial intelligence. 309. 103711. Available from: DOI
43. Margaux Nattaf, Stéphane Dauzère-Pérès, Claude Yugma, Cheng-Hung Wu. (2019) Parallel Machine Scheduling with Time Constraints on Machine Qualifications. Computers and Operations Research, Elsevier. 107. P. 61–76. Available from: DOI
44. Hua Gong, Yuyan Zhang and Puyu Yuan. (2020) Scheduling on a Single Machine and Parallel Machines with Batch Deliveries and Potential Disruption. Complexity in Economics and Business, Article ID 6840471, Available from: DOI
45. Ek A., Garcia de la Banda M., Schutt A., Stuckey P. J. and Tack G. (2020) Modelling and Solving Online Optimisation Problems. Proceedings of the AAAI Conference on Artificial Intelligence. 34(02). P. 1477–1485. Available from: DOI
46. 1S: Avtomatizirovannoe sostavlenie raspisaniya. Vozmozhnosti produkta. [1C: Automated scheduling. Product features]. URL
47. R ́egin J. (1996) Generalized arc consistency for global cardinality constraint. Proceedings of the Thirteenth National Conference on Artificial Intelligence. Portland. P. 209–215.
48. Likhtarnikov L. M. (1996) Zadachi mudreczov.[Tasks of the Wise]. Moscow, Enlightenment, JSC. Study. lit. (In Russian).
49. Employee Scheduling. URL
50. Mushfiqur Rahman M., Binte Noor S. and Hasan Siddiqui F. (2020) Automated Large-scale Class Scheduling in MiniZinc. Proceedings of the 2nd International Conference on Sustainable Technologies for Industry 4.0 (STI). P. 1–6. Available from: DOI
51. Demirović E. and Stuckey P. J. (2018) Constraint Programming for High School Timetabling: A Scheduling-Based Model with Hot Starts. In: van Hoeve, WJ. (eds) Integration of Constraint Programming, Artificial Intelligence and Operations Research. CPAIOR 2018. Lecture Notes in Computer Science, Springer, Cham. 10848. Available from: DOI
52. Traveling Salesperson Problemhttps. Available from: URL
53. Joshi C. K., Cappart Q., Rousseau L. M. [et al.] (2022) Learning the travelling salesperson problem requires rethinking generalization. Constraints. 27. P. 70–98. Available from: DOI
54. Van Cauwelaert S. and Schaus P. (2017) Efficient filtering for the Resource-Cost AllDifferent constraint. Constraints. 22. P. 493–511. Available from: DOI
55. Koehler J., Bürgler J., Fontana U. [et al.] (2021) Cable tree wiring-benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints. Constraints. 26. P. 56–106. Available from: DOI
56. Fages J. G., Lorca X. and Rousseau L. M. (2016) The salesman and the tree: the importance of search in CP. Constraints. 21. P. 145–162. Available from: DOI
57. Nicolas Isoart. (2021) The traveling salesman problem in constraint programming. Data Structures and Algorithms [cs.DS]. Université Côte d’Azur.
58. Resource Constraints. URL
Опубликован
2022-12-26
Как цитировать
Зуенко, А. А., Фридман, О. В., & Ольга Николаевна, З. (2022). Парадигма программирования в ограничениях при решении задач составления расписаний: аналитический обзор. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (4), 156-179. извлечено от https://journals.vsu.ru/sait/article/view/10814
Раздел
Современные технологии разработки программного обеспечения
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
