New heuristics for the multi-mode resource investment problem

2001 2001

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)

Operations research
0796: Operations research
Identifier / keyword
Applied sciences; Heuristics; Project scheduling; Resource investment problem
New heuristics for the multi-mode resource investment problem
Hsu, Chih-Cheng
Number of pages
Publication year
Degree date
School code
DAI-B 62/01, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
9780493083582, 0493083588
Giglio, Richard J.
University of Massachusetts Amherst
University location
United States -- Massachusetts
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.