Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/17894
Title: Single machine scheduling to minimize total weighted tardiness
Authors: Cheng, TCE 
Ng, CT 
Yuan, JJ
Liu, ZH
Keywords: Due dates
Processing-plus-wait
Single machine scheduling
SLK due-dates
Tardiness
Issue Date: 2005
Publisher: Elsevier
Source: European journal of operational research, 2005, v. 165, no. 2, p. 423-443 How to cite?
Journal: European journal of operational research 
Abstract: The problem of minimizing the total weighted tardiness in single machine scheduling is a well-known strongly NP-hard problem. In this paper, we present an O(n2) time approximation algorithm for the problem, where n is the number of jobs. We further investigate different sub-models of the problem and obtain interesting properties and results. We begin with the model where the job due dates are affine-linear functions of their processing times and the job tardiness weights are proportional to their processing times. For this model, we classify the NP-hardness of the problem with respect to different affine-linear functions, and provide an O(nlogn) algorithm for each of the polynomially solvable problems. The second model we investigate is one where all job due dates have equal slacks, namely the SLK due-date model. Results for this model include: the problem is NP-hard in the ordinary sense; a pseudo-polynomial algorithm with time complexity O(n2P) is derived, where P is the sum of all of the processing times; and a fully polynomial-time approximation scheme is constructed.
Description: This is a special issue for the papers presented in the Eighth International Workshop on Project Management and Scheduling was held in Valencia (Spain), April 3–5, 2002, and was hosted by the Department of Financial and Mathematical Economics and the Department of Statistics and Operational Research of the University of Valencia.
URI: http://hdl.handle.net/10397/17894
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2004.04.013
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

29
Last Week
0
Last month
0
Citations as of Aug 20, 2017

WEB OF SCIENCETM
Citations

24
Last Week
0
Last month
0
Citations as of Aug 4, 2017

Page view(s)

59
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.