Date on Master's Thesis/Doctoral Dissertation


Document Type

Doctoral Dissertation

Degree Name

Ph. D.


Industrial Engineering

Degree Program

Industrial Engineering, PhD

Committee Chair

DePuy, Gail W.

Committee Co-Chair (if applicable)

Biles, William

Committee Member

Biles, William

Committee Member

Hardin, C. Tim

Committee Member

Ouyang, Ming


Assigning workers, each with their own skill set, to tasks which demand different skills in an efficient manner is a challenging problem that often requires workers to receive additional training. The training of workers is very costly with Training Magazine’s Annual Industry Report stating 58.5 billion dollars were spent in 2007 on employee training in the United States. Therefore assigning workers to tasks in such a way as to minimize the overall training costs is an important problem in many organizations. In this research, the assignment problem with dependent cost is considered, i.e. the training cost associated with assigning a worker to a particular task depends on the training the worker receives for their other assigned tasks. Once a worker is trained in a skill that training will available for any additional tasks that may be assigned. The problem is formulated mathematically as an integer linear program. Based on past research, high quality solutions to large-size problems are difficult to obtain. This research develops and upper bound approach and three heuristic solution methodologies. The basic idea of the heuristics is to form groups of tasks which require similar skills, then assign a worker to the task group. The Shortest Augmenting Path (SAP) algorithm of Jonker and Volgenant is known to quickly find the optimal assignment of N workers to N tasks. This SAP algorithm will be used in this research after grouping the tasks into N groups which can then be assigned to the N workers. The task grouping heuristic methods developed in this research were tested for several randomly generated large-sized data sets. Results showed an average 7.34% improvement compared to previous solution methods. Additionally to consider workers’ preferences, a multiple-objective model is presented for the skills management problem to maximize workers’ preferences and aggregate training while minimizing training cost. The model is demonstrated for randomly generated data sets.