Just-in-time scheduling with controllable processing times on parallel machines

We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider four different models for treating the two criteria. We prove that three of these problems are NP-hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three NP-hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial time optimization algorithm, which is converted to a fully polynomial time approximation scheme.