In this paper, a method based on local optimality rules is extended to maintenance planning in a random environment, where its robustness is evaluated using Monte Carlo simulation. The heuristics based on the local optimality rules consider tasks with unequal release dates and sequence-dependent set-up times characterized by the task sequences to minimize their flow-time. The appropriate priority rules enable optimizing tasks locally and minimizing their total weighted flow-time (resp. unweighted flow-time). Comparing the method in deterministic environments to random environments shows that it is greatly robust. The low polynomial complexity of heuristics based on the priority rules allows their use on distributed systems of large dimensions.