Citation
Bmt. Lin et Ss. Tseng, GENERATING THE BEST K-SEQUENCES IN RELOCATION PROBLEMS, European journal of operational research, 69(1), 1993, pp. 131-137
Citations number
16
Categorie Soggetti
Management,"Operatione Research & Management Science
Journal title
ISSN journal
03772217
Volume
69
Issue
1
Year of publication
1993
Pages
131 - 137
Database
ISI
SICI code
0377-2217(1993)69:1<131:GTBKIR>2.0.ZU;2-M
Abstract
There is a set J of h jobs to be processed. For every i, job J(i) dema
nds n(i) units of resources and returns a(i) units after completion. T
he problem is to find the best K schedules whose resource requirements
are minimum among all h! ones. In this paper, we present some importa
nt structural properties and then propose an O(h log h + hK log K) tim
e algorithm, which runs in polynomial time if K is fixed.