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

Research output: Journal article publicationJournal articleAcademic researchpeer-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 languageEnglish
Pages (from-to)43-49
Number of pages7
JournalEngineering Costs and Production Economics
Volume21
Issue number1
DOIs
Publication statusPublished - 1 Jan 1991
Externally publishedYes

ASJC Scopus subject areas

  • Engineering(all)

Cite this