Scheduling with undirected graphs: motivations and reviews

Mourad Boudhar

International Journal of Operational Research, 2009, vol. 6, issue 3, 405-419

Abstract: In this paper, we aim at compiling the bibliography and the recent developments on scheduling problems involving undirected graphs. Two types of problems are considered: the mutual exclusion scheduling and the scheduling with batch-compatible jobs. We first consider the scheduling problems that can be solved by creating an undirected graph with a vertex for each job and an edge between every pair of conflicting jobs. Then, we consider the problem of minimising the makespan on a batch processing machine in which jobs are not at all compatible. This relation of compatibility is represented by an undirected graph called 'compatibility graph'.

Keywords: mutual exclusion; batch processing; batch scheduling; job compatibilities; compatibility graphs; undirected graphs. (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=26940 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:6:y:2009:i:3:p:405-419

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().