Michael Pavlin
Scheduling problems arise in contexts where we have limited resources to accomplish a set of tasks. These are both common and often very difficult. The multi-processor total tardiness problem (MPTTP) is no exception and has been shown to be NP-hard. This problem involves scheduling a set of jobs onto a set of processors such that an objective which penalizes late jobs is minimized. Optimal algorithms have proven to be impractical for MPTTP instances of any size. This provides motivation to investigate stochastic search algorithms as an effective means to reliably find good solutions in tolerable time frames. In particular, we are investigating the application of iterated local search algorithms to the MPTTP and possible benefits of population based extensions.