Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/10416
Title: Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due date constraints
Authors: Lin, BMT
Cheng, TCE 
Issue Date: 1999
Publisher: Elsevier
Source: European journal of operational research, 1999, v. 116, no. 1, p. 183-193 How to cite?
Journal: European journal of operational research 
Abstract: The relocation problem addressed in this paper is to determine a reconstruction sequence for a set of old buildings, under a limited budget, such that there is adequate temporary space to house the residents decanted during rehabilitation. It can be regarded as a resource-constrained scheduling problem where there is a set of jobs to be processed on a single machine. Each job demands a number of resources for processing and returns probably a different number of resources on its completion. Given a number of initial resources, the problem seeks to determine if there is a feasible sequence for the successful processing of all the jobs. Two generalizations of the relocation problem in the context of single machine scheduling with due date constraints are studied in this paper. The first problem is to minimize the weighted number of tardy jobs under a common due date. We show that it is NP-hard even when all the jobs have the same tardy weight and the same resource requirement. A dynamic programming algorithm with pseudo-polynomial computational time is proposed for the general case. In the second problem, the objective is to minimize the maximum tardiness when each job is associated with an individual due date. We prove that it is strongly NP-hard. We also propose a pseudo-polynomial time dynamic programming algorithm for the case where the number of possible due dates is predetermined.
URI: http://hdl.handle.net/10397/10416
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/S0377-2217(98)00196-9
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

6
Last Week
0
Last month
0
Citations as of Aug 18, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Aug 13, 2017

Page view(s)

44
Last Week
3
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



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