Weighted-Tardiness Scheduling on Parallel Machines with Proportional Weights

Esther M. Arkin and Robin O. Roundy
Additional contact information
Esther M. Arkin: Cornell University, Ithaca, New York
Robin O. Roundy: Cornell University, Ithaca, New York

Operations Research, 1991, vol. 39, issue 1, 64-81

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.

Keywords: production/scheduling:; weighted-tardiness; scheduling; with; proportional; weights (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.1.64 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:1:p:64-81

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().