Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due date constraints

Bertrand M.T. Lin*, T. C.E. Cheng

*Corresponding author for this work

研究成果: Article同行評審

6 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)183-193
期刊European Journal of Operational Research
出版狀態Published - 1 七月 1999

指紋 深入研究「Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due date constraints」主題。共同形成了獨特的指紋。