Weighted-tardiness scheduling on parallel machines with proportional weights

In this paper, the authors 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. The authors prove this version of the problem to be NP-complete, and give a pseudopolynomial time algorithm for solving. it. They study a family of simple sequencing rules in which the jobs are sequenced in increasing order of , where is the due date of job i, its processing time, its weight, and . This family of sequencing rules generalizes the earliest due date sequencing rule. The authors obtain bounds on the ratio , where