An Entropy-Based Upper Bound Methodology for Robust Predictive Multi-Mode RCPSP Schedules
Projects are an important part of our activities and regardless of their magnitude, scheduling is at the very core of every project. In an ideal world makespan minimization, which is the most commonly sought objective, would give us an advantage. However, every time we execute a project we have to d...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2014-09-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1099-4300/16/9/5032 |
| _version_ | 1828116221328883712 |
|---|---|
| author | Angela Hsiang-Ling Chen Yun-Chia Liang Jose David Padilla |
| author_facet | Angela Hsiang-Ling Chen Yun-Chia Liang Jose David Padilla |
| author_sort | Angela Hsiang-Ling Chen |
| collection | DOAJ |
| description | Projects are an important part of our activities and regardless of their magnitude, scheduling is at the very core of every project. In an ideal world makespan minimization, which is the most commonly sought objective, would give us an advantage. However, every time we execute a project we have to deal with uncertainty; part of it coming from known sources and part remaining unknown until it affects us. For this reason, it is much more practical to focus on making our schedules robust, capable of handling uncertainty, and even to determine a range in which the project could be completed. In this paper we focus on an approach to determine such a range for the Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP), a widely researched, NP-complete problem, but without adding any subjective considerations to its estimation. We do this by using a concept well known in the domain of thermodynamics, entropy and a three-stage approach. First we use Artificial Bee Colony (ABC)—an effective and powerful meta-heuristic—to determine a schedule with minimized makespan which serves as a lower bound. The second stage defines buffer times and creates an upper bound makespan using an entropy function, with the advantage over other methods that it only considers elements which are inherent to the schedule itself and does not introduce any subjectivity to the buffer time generation. In the last stage, we use the ABC algorithm with an objective function that seeks to maximize robustness while staying within the makespan boundaries defined previously and in some cases even below the lower boundary. We evaluate our approach with two different benchmarks sets: when using the PSPLIB for the MRCPSP benchmark set, the computational results indicate that it is possible to generate robust schedules which generally result in an increase of less than 10% of the best known solutions while increasing the robustness in at least 20% for practically every benchmark set. And, in an attempt to solve larger instances with 50 or 100 activities, we also used the MRCPSP/max benchmark sets, where the increase of the makespan is approximately 35% with respect to the best known solutions at the same time as with a 20% increase in robustness. |
| first_indexed | 2024-04-11T12:53:32Z |
| format | Article |
| id | doaj.art-0beb5f2489c8435e8785c607add63ffb |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-11T12:53:32Z |
| publishDate | 2014-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-0beb5f2489c8435e8785c607add63ffb2022-12-22T04:23:07ZengMDPI AGEntropy1099-43002014-09-011695032506710.3390/e16095032e16095032An Entropy-Based Upper Bound Methodology for Robust Predictive Multi-Mode RCPSP SchedulesAngela Hsiang-Ling Chen0Yun-Chia Liang1Jose David Padilla2Department of Marketing and Distribution Management, Taoyuan Innovation Institute of Technology, Chungli, Taoyuan County 32003, TaiwanDepartment of Industrial Engineering and Management, Yuan Ze University, Chungli, Taoyuan County 32003, TaiwanDepartment of Industrial Engineering and Management, Yuan Ze University, Chungli, Taoyuan County 32003, TaiwanProjects are an important part of our activities and regardless of their magnitude, scheduling is at the very core of every project. In an ideal world makespan minimization, which is the most commonly sought objective, would give us an advantage. However, every time we execute a project we have to deal with uncertainty; part of it coming from known sources and part remaining unknown until it affects us. For this reason, it is much more practical to focus on making our schedules robust, capable of handling uncertainty, and even to determine a range in which the project could be completed. In this paper we focus on an approach to determine such a range for the Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP), a widely researched, NP-complete problem, but without adding any subjective considerations to its estimation. We do this by using a concept well known in the domain of thermodynamics, entropy and a three-stage approach. First we use Artificial Bee Colony (ABC)—an effective and powerful meta-heuristic—to determine a schedule with minimized makespan which serves as a lower bound. The second stage defines buffer times and creates an upper bound makespan using an entropy function, with the advantage over other methods that it only considers elements which are inherent to the schedule itself and does not introduce any subjectivity to the buffer time generation. In the last stage, we use the ABC algorithm with an objective function that seeks to maximize robustness while staying within the makespan boundaries defined previously and in some cases even below the lower boundary. We evaluate our approach with two different benchmarks sets: when using the PSPLIB for the MRCPSP benchmark set, the computational results indicate that it is possible to generate robust schedules which generally result in an increase of less than 10% of the best known solutions while increasing the robustness in at least 20% for practically every benchmark set. And, in an attempt to solve larger instances with 50 or 100 activities, we also used the MRCPSP/max benchmark sets, where the increase of the makespan is approximately 35% with respect to the best known solutions at the same time as with a 20% increase in robustness.http://www.mdpi.com/1099-4300/16/9/5032MRCPSPABCentropyrobust schedule |
| spellingShingle | Angela Hsiang-Ling Chen Yun-Chia Liang Jose David Padilla An Entropy-Based Upper Bound Methodology for Robust Predictive Multi-Mode RCPSP Schedules Entropy MRCPSP ABC entropy robust schedule |
| title | An Entropy-Based Upper Bound Methodology for Robust Predictive Multi-Mode RCPSP Schedules |
| title_full | An Entropy-Based Upper Bound Methodology for Robust Predictive Multi-Mode RCPSP Schedules |
| title_fullStr | An Entropy-Based Upper Bound Methodology for Robust Predictive Multi-Mode RCPSP Schedules |
| title_full_unstemmed | An Entropy-Based Upper Bound Methodology for Robust Predictive Multi-Mode RCPSP Schedules |
| title_short | An Entropy-Based Upper Bound Methodology for Robust Predictive Multi-Mode RCPSP Schedules |
| title_sort | entropy based upper bound methodology for robust predictive multi mode rcpsp schedules |
| topic | MRCPSP ABC entropy robust schedule |
| url | http://www.mdpi.com/1099-4300/16/9/5032 |
| work_keys_str_mv | AT angelahsianglingchen anentropybasedupperboundmethodologyforrobustpredictivemultimodercpspschedules AT yunchialiang anentropybasedupperboundmethodologyforrobustpredictivemultimodercpspschedules AT josedavidpadilla anentropybasedupperboundmethodologyforrobustpredictivemultimodercpspschedules AT angelahsianglingchen entropybasedupperboundmethodologyforrobustpredictivemultimodercpspschedules AT yunchialiang entropybasedupperboundmethodologyforrobustpredictivemultimodercpspschedules AT josedavidpadilla entropybasedupperboundmethodologyforrobustpredictivemultimodercpspschedules |