Scheduling to minimize the total resource consumption with a constraint on the sum of completion times

Chung Lun Li

doi:10.1016/0377-2217(93)E0255-V

Scheduling to minimize the total resource consumption with a constraint on the sum of completion times

Chung Lun Li

Research output: Journal article publication › Journal article › Academic research › peer-review

20 Citations (Scopus)

Abstract

We consider the problem of scheduling a set of jobs on a single machine where the release time of a job is related to the amount of resource consumed. The objective is to minimize the total amount of resource consumed subject to a constraint on the sum of completion times of the jobs. We show that the problem is NP-hard in general and can be solved efficiently when the resource consumption function is linear. The parallel machine case is also discussed.

Original language	English
Pages (from-to)	381-388
Number of pages	8
Journal	European Journal of Operational Research
Volume	80
Issue number	2
DOIs	https://doi.org/10.1016/0377-2217(93)E0255-V
Publication status	Published - 19 Jan 1995
Externally published	Yes

Keywords

Release dates
Resource allocation
Scheduling
Sequencing

ASJC Scopus subject areas

Information Systems and Management
Management Science and Operations Research
Modelling and Simulation
Statistics, Probability and Uncertainty
Applied Mathematics
Transportation

More information

10.1016/0377-2217(93)E0255-V

Cite this

@article{fb61ea6455c548419862a435aa08da2e,

title = "Scheduling to minimize the total resource consumption with a constraint on the sum of completion times",

abstract = "We consider the problem of scheduling a set of jobs on a single machine where the release time of a job is related to the amount of resource consumed. The objective is to minimize the total amount of resource consumed subject to a constraint on the sum of completion times of the jobs. We show that the problem is NP-hard in general and can be solved efficiently when the resource consumption function is linear. The parallel machine case is also discussed.",

keywords = "Release dates, Resource allocation, Scheduling, Sequencing",

author = "Li, {Chung Lun}",

year = "1995",

month = jan,

day = "19",

doi = "10.1016/0377-2217(93)E0255-V",

language = "English",

volume = "80",

pages = "381--388",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Scheduling to minimize the total resource consumption with a constraint on the sum of completion times

AU - Li, Chung Lun

PY - 1995/1/19

Y1 - 1995/1/19

N2 - We consider the problem of scheduling a set of jobs on a single machine where the release time of a job is related to the amount of resource consumed. The objective is to minimize the total amount of resource consumed subject to a constraint on the sum of completion times of the jobs. We show that the problem is NP-hard in general and can be solved efficiently when the resource consumption function is linear. The parallel machine case is also discussed.

AB - We consider the problem of scheduling a set of jobs on a single machine where the release time of a job is related to the amount of resource consumed. The objective is to minimize the total amount of resource consumed subject to a constraint on the sum of completion times of the jobs. We show that the problem is NP-hard in general and can be solved efficiently when the resource consumption function is linear. The parallel machine case is also discussed.

KW - Release dates

KW - Resource allocation

KW - Scheduling

KW - Sequencing

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

U2 - 10.1016/0377-2217(93)E0255-V

DO - 10.1016/0377-2217(93)E0255-V

M3 - Journal article

SN - 0377-2217

VL - 80

SP - 381

EP - 388

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

Scheduling to minimize the total resource consumption with a constraint on the sum of completion times

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this