GENERATING THE BEST K-SEQUENCES IN RELOCATION PROBLEMS

Abstract

There is a set J of h jobs to be processed. For every i, job J(i) demands n(i) units of resources and returns a(i) units after completion. The problem is to find the best K schedules whose resource 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.