In the MARTHA project, a large number of robots in a harbour are given the global task of transporting containers from one area to anothel: The global decision-making process of allocating robots to those predejined tasks can be viewed as a scheduling and resource allocation problem , which is addressed here in a centralised way. Imprecision of temporal constraints make it meaningless to search for a strict optimal schedule. Our approach in-terleaves task allocation and execution, scheduling in a sliding short-term horizon, as the execution process runs, and providing near-optimal solutions. For largeapplications as our, the complexity of temporal management is a crucial issue. We present here a graph decomposition technique, leading to nearly-constant time temporal propagation, without any loss of information.