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

摘要

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.