Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Florent Breuil Connect in order to contact the contributor
Submitted on : Tuesday, June 5, 2012 - 4:55:04 PM
Last modification on : Wednesday, August 4, 2021 - 3:42:04 PM


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



Record views