# 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 :
Document type :
Journal articles

https://hal-emse.ccsd.cnrs.fr/emse-00704571
Contributor : Florent Breuil <>
Submitted on : Tuesday, June 5, 2012 - 4:55:04 PM
Last modification on : Wednesday, August 4, 2021 - 3:42:04 PM

### Identifiers

• 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⟩

Record views