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.
International Journal of Operational Research, 2009 Vol.6 No.3, pp.405 - 419
Published online: 09 Jul 2009 *Full-text access for editors Access for subscribers Purchase this article Comment on this article