Abstract
This paper reconsiders the most basic scheduling problem, that of minimizing the makespan of a partially ordered set of activities, in the context of incomplete knowledge. While this problem is very easy in the deterministic case, its counterpart when durations are interval-valued is much trickier, as standard results and algorithms no longer apply. After positioning this paper in the scope of temporal networks under uncertainty, we provide a complete solution to the problem of finding the latest starting times and floats of activities, and of locating surely critical ones, as they are often isolated. The minimal float problem is NP-hard while the maximal float problem is polynomial. New complexity results and efficient algorithms are provided for the interval-valued makespan minimization problem.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dechter, R., Meiri, I., Pearl, J.: Temporal constraint networks. Artif. Intell. 49, 61–95 (1991)
Morris, P., Muscettola, N., Vidal, T.: Dynamic control of plans with temporal uncertainty. In: IJCAI, pp. 494–502 (2001)
Vidal, T., Fargier, H.: Handling contingency in temporal constraint networks: from consistency to controllabilities. JETAI 11, 23–45 (1999)
Morris, P.H., Muscettola, N.: Managing temporal uncertainty through waypoint controllability. In: IJCAI, pp. 1253–1258 (1999)
Khatib, L., Morris, P., Morris, R., Rossi, F.: Temporal constraint reasoning with preferences. In: IJCAI, pp. 322–327 (2001)
Kelley, J., Walker, M.: Critical path planning and scheduling. In: Proc. of the Eastern Joint Comp. Conf., pp. 160–172 (1959)
Chanas, S., Zieliński, P.: The computational complexity of the criticality problems in a network with interval activity times. Eur. J. Oper. Res. 136, 541–550 (2002)
Dubois, D., Fargier, H., Fortin, J.: Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks. J. Intell. Manuf. (2005) (to appear)
Buckley, J.: Fuzzy PERT. In: Applications of fuzzy set methodologies in industrial engineering, pp. 103–114. Elsevier, Amsterdam (1989)
Dubois, D., Fargier, H., Fortemps, P.: Fuzzy scheduling: modeling flexible constraints vs. coping with incomplete knowledge. Eur. J. Oper. Res. 147, 231–252 (2003)
Dubois, D., Fargier, H., Galvagnon, V.: On latest starting times and floats in activity networks with ill-known durations. Eur. J. Oper. Res. 147, 266–280 (2003)
Chanas, S., Kamburowski, J.: The use of fuzzy variables in pert. Fuzzy Set Syst. 5, 1–19 (1981)
Chanas, S., Dubois, D., Zieliński, P.: On the sure criticality of tasks in activity networks with imprecise durations. IEEE T. Syst. Man Cy. B 34, 393–407 (2002)
Zieliński, P.: On computing the latest starting times and floats of activities in a network with imprecise durations. Fuzzy Set Syst. 150, 53–76 (2005)
Kolisch, R., Sprecher, A.: Psplib - a project scheduling library. Eur. J. Oper. Res. 96, 205–216 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fortin, J., Zieliński, P., Dubois, D., Fargier, H. (2005). Interval Analysis in Scheduling. In: van Beek, P. (eds) Principles and Practice of Constraint Programming - CP 2005. CP 2005. Lecture Notes in Computer Science, vol 3709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564751_19
Download citation
DOI: https://doi.org/10.1007/11564751_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29238-8
Online ISBN: 978-3-540-32050-0
eBook Packages: Computer ScienceComputer Science (R0)