Date on Master's Thesis/Doctoral Dissertation
6-2007
Document Type
Master's Thesis
Degree Name
M. Eng.
Department
Industrial Engineering
Committee Chair
Depuy, Gail W.
Subject
Production management; Personnel management--Data processing
Abstract
Assigning workers to tasks in an efficient and cost effective manner is a problem that nearly every company faces. This task assignment problem can be very time consuming to solve optimally. This difficulty increases as problem size increases. Most companies are large enough that it isn't feasible to find an optimal assignment; therefore a good heuristic method is needed. This project involved creating a new heuristic to solve this problem by combining the Greedy Algorithm with the Meta-RaPS method. The Greedy Algorithm is a near-sighted assignment procedure that chooses the best assignment at each step until a full solution is found. Although the Greedy Algorithm finds a good solution for small to medium sized problems, introducing randomness using the meta-heuristic Meta-RaPS results in a better solution. The new heuristic runs 5000 iterations and reports the best solution. The final Excel® VBA program solves a small sized problem in less than one minute, and is within 10% of the optimal solution, making it a good alternative to time consuming manual assignments. Although larger, more realistic problems will take longer to solve, good solutions will be available in a fraction of the time compared to solving them optimally.
Recommended Citation
Douglas, Allison M., "A modified greedy algorithm for the task assignment problem." (2007). Electronic Theses and Dissertations. Paper 369.
https://doi.org/10.18297/etd/369
