Unit-time Job-shop Scheduling via Mixed Graph Coloring - Archive ouverte HAL Access content directly
Journal Articles International Journal of Mathematical Algorithms Year : 2001

Unit-time Job-shop Scheduling via Mixed Graph Coloring

, (1, 2) , (3)
1
2
3

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

Dates and versions

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

Identifiers

  • HAL Id : emse-00704571 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More