Some results of the relocation problems with processing times and deadlines

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

The relocation problem originates from the public housing project so as to minimize the budgets. Given a set of jobs each demands n i units of resources for processing and returns aiunits of resources. The relocation problem is to determine the minimum resource requirements demanded by the successful completion of this set of jobs. In the literature, an O(h* log h) algorithm has been proposed by Kaplan and Amir, where h is the number of jobs. In this paper, we consider the relocation problem with processing times and deadlines in which each job is additionally associated with a processing length and an individual deadline. Studies of NP-completeness of some versions of this problem are included. Also, we propose two polynomial algorithms, one runs in O(h* log h) time and the other in O(h2* log h) time, to solve some further restricted problems.

Original languageEnglish
Pages (from-to)1-15
Number of pages15
JournalInternational Journal of Computer Mathematics
Volume40
Issue number1-2
DOIs
StatePublished - 1 Jan 1991

Keywords

  • algorithm
  • deadline
  • NP-complete
  • processing time
  • Relocation problem
  • scheduling

Fingerprint Dive into the research topics of 'Some results of the relocation problems with processing times and deadlines'. Together they form a unique fingerprint.

Cite this