On a multiprocessor job scheduling problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A multiprocessor job scheduling problem is discussed. The scheduling problem has been transformed into a graph partitioning problem. It has been shown that for a general graph the problem is NP-complete. An integer linear programming formulation is given for the graph partitioning problem. The scheduling problem can then be solved using one of the several methods for solving integer linear programming problems. A linear time algorithm is also given for the case when the graph is a tree. This problem is a generalization of the chromatic sum problem.

Original languageEnglish (US)
Title of host publicationConference Record - Asilomar Conference on Circuits, Systems & Computers
PublisherPubl by Maple Press, Inc
Number of pages5
StatePublished - 1991
Event24th Asilomar Conference on Signals, Systems and Computers Part 2 (of 2) - Pacific Grove, CA, USA
Duration: Nov 5 1990Nov 7 1990


Other24th Asilomar Conference on Signals, Systems and Computers Part 2 (of 2)
CityPacific Grove, CA, USA

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'On a multiprocessor job scheduling problem'. Together they form a unique fingerprint.

Cite this