An algorithm for the N/M/parallel/Cmaxpreemptive due-date scheduling problem

Edwin Tai Chiu Cheng; C. C.S. Sin

doi:10.1016/0167-188X(91)90017-V

An algorithm for the N/M/parallel/C_maxpreemptive due-date scheduling problem

Edwin Tai Chiu Cheng, C. C.S. Sin

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

2 Citations (Scopus)

Abstract

In this paper we consider the problem of scheduling n independent jobs on m parallel and identical machines with preemptions. The objective is to minimize the maximum job completion time (or makespan) while meeting all job due-dates. We present an algorithm which is able to generate a due-date schedule, if one exists, and to find the minimum makespan. We also discuss the relevance of the number of job preemptions as a performance measure for the class of parallel-machine scheduling problems. Finally, we identify some potential areas worthy of further research.

Original language	English
Pages (from-to)	43-49
Number of pages	7
Journal	Engineering Costs and Production Economics
Volume	21
Issue number	1
DOIs	https://doi.org/10.1016/0167-188X(91)90017-V
Publication status	Published - 1 Jan 1991
Externally published	Yes

ASJC Scopus subject areas

General Engineering

More information

10.1016/0167-188X(91)90017-V

Cite this

@article{7cf0dcecbed14a488289fe312848094c,

title = "An algorithm for the N/M/parallel/Cmaxpreemptive due-date scheduling problem",

abstract = "In this paper we consider the problem of scheduling n independent jobs on m parallel and identical machines with preemptions. The objective is to minimize the maximum job completion time (or makespan) while meeting all job due-dates. We present an algorithm which is able to generate a due-date schedule, if one exists, and to find the minimum makespan. We also discuss the relevance of the number of job preemptions as a performance measure for the class of parallel-machine scheduling problems. Finally, we identify some potential areas worthy of further research.",

author = "Cheng, {Edwin Tai Chiu} and Sin, {C. C.S.}",

year = "1991",

month = jan,

day = "1",

doi = "10.1016/0167-188X(91)90017-V",

language = "English",

volume = "21",

pages = "43--49",

journal = "Engineering Costs and Production Economics",

issn = "0167-188X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - An algorithm for the N/M/parallel/Cmaxpreemptive due-date scheduling problem

AU - Cheng, Edwin Tai Chiu

AU - Sin, C. C.S.

PY - 1991/1/1

Y1 - 1991/1/1

N2 - In this paper we consider the problem of scheduling n independent jobs on m parallel and identical machines with preemptions. The objective is to minimize the maximum job completion time (or makespan) while meeting all job due-dates. We present an algorithm which is able to generate a due-date schedule, if one exists, and to find the minimum makespan. We also discuss the relevance of the number of job preemptions as a performance measure for the class of parallel-machine scheduling problems. Finally, we identify some potential areas worthy of further research.

AB - In this paper we consider the problem of scheduling n independent jobs on m parallel and identical machines with preemptions. The objective is to minimize the maximum job completion time (or makespan) while meeting all job due-dates. We present an algorithm which is able to generate a due-date schedule, if one exists, and to find the minimum makespan. We also discuss the relevance of the number of job preemptions as a performance measure for the class of parallel-machine scheduling problems. Finally, we identify some potential areas worthy of further research.

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

U2 - 10.1016/0167-188X(91)90017-V

DO - 10.1016/0167-188X(91)90017-V

M3 - Journal article

SN - 0167-188X

VL - 21

SP - 43

EP - 49

JO - Engineering Costs and Production Economics

JF - Engineering Costs and Production Economics

IS - 1

ER -

An algorithm for the N/M/parallel/C_maxpreemptive due-date scheduling problem

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this