Filtering algorithms for the unary resource constraint

• Autorzy: Vilim P.
• Języki publikacji: EN

Abstrakty

EN

Scheduling is one of the most successful application areas of constraint programming mainly due to special global constraints designed to model resource restrictions. Among scheduling constraints, the most useful and most studied constraint is probably the unary resource constraint. This paper presents state-of-the-art filtering algorithms for this important constraint. These algorithms are very fast (almost all of them has time complexity O(n log n) and furthermore they are able to take into account so called optional activities, that is, activities which may or may not appear in the schedule depending for example on a resolution of an alternative processing rule(s). In particular, this paper presents the following algorithms: overload checking, edge finding, not-first/not-last, detectable precedences and precedence energy.

Słowa kluczowe

EN

constraint programming; scheduling; optional activities; unary resource; filtering algorithms

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2008
• Tom: Vol. 18, no. 2
• Strony: 159--202
• Opis fizyczny: Bibliogr. 31 poz., rys.

Twórcy

autor

Vilim P.

• ILOG S.A., Gentilly Cedex, France,

Bibliografia

• [1] ILOG CP Optimizer. URL http : //www. og.fr/products/cpoptimizer/.
• [2] K. R. APT: The essence of constraint propagation. Theoretical Computer Science, 221(1-2), (1999), 179-210, URL http: //citeseer ist .psu.edu/apt98essence html.
• [3] P. BAPTISTE: A theoretical and experimental study of resource constraint propagation. In PhD thesis. University of Compiegne, 1998.
• [4] P. BAPTISTE, C. LE PAPE and W. NUIJTEN: Satisfiability tests and time-bound adjustments for cumulative scheduling problems. In Technical Report 98/97. Universit de Technologie de Compigne, 1998.
• [5] P. BAPTISTE and C. LE PAPE: Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling. Proc. 15th Workshop of the U.K. Planning Special Interest Group, (1996).
• [6] ROMAN BARTÁK: Dynamic global constraints in backtracking based environments. Annals of Operations Research, 118 (2003), 101-119.
• [7] J. C. BECK and M. S. Fox: Scheduling alternative activities. Proc. 16th National Conf. Artificial Intelligence and 11th Conf. Innovative Applications of Artificial Intelligence, AAAI Press / The MIT Press, (1999), 680-687.
• [8] P. BRUCKE: Complex scheduling problems. 1999. URL http://citeseer.ist.psu.edu/brucker99complex.htmL
• [9] P. BRUCKER and S. KNUST: An 0(n2 )-algorithm for the input-or-output test. Osnabrucker Schrifien zur Mathematik, Reihe preprints, 259 (2005), URL ftp://ftp.mathematik.uni-osnabrueck.de/pub/osm/preprints/osmp259.pdf.
• [10] J. CARLIER and E. PINSON: Adjustments of head and tails for the job-shop problem. European J. Operational Research, 78 (1994), 146-161.
• [11] Y. CASEAU and F. LABURTHE: Improved CLP Scheduling with Task Intervals. In P. van Hentenryck, (Ed), Proc. 11th Int. Conf. Logic Programming, The MIT press, (1994).
• [12] Y. CASEAU and F. LABURTFIE: Disjunctive scheduling with task intervals. Technical report, LIENS Technical Report 95-25. Ecole Normale Suprieure Paris, Franc, 1995.
• [13] R. DECHTER: Constraint Processing (The Morgan Kaufmann Series in Artificial Intelligence). Morgan Kaufmann, 2003.
• [14] F. FOCACCI, P. LABORIE and W. NUIJTEN: Solving scheduling problems with setup times and alternative resources. In C.A. Knoblock S. Chien, S. Kambhampati, (Ed), Proc. 5th Int. Conf Artificial Intelligence Planning and Scheduling, AAAI Press, (2000), 92-111.
• [15] M. R. GAREY and D. S. JOHNSON: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco, 1979.
• [16] S. KUHNERT: Efficient edge-finding on unary resources with optional activities. Proc. 17th Conf. Applications of Declarative Programming and Knowledge Management, and 21st Workshop on (Constraint) Logic Programming, Technical Report 434, Universitat Wiirzburg, (2007), 35-46. URL http://wwwl.informatik.uni-wuerzburg.de/databases/INAP/2007/TR/report.pdf.
• [17] P. LABORIE: Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artcial Intelligence, 143(2), (2003), 151-188. ISSN 0004-3702. URL http://dx.doi.org/10.1016/S0004-3702(02)00362-4.
• [18] P. MARTIN and D.B. SHMOYS: A new approach to computing optimal schedules for the job-shop scheduling problem. In W.H. Cunningham, S.T. McCormick and M. Queyranne, (Ed), Proc. 5th Int. Conf. Integer Programming and Combinatorial Optimization, (1996), 389-403.
• [19] L. MERCIER and P. VAN HENTENRYCK: Edge finding for cumulative scheduling. Informs J. Computing, (2005). URL ht tp : / /www c s . brown edu/ pvh/ e f 2 . pdf . To appear.
• [20] J.-N. MONETTE, Y. DEVILLE and P. E. DUPONT: A position-based propagator for the open-shop problem. In P. Van Hentenryck and L.A. Wolsey, (Ed), Integration ofAI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 4th Int. Conf, (2007), volume 4510 of Lecture Notes in Computer Science, Springer, 2007, 186-199.
• [21] C. LE PAPE: Implementation of resource constraints in ILOG SCHEDULE: a library for the development of constraint-based scheduling systems. Intelligent Systems Engineering, 3(2), (1994), 55-66. URL www.ilog.com/products/optimization/tech/research/ise94.pdf.
• [22] C. LE PAPE, P. BAPTISTE and W. NUIJTEN: Constraint-based scheduling: Applying constraint programming to scheduling problems. Kluwer Academic Publishers, 2001.
• [23] A. SCHUTT, A. WOLF and G. SCHRADER: Not-first and not-last detection for cumulative scheduling in 0(n3 log n). Proc. 16th Int. Conf. Applications of Declarative Programming and Knowledge Management, (2005), 66-80.
• [24] P. TORRES and P. LOPEZ: On not-first/not-last conditions in disjunctive scheduling. European J. Operational Research, 127(2), (1999), 332-343.
• [25] P. VILIM: Batch processing with sequence dependent setup times: New results. Proc. 4th Workshop of Constraint Programming for Decision and Control, (2002). URL http: //vili.m.eu/petr/cpdc2002 .pdf.
• [26] P. VILIM: O(n log n) filtering algorithms for unary resource constraint. In J.-C. Rêgin and M. Rueher, (Ed), Proc. CP-AI-OR 2004, volume 3011 of Lecture Notes in Computer Science, Springer-Verlag, (2004), 335-347. URL http://vilim.eu/petr/nlogn.pdf.
• [27] P. VILIM, R. BARTAK and O. CEPEK: Unary resource constraint with optional activities. Principles and Pracitce of Constraint Programming, 10th Mt. Conf, Toronto, Canada, volume 3258 of Lecture Notes in Computer Science, Springer, (2004), 62-76. URL http : //vilim.eu/petr/cp2 004 pdf.
• [28] P. VILIM, R. BARTAK and O. CEPEK: Extension of O(nlogn) filtering algorithms for the unary resource constraint to optional activities. Contraints, 10(4), (2005), 403-425. ISSN 1383-7133. URL http://vilim.eu/petr/constraints2005.pdf.
• [29] A. WOLF and H. SCHLENKER: Realizing the alternative resources constraint problem with single resource constraints. Proc. 15th Mt. Conf. Applications of Declarative Programming and Knowledge Management and the 18th Workshop on Logic Programming, Technical Report 327, Bayerische Julius-Maximilians-Universitat Wiirzburg, 2004, 280-294.
• [30] A. WOLF: Pruning while sweeping over task intervals. In F. Rossi, (Ed), Principles and Practice of Constraint Programming, volume 2833 of Lecture Notes in Computer Science, Springer, 2003, 739-753.
• [31] A. WOLF and G. SCHRADER: O(nlogn) overload checking for the cumulative constraint and its application. Proc. 16th Int. Conf on Applications of Declarative Programming and Knowledge Management, Springer, (2005), 88-101.