Minimizing total weighted completion times subject to precedence constraints by dynamic programming

摘要

In this paper we present a polynomial time dynamic programming algorithm for solving a scheduling problem with a (total) weighted completion time objective function where the weights are activity- and time-dependent. We highlight application areas for this type of problem to underscore the relevance of it. A computational study proves that large instances with up to 120 activities can be solved.