×

zbMATH — the first resource for mathematics

Computing a lower approximation of the compulsory part of a task with varying duration and varying resource consumption. (English) Zbl 1053.90044
Summary: This paper considers a generalisation of the classical RCPSP problem: the resource consumption of each task is continuously varying over time and the duration and the start of each task may vary within real intervals. A first contribution is a general model for describing the resource consumption of a task over time. This model is justified when considering continuously divisible resources. The second contribution is the computation of the compulsory part or core time of such a task. The compulsory part gives the task’s resource consumption common to all feasible schedules. Hence, it can be used in a global resolution process such as constraint programming or branch and bound approaches. The presented polynomial algorithms use only two particular schedules of that task.

MSC:
90B35 Deterministic scheduling theory in operations research
Software:
CHIP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggoun, A; Beldiceanu, N, Extending CHIP in order to solve complex scheduling and placement problems, Mathematical and computer modelling, 17, 7, 57-73, (1993)
[2] N. Beldiceanu, Q. Guo, S. Thiel, Non-overlapping constraint between convex polytopes, in: Principles and Practice of Constraint Programming-CP 2001, 7th International Conference, Cyprus, November 26-December 1, in: Lecture Notes in Computer Science, vol. 2239, Springer, 2001, pp. 377-391
[3] Biró, M, Object-oriented interaction in resource constrained scheduling, Information processing letters, 36, 2, 65-67, (1990) · Zbl 0705.90041
[4] Brucker, P; Drexl, A; Möhring, R; Neumann, K; Pesch, E, Resource-constrained project scheduling: notation, classification, models, and methods, European journal of operational research, 112, 3-41, (1999) · Zbl 0937.90030
[5] Y. Caseau, F. Laburthe, Cumulative scheduling with task intervals, in: Proceedings of the Joint International Conference and Symposium on Logic Programming, The MIT Press, 1996 · Zbl 0949.90058
[6] A. Chamard, F. Decès, A. Fischler, A Workshop Scheduler System written in CHIP, in: 2nd Conference on Practical Applications of Prolog, London, April 1994
[7] CHIP Reference Manual Version 5, 2001, COSYTEC SA, France
[8] Dorndorf, U; Phan Huy, T; Pesch, E, A survey of interval capacity consistency tests for time and resource constrained scheduling, (), 213-238
[9] X. Gandibleux, Système d’aide á la décision pour la conduite de processus perturbés; une approche hybride fondée sur l’intelligence artificielle, la programmation linéaire et l’aide multicritére à la décision. Application à la mobilisation de réserve tertiaire d’Electricité De France. Ph.D. thesis, Université de Valenciennes et du Hainaut-Cambrésis, January 1995. (in French)
[10] Heipcke, S; Colombani, Y; Cavalcante, C.C.B; de Souza, C.C, Scheduling under labour resource constraints, Constraints, 5, 4, 415-422, (2000) · Zbl 0972.68502
[11] Van Hentenryck, P, Constraint satisfaction in logic programming, (1989), The MIT Press
[12] Herroelen, W; Demeulemeester, E; De Reyck, B, A classification scheme for project scheduling problems, (), 1-26
[13] M. Hujter, On the dynamic storage allocation problem, Manuscript, Computer and Automation Institute, Hungarian. Acad. Sci., 1990
[14] Klein, R; Scholl, A, Computing lower bounds by destructive improvement: an application to resource-constrained project scheduling, European journal of operational research, 112, 322-346, (1999) · Zbl 0938.90030
[15] A. Lahrichi, Ordonnancements: la notion de “partie obligatoire” et son application aux problèmes cumulatifs, Ph.D. thesis, Université de Paris VI, May 1979 (in French)
[16] Lahrichi, A, Scheduling: the notions of hump, compulsory parts and their use in cumulative problems, Comptes rendus de academie des sciences, Paris, 294, February, 209-211, (1982)
[17] J.-L. Laurière; A language and a program for stating and solving combinatorial problems, Artificial intelligence, 10, 29-127, (1978)
[18] H. Simonis, T. Cornelissens, Modeling producer/consumer constraints, in: Principles and Practice of Constraint programming–CP 1995, First International Conference, Cassis, France, September 19-22, in: Lecture Notes in Computer Science, vol. 976, Springer, 1995, pp. 449-462
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.