---
title: "Minimizing a Makespan Under Uncertainty"
authors:
  - "Jérôme Fortin"
  - "Pawel Zielinski"
  - "Didier Dubois"
  - "Hélène Fargier"
doi: ""
url: "https://ijcai.org/proceedings/2005/292"
pdf: "https://ijcai.org/proceedings/2005/0292.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "1519-1519"
track: ""
keywords:
---

# Minimizing a Makespan Under Uncertainty

Jérôme Fortin, Pawel Zielinski, Didier Dubois, Hélène Fargier

*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.