# Unit-time Job-shop Scheduling via Mixed Graph Coloring

Abstract : A unit-time scheduling problem with makespan criterion may be interpreted as an optimal coloring of the vertices of a mixed graph, where the number of colors is minimal. We consider an optimal coloring which defines a schedule that minimizes the makespan for a unit-time job-shop problem, present complexity results for some special cases and improve a geometrical algorithm. For the general case, we develop three branch-and-bound algorithms and test them on randomly generated mixed graphs of order $n \leq 200$ for the exact solution and of order $n \leq 900$ for the approximate solution, where $n$ is the number of vertices.
Keywords :
Type de document :
Article dans une revue
International Journal of Mathematical Algorithms, 2001, 2 (4), pp.289-325
Domaine :

https://hal-emse.ccsd.cnrs.fr/emse-00704571
Contributeur : Florent Breuil <>
Soumis le : mardi 5 juin 2012 - 16:55:04
Dernière modification le : dimanche 28 janvier 2018 - 15:22:05

### Identifiants

• HAL Id : emse-00704571, version 1

### Citation

Yuri Sotskov, Alexandre Dolgui, Frank Werner. Unit-time Job-shop Scheduling via Mixed Graph Coloring. International Journal of Mathematical Algorithms, 2001, 2 (4), pp.289-325. 〈emse-00704571〉

### Métriques

Consultations de la notice