Scheduling with a weight-modifying activity to minimize the total weighted completion time

This paper considers a single-machine scheduling problem to minimize the total weighted completion time with a weight modifying activity, after which the job weights are discounted by a given factor. The problem is known to be ordinary NP-hard. We propose two mixed integer linear programs (MILPs) and a dynamic programming algorithm to optimally solve the problem. Optimality properties are established and then formulated as pruning constraints to improve the problem-solving efficiency of the MILPs. Special cases are discussed and shown to be solvable by polynomial time algorithms. Complexity status of the studied problem with several instance characteristics is shown. Computational experiments indicate that the optimality properties can reduce the computing efforts and that one of the proposed MILPs can solve instances of 200 jobs in a few seconds.