A very difficult scheduling problem with communication delays

J.A. Hoogeveen, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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? We prove that answering this problem is complete for the complexity class . Hence, the problem is at least as difficult as all the problems in and at least as difficult as all the problems in , and unless some complexity classes collapse, it is even more difficult than all these problems. This answers a question raised by Ivan Rival.
Original languageEnglish
Pages (from-to)241-245
JournalOperations Research Letters
Volume29
Issue number5
DOIs
Publication statusPublished - 2001

Fingerprint

Dive into the research topics of 'A very difficult scheduling problem with communication delays'. Together they form a unique fingerprint.

Cite this