A very difficult scheduling problem with communication delays

Han Hoogeveen, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review


A set of unit-time tasks has to be processed on an unrestricted number of processors subject to precedence constraints and unit-time communication delays such that the makespan is minimized. What is the smallest number m* such that increasing the number of processors beyond m* cannot decrease the makespan any more?
Original languageUndefined
Pages (from-to)241-245
Number of pages5
JournalOperations research letters
Issue number5
Publication statusPublished - 2001


  • Makespan
  • IR-74417
  • Computational Complexity
  • Scheduling
  • Parallel computation
  • Precedence constraints
  • Communication delays
  • METIS-203192

Cite this