A plan including several groups of tasks is constructed for performing maintenance on a plurality of interrelated machines. A maintenance task in a first group is caused to execute within a window of time allocated for the maintenance. A determination is made that an estimated amount of time needed to execute a second group of tasks from the several groups is more than the remaining time in the window. In response to such a determination, the execution of the second group of tasks is omitted. The execution of a post-requisite task of the first group is completed. A maintenance task in the second group is executed during a second window of time allocated for the maintenance.