New heuristics for the multi-mode resource investment problem

The Multi-Mode Resource Investment Problem (MMRIP), which is a specific class of project scheduling problems, is the topic of this dissertation. A project consists of tasks that follow a specific precedence order, with each task being executed in one of its available modes. Modes for each task are different alternatives for completing a task, and may differ in their resource consumption and duration. The goal in the MMRIP is to select a mode and starting time for each task so that the project due date is met with minimal resource investment. This research is inspired by a real scheduling problem from a large engineering organization, but has applications in many other areas such as service industry and production scheduling. Even with such wide spread applicability, a review of the literature in project scheduling and related areas shows that work in the MMRIP is limited and no practical and effective methods is discovered. The opportunity exists to make both a theoretical and practical contribution in project scheduling research. In this dissertation an effective heuristic for this computationally intractable problem is developed and documented. This enhanced priority rule heuristic simultaneously considers both due date constraints and resource usage to select and schedule tasks in one decision step. This differs from previous priority rule heuristics that require two decision steps. Modifications, including stochastic search and local improvement techniques, are also developed and tested. Computational tests of the new heuristics and comparisons to existing heuristic are conducted. With 600 test instances, the best of the new heuristics performs 15% better than the best existing heuristic. The new heuristic (without stochastic search, or local improvement implemented) performs, on average, 12.6% above optimal in 30 test instances. Computation times with the new heuristic are negligible on a typical personal computer (1999 processor), for a real size problem of 35 tasks. The inclusion of stochastic search techniques takes the computation times up to several minutes