Search

Showing total 31,434 results
Start Over Journal ifac proceedings volumes
31,434 results

197. Unit-Time Job-Shop Scheduling by Algorithm for Mixed Graph Coloring (Invited paper)

Author

Georgi V. Andreev, Yuri N. Sotsko, and Alexandre B. Dolgu

Subjects
Discrete mathematics, Combinatorics, Greedy coloring, Edge coloring, Neighbourhood (graph theory), Bound graph, Complete coloring, Graph coloring, Fractional coloring, Algorithm, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics, List coloring
Abstract

A job-shop problem with unit processing time of each operation and makespan criterion is interpreted as a mixed graph coloring, i.e. as an assignment of t positive integers (colors) 1,2,...,t to vertices V={V 1 , V 2 , ..., V n } ofa mixed graph (V, A, E) such that, if vertices vp and vq are joined by an edge [v p , V q ɛ A, then their colors have to be different, and if two vertices are joined by an arc (Vi, Vj) E A, then the color of vertex Vi has to be smaller than the color of vertex V j . The optimal coloring of the special mixed graph G = (V, A, E) defines the schedule minimizing makespan for the unit-time job-shop problem denoted by J(p 1 =1)C max New algorithm for optimal coloring of such a mixed graph G is described briefly. This algorithm is realized as a branch-and-bound one and provides acceptable computational results for optimal coloring of mixed graphs G randomly generated with n ≤ 180 and (E) ≤ 1500, the cardinality of the set of arcs A being not critical.

Published
2000