Minimizing total tardiness on two uniform parallel machines considering a cost constraint

This paper considers a scheduling problem of processing jobs on two uniform parallel machines. The objective is to minimize total tardiness, subject to the constraint that the total cost cannot exceed a given threshold. The problem is NP-hard even if there is no constraint on machine cost. Two machines are defined, one being fast with a higher processing cost and the other being slow with a lower processing cost. A mixed integer programming (MIP) model is established for the problem. We propose two heuristics with an improvement procedure to obtain initial solutions. To improve the quality of initial solutions, an algorithm based on simulated annealing (SA) approach is developed. The performance of the proposed algorithm is tested through random data and evaluated against optimal solutions obtained by Cplex. The results indicate that the algorithm is efficient and performs well.