Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable

作者：Nieuwoudt I; van Vuuren J H^*

来源：Journal of Scheduling, 2012, 15(6): 681-702.

DOI：10.1007/s10951-012-0291-z

• Shared resource scheduling
• Scheduling with conflict
• Maximum degree colouring

In certain shared resource applications, such as file access scheduling for a network of computer users, some level of conflict between the elements of the schedule is tolerable. A scheduling problem of this nature may be modelled as a generalisation of the classical vertex colouring problem for graphs, called the maximum degree graph colouring problem. In this paper we present four algorithmic procedures for solving the maximum degree graph colouring problem. The first two of these algorithms (a simple heuristic and a tabu search metaheuristic) produce approximate solutions, while the other two algorithms are exact. The runtime efficiencies of and the solution qualities produced by these procedures are tested with respect to a number of graph benchmarks from the literature.

• 出版日期2012-12