Using mixed graph coloring to minimize total completion time in job shop scheduling

The problem of scheduling a set of jobs with unit operation times in a job shop to minimize total completion time is addressed. It is shown that this problem can be modeled as finding the optimal coloring of a special mixed graph. Subgraph of such a mixed graph without edges represents union of paths, and subgraph without arcs represents union of cliques. Finding the optimal coloring of the mixed graph with the criterion of minimizing the sum of maximal colors (used for the paths) is shown to determine a schedule for minimizing total completion time for processing jobs in a job shop. Since the problem is NP-hard, we develop a branch and bound algorithm for obtaining the optimal coloring of such a mixed graph. We develop a color-based branching scheme, dominance of the vertices in the solution tree, and three lower bounds of the objective function. The computational experiments indicate that the branch and bound algorithm performs well for randomly generated mixed graphs of order up to 200, if all the paths in the directed subgraph (job routes) have the same length, and of order up to 750 otherwise. Since in the considered job shop problem, machine repetition and absence of some machines in the job route are allowed, the developed methodology can be used to minimize total completion time in the job shop with arbitrary integer operation durations.