Weighted-Tardiness Scheduling on Parallel Machines with Proportional Weights

This paper addresses 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.

Abstract

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 * ]/[Σ i w i p 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.