Unit-time Job-shop Scheduling via Mixed Graph Coloring - Mines Saint-Étienne Access content directly
Journal Articles International Journal of Mathematical Algorithms Year : 2001

Unit-time Job-shop Scheduling via Mixed Graph Coloring


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.
No file

Dates and versions

emse-00704571 , version 1 (05-06-2012)


  • HAL Id : emse-00704571 , version 1


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⟩
150 View
0 Download


Gmail Facebook X LinkedIn More