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

**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