Generating the best K sequences in relocation problems

Bertrand M.T. Lin, Shian Shyong Tseng*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


There is a set J of h jobs to be processed. For every i, job Ji demands ni units of resources and returns ai units after completion. The problem is to find the best K schedules whose resources requirements are minimum among all h! ones. In this paper, we present some important structural properties and then propose an O(h log h + hK log K) time algorithm, which runs in polynomial time if K is fixed.

Original languageEnglish
Pages (from-to)131-137
Number of pages7
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - 27 Aug 1993


  • Construction
  • Optimization
  • Planning
  • Scheduling

Fingerprint Dive into the research topics of 'Generating the best K sequences in relocation problems'. Together they form a unique fingerprint.

Cite this