Horizontally Elastic Edge-Finder Algorithm for Cumulative Resource Constraint Revisited

Operations Research Forum - Tập 3 - Trang 1-32 - 2022
Sévérine Fetgo Betmbe1, Clémentin Tayou Djamegni1,2
1Department of Mathematics and Computer Science, Faculty of Sciences, University of Dschang, Dschang, Cameroon
2IUT-FV de Bandjoun, University of Dschang, Dschang, Cameroon

Tóm tắt

The success of constraint programming on scheduling problems comes from the low complexity and power of propagators. The data structure Profile recently introduced by Gingras and Quimper in Generalizing the edge-finder rule for the cumulative constraint. In: IJCAI, IJCAI/AAAI Press, pp 3103–3109, 2016, when applied to the edge-finder rule for the cumulative resource constraint (which we call horizontally elastic edge-finder) has improved the filtering power of this rule. In this paper, the algorithm proposed by Gingras and Quimper in Generalizing the edge-finder rule for the cumulative constraint. In: IJCAI, IJCAI/AAAI Press, pp 3103–3109, 2016 is revisited. It is proved that the data structure Profile can be further used for more adjustments. A new formulation of the horizontally elastic edge-finder rule is put forward. Similar to Gingras and Quimper in Generalizing the edge-finder rule for the cumulative constraint. In: IJCAI, IJCAI/AAAI Press, pp 3103–3109, 2016, an $$\mathcal {O}(kn^2)$$ algorithm (where n is the number of tasks sharing the resource and $$k\le n$$ , the number of distinct capacities required by tasks) based on new attributes of the Profile data structure is proposed for the new rule. Experimental results on instances of Resource-Constrained Project Scheduling Problems (RCPSPs) from the benchmark suites highlight that using this new algorithm reduces the number of backtracks for the majority of instances with a slight increase in running time.

Tài liệu tham khảo

Abel Soares Siqueira Raniere Gaia Costa da Silva LRS (2016) A python package for performance profile of mathematical optimization software. J Open Res Softw 4(1):p.e12. https://doi.org/10.5334/jors.81

Aggoun A, Beldiceanu N (1993) Extending CHIP in order to Solve Complex Scheduling and Placement Problems. Mathl Comput Model 17(7):57–73.https://hal.archives-ouvertes.fr/hal-00442821

Baptiste P, Pape C, Nuijten W (2012) Constraint-based scheduling: applying constraint programming to scheduling problems. International series in operations research & management science, Springer US, https://books.google.cm/books?id=qUzhBwAAQBAJ

Carlier J, Néron E (2003) On linear lower bounds for the resource constrained project scheduling problem. Eur J Oper Res 149(2):314–324

Carlier J, Pinson E, Sahli A, Jouglet A (2020) An: O(n2) algorithm for time-bound adjustments for the cumulative scheduling problem. Eur J Oper Res 286(2):468–476

Dechter R (2003) Constraint processing. Elsevier Morgan Kaufmann

Derrien A, Petit T (2014) A new characterization of relevant intervals for energetic reasoning. CP, Springer, Lect Notes Comput Sci 8656:289–297

Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201–213

FetgoBetmbe S, Djamegni CT (2020) Horizontally elastic edge-finder algorithm for cumulative resource constraint revisited. In: CARI 2020, THIES, Senegal.https://hal.archives-ouvertes.fr/hal-02931383

Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H

Gay S, Hartert R, Lecoutre C, Schaus P (2015) Conflict ordering search for scheduling problems. In: CP, Springer, Lect Notes Comput Sci 9255:140–148

Gay S, Hartert R, Schaus P (2015) Simple and scalable time-table filtering for the cumulative constraint. In: CP, Springer, Lect Notes Comput Sci 9255:149–157

Gingras V, Quimper C (2016) Generalizing the edge-finder rule for the cumulative constraint. In: IJCAI, IJCAI/AAAI Press, pp 3103–3109

Kameugne R, Fotso LP (2013) A cumulative not-first/not-last filtering algorithm in o(n2log(n)). Indian J Pure Appl Math 44:95–115

Kameugne R, Fotso LP, Scott JD (2013) A quadratic extended edge-finding filtering algorithm for cumulative resource constraints. Int J Plan Sched 1(4):264–284

Kameugne R, Fotso LP, Scott JD, Ngo-Kateu Y (2014) A quadratic edge-finding filtering algorithm for cumulative resource constraints. Constraints An Int J 19(3):243–269

Koné O, Artigues C, Lopez P, Mongeau M (2011) Event-based MILP models for resource-constrained project scheduling problems. Comput Oper Res 38(1):3–13

Letort A, Beldiceanu N, Carlsson M (2012) A scalable sweep algorithm for the cumulative constraint. CP, Springer, Lect Notes Comput Sci 7514:439–454

Mercier L, Hentenryck PV (2008) Edge finding for cumulative scheduling. INFORMS J Comput 20(1):143–153

Ouellet P, Quimper C (2013) Time-table extended-edge-finding for the cumulative constraint. CP, Springer, Lect Notes Comput Sci 8124:562–577

Ouellet Y, Quimper C (2018) A o(2n) checker and o(n2n) filtering algorithm for the energetic reasoning. CPAIOR, Springer, Lect Notes Comput Sci 10848:477–494

Prud’homme C, Fages JG, Lorca X (2016) Choco Solver Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S., http://www.choco-solver.org

Rossi F, van Beek P, Walsh T (eds) (2006) Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol2. Elsevier

Schutt A, Feydy T, Stuckey PJ (2013) Explaining time-table-edge-finding propagation for the cumulative resource constraint. CPAIOR, Springer, Lect Notes Comput Sci 7874:234–250

Tesch A (2018) Improving energetic propagations for cumulative scheduling. CP, Springer, Lect Notes Comput Sci 11008:629–645

Vilím P (2007) Global constraints in scheduling. PhD thesis, Charles University in Prague, Faculty of Mathematics and Physics, Department of Theoretical Computer Science and Mathematical Logic, KTIML MFF, Universita Karlova, Malostranské náměstí 2/25, 118 00 Praha 1, Czech Republic, http://vilim.eu/petr/disertace.pdf

Vilím P (2009) Edge finding filtering algorithm for discrete cumulative resources in BOFO(knn). In: CP’09: Proceedings of the 15th international conference on Principles and practice of constraint programming, Springer-Verlag, Berlin, Heidelberg, pp 802–816. http://vilim.eu/petr/cp2009.pdf

Vilím P (2011) Timetable edge finding filtering algorithm for discrete cumulative resources. CPAIOR, Springer, Lect Notes Comput Sci 6697:230–245

Yang M, Schutt A, Stuckey PJ (2019) Time table edge finding with energy variables. CPAIOR, Springer, Lect Notes Comput Sci 11494:633–642

Thông tin
Thông tin xuất bản

Operations Research Forum

Tập 3

1-32

Thông tin tác giả