Heterogenous task allocation with constraints

Task allocation is a common problem in both distributed computing and applied scheduling problems. A task allocation problem arises wherever there are tasks that must be scheduled onto a number of processors with no precedence constraints between tasks. One variation of this problem deals with heterogeneous tasks, where each processor is only capable of executing a subset of the total tasks. This problem has been considered many times, however the literature has largely neglected consideration of constraints placed on processors other than availability. These constraints arise in the real world under a large number of circumstances, one of the largest being retail labor scheduling and related areas. As margins for retail stores decrease, the importance of optimizing labor costs increases and the traditional ad-hoc scheduling methods have problems balancing feasibility of schedules with minimization of cost. Results from task allocation provide a promising avenue for solving this problem as well as problems in a variety of other fields. In this paper we develop two candidate models for this task allocation problem as well as show the equivalence between this problem and a variant of the weighted graph coloring problem. We use these two models to explore two heuristics and compare their performance with that of other algorithms for general weighted graph coloring.