Scheduling precedence-constrained jobs on two resources to minimize the total weighted completion time

We study a problem of scheduling precedence-constrained jobs on two pre-specified resources, in which a job may require either resource or both resources with the objective of minimizing the weighted completion time. We present two mathematical formulations of the problem: a dynamic programming (DP) model and a binary integer programming (BIP) model. Due to the strong NP-hardness of the problem, we restrict our analysis to series-parallel (s/p) graphs. We focus on reducing the state space in the DP model to obtain an optimal, or near optimal, solution. We compare, through a number of experiments with varying number of jobs, resource requirements, and topology of the precedence among the jobs, the performance of the DP and the BIP models relative to the quality of the final result and the time taken to reach a conclusion.