### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010 |

Publisher | ACTA Press |

Pages | 278-284 |

Number of pages | 7 |

ISBN (Print) | 9780889868205 |

DOIs | |

State | Published - Jan 1 2010 |

Event | 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010 - Innsbruck, Austria Duration: Feb 16 2010 → Feb 18 2010 |

### Publication series

Name | Proceedings of the 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010 |
---|

### Conference

Conference | 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010 |
---|---|

Country | Austria |

City | Innsbruck |

Period | 2/16/10 → 2/18/10 |

### Keywords

- Algorithms
- Scheduling
- Task allocation
- Task assignment

### ASJC Scopus subject areas

- Computational Theory and Mathematics
- Computer Networks and Communications
- Software

## Fingerprint Dive into the research topics of 'Heterogenous task allocation with constraints'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010*(pp. 278-284). (Proceedings of the 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010). ACTA Press. https://doi.org/10.2316/p.2010.676-086