Weighted-Tardiness Scheduling on Parallel Machines with Proportional Weights

In this paper, we address the problem of scheduling a number of jobs on a bank of parallel machines to minimize the total weighted tardiness, under the assumption that the weight of each job is proportional to its processing time. The version of the problem that has general weights has been shown to be strongly NP-complete. We prove this version of the problem to be NP-complete, and give a pseudopolynomial time algorithm for solving it. We study a family of simple sequencing rules in which the jobs are sequenced in increasing order of γ_i = d_i − θp_i, where d_i is the due date of job i, p_i its processing time, w_i its weight, and 0 ≤ θ ≤ 1. This family of sequencing rules generalizes the earliest due date sequencing rule. We obtain bounds on the ratio [C_γ · C^*]/[Σ_iw_ip_i], where C_γ and C^* are the costs of the heuristic and optimal schedules, respectively. The denominator is the cost of having each job be late by its own processing time. It is intended to measure what is or is not a large deviation from optimality, in absolute rather than relative terms, for the problem at hand. We also report on the results of computational experiments.