Minimizing total weighted completion time in semiresumable case of single-machine scheduling with an availability constraint

Single-machine scheduling with an availability constraint to minimize total weighted completion time under the assumption that the disrupted job is semiresumable is considered in this paper. It is easily shown that this problem is NP-hard, and a dynamic programming algorithm and a branch-and-bound algorithm are developed to solve it optimally. Experiment results show that these two algorithms are accurate and efficient, and that the branch-and-bound outperforms the dynamic programming absolutely.