Task scheduling in distributed systems is a challenging NP-hard problem. This paper proposes a structural decomposition approach based on rank intervals derived from the precedence matrix. Tasks are grouped into atomic subsets using interval overlaps, enabling a reduction of the scheduling problem. A local ILP formulation is applied within each subset while preserving global precedence constraints. Experimental results show that the proposed approach reduces the problem complexity while maintaining solution quality.
Amamou et al. (Tue,) studied this question.