Multi-mode resource-constrained project scheduling problem with resource vacations and task splitting Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/h415pd69f

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • The research presented in this dissertation addresses the Multi-Mode Resource-Constrained Project Scheduling Problem (MMRCPSP) in the presence of resource unavailability. This research is motivated by the scheduling of engineering design tasks in automotive product development to minimize the project completion time, but addresses a general scheduling situation that is applicable in many contexts. The current body of MMRCPSP research typically assumes that, 1) individual resource units are available at all times when assigning tasks to resources and, 2) before assigning tasks to resources, there must be enough resource availability over time to complete the task without interruption. In many situations such as assigning engineering design tasks to designers, resources are not available over the entire project-planning horizon. In the case of engineering designers and other human resources, unavailability may be due to several reasons such as vacation, training, or being scheduled to do other tasks outside the project. In addition, when tasks are scheduled they are often split to accommodate unavailable resources and are not completed in one continuous time segment. The objectives of this research are to obtain insight into the types of project scheduling situations where task splitting may result in significant makespan improvements, and to develop a fast and effective scheduling heuristic for such situations. A designed computational experiment was used to gain insight into when task splitting may provide significant makespan improvements. Problem instances were randomly generated using a modification of a standard problem generator, and optimally solved with and without task splitting using a branch and bound algorithm. In total 3,880 problem instances were solved with and without task splitting. Statistical analysis of the experimental data reveals that high resource utilization is the most important factor affecting the improvements obtained by task splitting. The analysis also shows that splitting is more helpful when resource unavailability occurs in multiple periods of short duration versus fewer periods of long duration. Another conclusion from the analysis indicates that the project precedence structure and the number (not amount) of resources used by tasks do not significantly affect the improvements due to task splitting. Using the insights from the computational testing, a new heuristic is developed that can be applied to large problems. The heuristic is an implementation of a simple priority rule-based heuristic with a new parameter used to control the number of task splits. It is desirable to obtain the majority of task splitting benefits with the smallest number of split tasks. Computational experiments are conducted to evaluate its performance against known optimal solutions for small sized problems. A deterministic version of the heuristic found optimal solutions for 33% of the problems and a stochastic version found optimal solutions for over 70%. The average percent increase in makespan compared to optimal was 7.58% for the deterministic heuristic and less than 2% for the stochastic versions demonstrating acceptable performance.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2012-07-24T19:20:47Z (GMT). No. of bitstreams: 1 BuddhakulsomsiriJirachai2003.pdf: 2233499 bytes, checksum: 8852605e248423ad38f14fd8636f8a0a (MD5) Previous issue date: 2003-03-14
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-07-24T19:20:47Z (GMT) No. of bitstreams: 1 BuddhakulsomsiriJirachai2003.pdf: 2233499 bytes, checksum: 8852605e248423ad38f14fd8636f8a0a (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-07-24T19:15:27Z (GMT) No. of bitstreams: 1 BuddhakulsomsiriJirachai2003.pdf: 2233499 bytes, checksum: 8852605e248423ad38f14fd8636f8a0a (MD5)
  • description.provenance : Submitted by Kevin Martin (martikev@onid.orst.edu) on 2012-07-10T21:25:36Z No. of bitstreams: 1 BuddhakulsomsiriJirachai2003.pdf: 2233499 bytes, checksum: 8852605e248423ad38f14fd8636f8a0a (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items