The Weighted Total Tardiness Problem with Fixed Shipping Times and Overtime Utilization

Hirofumi Matsuo

Operations Research, 1988, vol. 36, issue 2, 293-307

Abstract: This paper addresses the problem of simultaneously determining overtime utilization and job sequencing over a finite planning horizon in a single machine job shop environment. Shipping times are assumed to occur at fixed and specified points in time, and their number is much smaller than the number of jobs. The goal is to find an overtime utilization level and job sequence that yields a “good” tradeoff between overtime cost and tardiness penalties. We begin by showing that the problem in its simplest form is NP-hard. We then present an approximate algorithm based on a capacitated transshipment formulation. This approximation provides a feasible solution along with its error bound. The algorithm is refined by incorporating the dominance relations of jobs. Extensive computational experience indicates that the algorithm is implementable in terms of both speed and accuracy.

Keywords: 482 transshipment problem for approximation; 584 single machine total tardiness problem; 632 error bound analysis (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.2.293 (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:36:y:1988:i:2:p:293-307

Access Statistics for this article

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