×

zbMATH — the first resource for mathematics

Stochastic project scheduling with hierarchical alternatives. (English) Zbl 07166838
Summary: In this paper, a resource constrained project scheduling problem with hierarchical alternatives and stochastic activity durations is studied. A stochastic chance constraint is introduced to formulate this problem. A metaheuristic framework called SAA/DAAA through integrating the sampling average approximation (SAA) with the population-based evolutionary artificial algae algorithm (AAA) is developed to solve the problem due to the NP-hardness nature of the problem. The priority-selection list (PSL) and schedule generation scheme (SGS) are introduced for local search. Experiments with different sizes (50-scale, 100-scale, 150-scale) as well as different uncertainty levels (moderate, medium, high) are used as examples to illustrate and validate the proposed method. The influences of sample size, sampling times and confidence level are also analyzed during experiments. In addition, the proposed discrete AAA (DAAA) is compared with classic GA and numerical experiments show that the SAA/DAAA outperforms the SAA/GA in terms of both objectives and solving time.

MSC:
90 Operations research, mathematical programming
65 Numerical analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Wu, I. C.; Borrmann, A.; Beibert, U., Bridge construction schedule generation with pattern-based construction methods and constraint-based simulation, Adv. Eng. Inform., 24, 4, 379-388 (2010)
[2] Ranjbar, M.; Hosseinabadi, S.; Abasian, F., Minimizing total weighted late work in the resource-constrained project scheduling problem, Appl. Math. Model., 37, 23, 9776-9785 (2013) · Zbl 1427.90157
[3] Liu, J. J.; Teo, K. L.; Wang, X. Y.; Wu, C. Z., An exact penalty function-based differential search algorithm for constrained global optimization, Soft Comput., 20, 4, 1305-1313 (2016)
[4] Van Peteghem, V.; Vanhoucke, M., An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances, Eur. J. Oper. Res., 235, 1, 62-72 (2014) · Zbl 1305.90203
[5] Wauters, T.; Kinable, J.; Smet, P.; Vancroonenburg, W.; Vanden Berghe, G.; Verstichel, J., The multi-mode resource-constrained multi-project scheduling problem, J. Sched., 19, 3, 271-283 (2016) · Zbl 1347.90052
[6] Schnell, A.; Hartl, R. F., On the efficient modeling and solution of the multi-mode resource-constrained project scheduling problem with generalized precedence relations, OR Spectr., 38, 2, 283-303 (2016) · Zbl 1339.90151
[7] Fu, F., Integrated scheduling and batch ordering for construction project, Appl. Math. Model., 38, 2, 784-797 (2014) · Zbl 1427.90139
[8] Coelho, J.; Vanhoucke, M., Multi-mode resource-constrained project scheduling using RCPSP and sat solvers, Eur. J. Oper. Res., 213, 1, 73-82 (2011) · Zbl 1237.90086
[9] Huang, X.; Zhao, T., Project selection and scheduling with uncertain net income and investment cost, Appl. Math. Comput., 247, 1, 61-71 (2014) · Zbl 1338.90201
[10] Tofighian, A. A.; Naderi, B., Modeling and solving the project selection and scheduling, Comput. Ind. Eng., 83, 1, 30-38 (2015)
[11] Huang, X.; Zhao, T.; S, K., Uncertain mean-variance and mean-semivariance models for optimal project selection and scheduling, Knowl.-Based Syst., 93, 1, 1-11 (2016)
[12] Capek, R.; Sucha, P.; Hanzalek, Z., Production scheduling with alternative process plans, Eur. J. Oper. Res., 217, 1, 300-311 (2012) · Zbl 1244.90090
[13] Coolen, K.; Wei, W. C.; Nobibon, F. T.; Leus, R., Scheduling modular projects on a bottleneck resource, J. Sched., 17, 1, 67-85 (2014) · Zbl 1297.90038
[14] Kellenbrink, C.; Helber, S., Scheduling resource-constrained projects with a flexible project structure, Eur. J. Oper. Res., 246, 2, 379-391 (2015) · Zbl 1346.90356
[15] Johannes, B., On the complexity of scheduling unit-time jobs with or-precedence constraints, Oper. Res. Lett., 33, 6, 587-596 (2005) · Zbl 1082.90037
[16] Belhe, U.; Kusiak, A., Scheduling modular projects on a bottleneck resource, IEEE Trans. Eng. Manag., 42, 2, 150-158 (1995)
[17] Vanhoucke, M.; Coelho, J., An approach using sat solvers for the rcpsp with logical constraints, Eur. J. Oper. Res., 249, 2, 577-591 (2016) · Zbl 1346.90449
[18] Ke, H.; Liu, B., Fuzzy project scheduling problem and its hybrid intelligent algorithm, Appl. Math. Model., 34, 2, 301-308 (2010) · Zbl 1185.90080
[19] Yakhchali, S. H.; Ghodsypour, S. H., On the latest starting times and criticality of activities in a network with imprecise durations, Appl. Math. Model., 34, 8, 2044-2058 (2010) · Zbl 1193.90118
[20] Li, H. T.; Womer, N. K., Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming, Eur. J. Oper. Res., 246, 1, 20-33 (2015) · Zbl 1346.90405
[21] Li, H. B.; Xu, Z.; Demeulemeester, E., Scheduling policies for the stochastic resource leveling problem, J. Constr. Eng. Manag., 141, 2, 04014071 (2015)
[22] Creemers, S., Minimizing the expected makespan of a project with stochastic activity durations under resource constraints, J. Schedul., 18, 3, 263-273 (2015) · Zbl 1320.90040
[23] Lamas, P.; Demeulemeester, E., A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations, J. Schedul., 19, 4, 409-428 (2016) · Zbl 1347.90045
[24] Li, H. B.; Demeulemeester, E., A genetic algorithm for the robust resource leveling problem, J. Schedul., 19, 1, 43-60 (2016) · Zbl 1341.90067
[25] Moukrim, A.; Quilliot, A.; Toussaint, H., An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration, Eur. J. Oper. Res., 244, 2, 360-368 (2015) · Zbl 1346.90375
[26] Ballestin, F.; Trautmann, N., An iterated-local-search heuristic for the resource-constrained weighted earliness-tardiness project scheduling problem, Int. J. Prod. Res., 46, 22, 6231-6249 (2008) · Zbl 1154.90353
[27] Zhang, H.; Li, X.; Li, H.; Huang, F., Particle swarm optimization-based schemes for resource-constrained project scheduling, Autom. Constr., 14, 3, 393-404 (2005)
[28] Zhao, C.; Wu, C.; Wang, X.; Ling, B. W.K.; Teo, K. L.; Lee, J. M.; Jung, K. H., Maximizing lifetime of a wireless sensor network via joint optimizing sink placement and sensor-to-sink routing, Appl. Math. Model., 49, 1, 319-337 (2017) · Zbl 07163486
[29] Hou, L.; Zhao, C.; Wu, C.; Moon, S.; Wang, X., Discrete firefly algorithm for scaffolding construction scheduling, J. Comput. Civ. Eng., 31, 3, 04016064 (2016)
[30] Zhao, C.; Wu, C.; Chai, J.; Wang, X.; Yang, X.; Lee, J. M.; Kim, M. J., Decomposition-based multi-objective firefly algorithm for RFID network planning with uncertainty, Appl. Soft Comput., 55, 1, 549-564 (2017)
[31] Liu, J.; Wu, C.; Cao, J.; Wang, X.; Teo, K. L., A binary differential search algorithm for the 0c1 multidimensional knapsack problem, Appl. Math. Model., 40, 23, 9788-9805 (2016) · Zbl 1443.90047
[32] Uymaz, S. A.; Tezel, G.; Yel, E., Artificial algae algorithm (AAA) for nonlinear global optimization, Appl. Soft Comput., 31, 153-171 (2015)
[33] Zhang, X. D.; Wu, C. Z.; Li, J.; Wang, X. Y., Binary artificial algae algorithm for multidimensional knapsack problems, Appl. Soft Comput., 43, 583-595 (2016)
[34] Akinci, B.; Fischer, M.; Kunz, J.; Levitt, R., Representing work spaces generically in construction method models, J. Constr. Eng. Manag., 128, 4, 296-305 (2002)
[35] Charnes, A.; Cooper, W. W., Chance-constrained programming, Manag. Sci., 6, 1, 73-79 (1959) · Zbl 0995.90600
[36] Ke, H.; Liu, B., Project scheduling problem with stochastic activity duration times, Appl. Math. Comput., 168, 1, 342-353 (2005) · Zbl 1076.94044
[37] Wang, L.; Fang, C., An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem, Comput. Oper. Res., 39, 2, 449-460 (2012)
[38] Luedtke, J.; Ahmed, S., A sample approximation approach for optimization with probabilistic constraints, SIAM J. Optim., 19, 2, 674-699 (2008) · Zbl 1177.90301
[39] Marichelvam, M. K.; Prabaharan, T.; Yang, X. S., A discrete firefly algorithm for the multiobjective hybrid flowshop scheduling problems, IEEE Trans. Evol. Comput., 18, 2, 301-305 (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.