Title: Scheduling with undirected graphs: motivations and reviews

Authors: Mourad Boudhar

Addresses: Faculty of Mathematics, University USTHB, BP 32, Bab-Ezzouar, El-Alia 16111, Algiers, Algeria

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.

DOI: 10.1504/IJOR.2009.026940

International Journal of Operational Research, 2009 Vol.6 No.3, pp.405 - 419

Published online: 09 Jul 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article