Minimizing a Makespan Under Uncertainty
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1519-1519.
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. After positioning this paper in the scope of temporal networks under uncertainty, we provide a complete solution to the problem of finding 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.
@inproceedings{ijcai2005p292,
title = {Minimizing a Makespan Under Uncertainty},
author = {Fortin, Jérôme and Zielinski, Pawel and Dubois, Didier and Fargier, Helene},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {1519--1519},
year = {2005},
url = {https://ijcai.org/proceedings/2005/292},
}
TY - CPAPER TI - Minimizing a Makespan Under Uncertainty AU - Fortin, Jérôme AU - Zielinski, Pawel AU - Dubois, Didier AU - Fargier, Helene T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 1519 EP - 1519 UR - https://ijcai.org/proceedings/2005/292 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
