Succinct Representation of Linear Extensions via MDDs and Its Application to Scheduling Under Precedence Constraints

摘要

We consider a single machine scheduling problem to minimize total flow time under precedence constraints, which is NP-hard. Matsumoto et al. proposed an exact algorithm that consists of two phases: first construct a Multi-valued Decision Diagram (MDD) to represent feasible permutations of jobs, and then find the shortest path in the MDD which corresponds to the optimal solution. Although their algorithm performs significantly better than standard IP solvers for problems with dense constraints, the performance rapidly diminishes when the number of constraints decreases, which is due to the exponential growth of MDDs. In this paper, we introduce an equivalence relation among feasible permutations and show that it suffices to construct an MDD that maintains only one representative for each equivalence class. Experimental results show that our algorithm outperforms Matsurnoto et al.'s algorithm for problems with sparse constraints, while keeping good performance for dense constraints. Moreover, we show that Matsurnoto et al.'s algorithm can be extended for solving a more general problem of minimizing weighted total flow time.