Date on Master's Thesis/Doctoral Dissertation
7-2009
Document Type
Master's Thesis
Degree Name
M. Eng.
Department
Computer Engineering and Computer Science
Committee Chair
Hardin, Charles Timothy
Subject
Heuristic; Production management; Personnel management--Data processing
Abstract
The Naval Surface Warfare Center wishes to create a task assignment schedule with a minimal training cost for workers to raise their skills to the required levels. As the number of workers, skills, and tasks increase, the problem quickly becomes too large to solve through brute force. Already several greedy heuristics have been produced, though their performance degrades for larger data sets. As Genetic Algorithms (GA) are effective for large combinatorial problems, their application to the task assignment problem may prove successful. The innovation in applying a GA to this problem is the utilization of existing greedy heuristics in the crossover operator. As the population begins to converge in the GA, the greedy algorithm benefits by having fewer tasks to assign. Likewise, the GA benefits from the addition of the greedy heuristic by increasing the likelihood of good valid solutions within the population. To explore the effectiveness of the proposed method, several different crossover operators are defined. The first method is purely random to act as a control, as the only improvements will be due to the genetic algorithm. The second method provides a basic heuristic to improve upon the random crossover operator, while still primarily stochastic and therefore relying on the GA for convergent behavior. The final two techniques incorporate existing greedy heuristics. The four crossover operators are tested against several data sets of varying sizes to ascertain their relative performance. Crossover methods are compared based on the best score found over all runs. In addition, the evolution and convergence of populations for the different operators are examined, offering further insight into their performance. The combination of a greedy heuristic and genetic algorithm proves to be an effective method for approaching the task assignment problem. This method compares favorably to existing techniques, as well as a purely genetic approach. While the greedy genetic approach suffers some shortcomings, the success of the combined algorithm warrants further development of this methodology.
Recommended Citation
Grieshaber, Daniel 1986-, "A hybrid genetic-greedy approach to the skills management problem." (2009). Electronic Theses and Dissertations. Paper 532.
https://doi.org/10.18297/etd/532
