Unit-Time Job-Shop Scheduling via mixed graph coloring

by Sotskov, Y.N.; Dolgui, A.; Werner, F.


Preprint series: 00-27, Preprints

The paper is published: International Journal of Mathematical Algorithms, Vol. 2, 2001, 289 -- 323.

05C15 Chromatic theory of graphs and maps
90B35 Scheduling theory, See also {68M20}


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: Scheduling algorithm; Mixed graph; Coloring

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.