Summary: A procedure relation can be represented non-uniquely by an activity on arc (AoA) directed acyclic graph (dag). This paper deals with the NP-hard problem of constructing an AoA dag having the minimum number of arcs among those that have the minimum number of nodes. We show how this problem can be reduced in polynomial time to the set-cover problem so that the known methods of solving the set-covering problem can be applied. Several special cases that lead to easy set-covering problems are discussed.