- 學位論文
Quality Based Measures to Generate Robust Baseline Schedules in the Multi-Mode Resource Constrained Project Scheduling Problem
Quality Based Measures to Generate Robust Baseline Schedules in the Multi-Mode Resource Constrained Project Scheduling Problem
摘要
Whichever the purpose for which a project is developed, and regardless of if it’s executed by common citizens or world-wide corporations, every project has at least two things in common: limited resources and uncertainty. In practice, every project usually has more than one way in which it can be completed and generally a schedule is required in such a way that it makes the best possible use of the limited resources to complete the project in the shortest possible time. In the academic world, this is known as the Multi-mode Resource Constrained Project Scheduling Problem, a widely researched, NP-complete problem. However, not much research has been made on how to make the schedules not only short, and with efficient use of the resources but also flexible enough to withstand the variations caused by the uncertain environment. This thesis researches how to generate robust base-line schedules with the use of an entropy function that generates buffer times only dependent on the activities duration and their relationships, starting from a previously optimized schedule. Later, this value is used as a makespan threshold or upper bound for schedules that maximize a robustness model to add flexibility to the MRCPSP. The initial optimal schedule is found with the help of a proven effective and powerful recent meta-heuristic algorithm, ABC. The results presented in Chapter 5 indicate that with the use of these models it is possible to generate robust base-line schedules. These have enough buffer time to absorb small variations, and generally result in an increase of less than 10% of the optimized makespan but with at least 65% increase in robustness over the initial schedule.
並列摘要
Whichever the purpose for which a project is developed, and regardless of if it’s executed by common citizens or world-wide corporations, every project has at least two things in common: limited resources and uncertainty. In practice, every project usually has more than one way in which it can be completed and generally a schedule is required in such a way that it makes the best possible use of the limited resources to complete the project in the shortest possible time. In the academic world, this is known as the Multi-mode Resource Constrained Project Scheduling Problem, a widely researched, NP-complete problem. However, not much research has been made on how to make the schedules not only short, and with efficient use of the resources but also flexible enough to withstand the variations caused by the uncertain environment. This thesis researches how to generate robust base-line schedules with the use of an entropy function that generates buffer times only dependent on the activities duration and their relationships, starting from a previously optimized schedule. Later, this value is used as a makespan threshold or upper bound for schedules that maximize a robustness model to add flexibility to the MRCPSP. The initial optimal schedule is found with the help of a proven effective and powerful recent meta-heuristic algorithm, ABC. The results presented in Chapter 5 indicate that with the use of these models it is possible to generate robust base-line schedules. These have enough buffer time to absorb small variations, and generally result in an increase of less than 10% of the optimized makespan but with at least 65% increase in robustness over the initial schedule.