### 2000-27

#### Unit-Time Job-Shop Scheduling via mixed graph coloring

Series: 2000-27, Preprints

MSC:
05C15 Coloring of graphs and hypergraphs
90B35 Scheduling theory, deterministic

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

This paper was published in:
International Journal of M