Minimizing total tardiness on a single machine with controllable processing times

The concept of time-cost trade-off is commonly considered in PERT/CPM, but it is seldom considered in the scheduling area. Such concept implies that the processing times of jobs are controllable by increasing or decreasing the available resources, such as manpower and equipment. In this paper, we focus on the single machine total tardiness problem with controllable processing times. First, a mixed-integer programming (MIP) model is formulated to find the optimal solution. Then, we propose both a linear programming model and a net benefit of compression (NBC) algorithm to obtain a set of optimal amounts of compression for a given sequence. To solve medium- to large-size problem instances, we develop a heuristic based on the NBC algorithm. To verify the proposed heuristic, the MIP model is used as a comparison for small-size problem instances, whereas for medium- to large-size instances the variable neighborhood search, a useful local search method, is employed. Computational results show that the proposed heuristic has a good performance.