A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness

Philippe Baptiste, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

We study the scheduling situation where n tasks, subjected to release dates and due dates, have to be scheduled on m parallel processors. We show that, when tasks have unit processing times and either require 1 or m processors simultaneously, the minimum maximal tardiness can be computed in polynomial time. Two algorithms are described. The first one is based on a linear programming formulation of the problem while the second one is a combinatorial algorithm. The complexity status of this "tall/small" task scheduling problem P|r i,p i = 1, size i ∈ {1, m}|T max was unknown before, even for two processors.

Original languageEnglish (US)
Pages (from-to)395-404
Number of pages10
JournalJournal of Scheduling
Volume6
Issue number4
DOIs
StatePublished - Jul 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Keywords

  • Linear programming
  • Multiprocessor task scheduling
  • Unit processing times

Fingerprint Dive into the research topics of 'A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness'. Together they form a unique fingerprint.

Cite this