Generating the best K sequences in relocation problems

Bertrand M.T. Lin; Shian Shyong Tseng

doi:10.1016/0377-2217(93)90098-8

Generating the best K sequences in relocation problems

Bertrand M.T. Lin, Shian Shyong Tseng^*

^*Corresponding author for this work

Department of Information Management and Finance

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

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 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 language	English
Pages (from-to)	131-137
Number of pages	7
Journal	European Journal of Operational Research
Volume	69
Issue number	1
DOIs	https://doi.org/10.1016/0377-2217(93)90098-8
State	Published - 27 Aug 1993

Keywords

Construction
Optimization
Planning
Scheduling

Access to Document

10.1016/0377-2217(93)90098-8

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

Cite this

@article{0011984fe74042449eec6eccbd4ef182,

title = "Generating the best K sequences in relocation problems",

abstract = "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.",

keywords = "Construction, Optimization, Planning, Scheduling",

author = "Lin, {Bertrand M.T.} and Tseng, {Shian Shyong}",

year = "1993",

month = aug,

day = "27",

doi = "10.1016/0377-2217(93)90098-8",

language = "English",

volume = "69",

pages = "131--137",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Generating the best K sequences in relocation problems

AU - Lin, Bertrand M.T.

AU - Tseng, Shian Shyong

PY - 1993/8/27

Y1 - 1993/8/27

N2 - 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.

AB - 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.

KW - Construction

KW - Optimization

KW - Planning

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=0027640835&partnerID=8YFLogxK

U2 - 10.1016/0377-2217(93)90098-8

DO - 10.1016/0377-2217(93)90098-8

M3 - Article

AN - SCOPUS:0027640835

VL - 69

SP - 131

EP - 137

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -

Generating the best K sequences in relocation problems

Abstract

Keywords

Access to Document

Other files and links

Cite this