Mixed Graph Colouring as Scheduling a Partially Ordered Set of Interruptible Multi-Processor Tasks with Integer Due Dates

Abstract

We investigate relationships between scheduling problems with the bottleneck objective functions (minimising makespan or maximal lateness) and problems of optimal colourings of the mixed graphs. The investigated scheduling problems have integer durations of the multi-processor tasks (operations), integer release dates and integer due dates of the given jobs. In the studied scheduling problems, it is required to find an optimal schedule for processing the partially ordered operations, given that operation interruptions are allowed and indicated subsets of the unit-time operations must be processed simultaneously. First, we show that the input data for any considered scheduling problem can be completely determined by the corresponding mixed graph. Second, we prove that solvable scheduling problems can be reduced to problems of finding optimal colourings of corresponding mixed graphs. Third, finding an optimal colouring of the mixed graph is equivalent to the considered scheduling problem determined by the same mixed graph. Finally, due to the proven equivalence of the considered optimisation problems, most of the results that were proven for the optimal colourings of mixed graphs generate similar results for considered scheduling problems, and vice versa.

Keywords

• scheduling
• maximal lateness
• makespan
• multi-processor task
• mixed graph colouring