nach oben

Soft Computing

Erschienen in:

24.08.2021 | Optimization

A resource flow-based branch-and-bound algorithm to solve fuzzy stochastic resource-constrained project scheduling problem

verfasst von: Yaghoub Alipouri

Erschienen in: Soft Computing | Ausgabe 22/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, a resource flow-based branch-and-bound procedure is designed to solve the well-known resource-constrained project scheduling problem under the mixed uncertainty of fuzziness and randomness (FS-RCPSP). The objective is to minimize the expected makespan of the project subject to precedence and resource constraints. The proposed branch-and-bound can be employed to obtain optimal solutions and also can be truncated in order to find promising near optimal solutions. The depth-first strategy is utilized for constructing the search tree, and earliest start time (EST) concept is adopted for selecting a node for further branching while traversing the tree down to the leaves. The performance of developed branch-and-bound is benchmarked against CPLEX and SADESP across an extensive set of 960 problems. The results returned by the proposed algorithm show experimentally its effectiveness to solve the FS-RCPSP.

Vorheriger Artikel Adaptive opposition slime mould algorithm

Nächster Artikel Rubber bushing optimization by using a novel chaotic krill herd optimization algorithm

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Alcaraz J, Maroto C (2001) A robust genetic algorithm for resource allocation in project scheduling. Ann Oper Res 102:83–109. https://doi.org/10.1023/A:1010949931021MathSciNetCrossRefMATH

Alipouri Y, Sebt MH, Ardeshir A, FazelZarandi MH (2017) A mixed-integer linear programming model for solving fuzzy stochastic resource constrained project scheduling problem. Oper Res Int J 20:197–217. https://doi.org/10.1007/s12351-017-0321-xCrossRef

Alipouri Y, Sebt MH, Ardeshir A, Chan WT (2019) Solving the FS-RCPSP with hyper-heuristics: a policy-driven approach. J Oper Res Soc 70(3):403–419. https://doi.org/10.1080/01605682.2018.1441636CrossRef

Altintas C, Azizoglu M (2020) A branch and bound algorithm for a multi-mode project scheduling problem with a single non-renewable resource. Int J Inf Tech Proj Manag (IJITPM) 11(2):1–14. https://doi.org/10.4018/IJITPM.2020040101CrossRef

Artigues C, Michelon P, Reusser S (2003) Insertion techniques for static and dynamic resource-constrained project scheduling. Eur J Oper Res 149(2):249–267. https://doi.org/10.1016/S0377-2217(02)00758-0MathSciNetCrossRefMATH

Artigues C, Leus R, TallaNobibon F (2013) Robust optimization for resource-constrained project scheduling with uncertain activity durations. Flex Serv Manuf J 25(1):175–205. https://doi.org/10.1007/s10696-012-9147-2CrossRef

Ashtiani B, Leus R, Aryanezhad MB (2011) New competitive results for the stochastic resource-constrained project scheduling problem: exploring the benefits of pre-processing. J Sched 4(2):157–171. https://doi.org/10.1007/s10951-009-0143-7MathSciNetCrossRefMATH

Atli O, Kahraman C (2012) Fuzzy resource-constrained project scheduling using taboo search algorithm. Int J Intell Syst 27(10):873–907. https://doi.org/10.1002/int.21552CrossRef

Atli O, Kahraman C (2013) The MinSlack and Kangaroo algorithm heuristic for fuzzy resource-constrained project scheduling problems. J Mult Valued Logic Soft Comput 20(1–2):189–219MathSciNet

Brucker P, Knust S, Schoo A, Thiele O (1998) A branch and bound algorithm for the resource-constrained project scheduling problem. Eur J Oper Res 107(2):272–288. https://doi.org/10.1016/S0377-2217(97)00335-4CrossRefMATH

Bruni ME, Di Puglia PL, Beraldi P, Guerriero F (2017) An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations. Omega 71:66–84. https://doi.org/10.1016/j.omega.2016.09.009CrossRef

Buckley JJ (2005) Fuzzy probability: new approach and applications. Stud Fuzziness Soft Comput Ser. https://doi.org/10.1007/3-540-32388-0CrossRefMATH

Buckley JJ, Feuring T (2000) Evolutionary algorithm solution to fuzzy problems: fuzzy linear programming. Fuzzy Set Sys 109(1):35–53. https://doi.org/10.1016/S0165-0114(98)00022-0MathSciNetCrossRefMATH

Chen L, Zhang Z (2016) Preemption resource-constrained project scheduling problems with fuzzy random duration and resource availabilities. J Ind Prod Eng 33(6):373–382. https://doi.org/10.1080/21681015.2016.1140089CrossRef

Damay J, Quilliot A, Sanlaville E (2007) Linear programming based algorithms for preemptive and non-preemptive RCPSP. Eur J Oper Res 182(3):1012–1022. https://doi.org/10.1016/j.ejor.2006.09.052CrossRefMATH

Davari M, Demeulemeester E (2018) A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem. Int J Prod Res 57(4):1265–1282. https://doi.org/10.1080/00207543.2018.1504245CrossRef

Demeulemeester EL, Herroelen WS (2002) Project scheduling: a research handbook. International series in operations research and management science vol 49, Kluwer Academic Publishers (now Springer). https://doi.org/10.1007/b101924

Dorndorf U, Pesch E, Phan-Huy T (2000) A branch-and-bound algorithm for the resource-constrained project scheduling problem. Math Method Oper Res 52:413–439. https://doi.org/10.1007/s001860000091MathSciNetCrossRefMATH

Fang C, Kolisch R, Wang L, Chundi M (2015) An estimation of distribution algorithm and new computational results for stochastic resource-constrained project scheduling problem. Flex Serv Manuf J 27:585–605. https://doi.org/10.1007/s10696-015-9210-xCrossRef

Herroelen W, Leus R (2005) Project scheduling under uncertainty: survey and research potentials. Eur J Oper Res 165(2):289–306. https://doi.org/10.1016/j.ejor.2004.04.002CrossRefMATH

Hirota K (1981) Concepts of probabilistic sets. Fuzzy Set Syst 5(1):31–46. https://doi.org/10.1016/0165-0114(81)90032-4MathSciNetCrossRefMATH

Huang W, Ding L, Wen B, Cao B (2009) Project scheduling problem for software development with random fuzzy activity duration times. In: Yu W, He H, Zhang N (eds) Advances in neural networks – ISNN 2009. ISNN 2009. Lecture Notes in Computer Science, vol 5552. Springer, Berlin. https://doi.org/10.1007/978-3-642-01510-6_8

Itoh T, Ishii H (2005) One machine scheduling problem with fuzzy random due-dates. Fuzzy Optim Decis Making 4:71–78. https://doi.org/10.1007/s10700-004-5571-4MathSciNetCrossRefMATH

Ke H, Liu B (2007) Project scheduling problem with mixed uncertainty of randomness and fuzziness. Eur J Oper Res 183(1):135–147. https://doi.org/10.1016/j.ejor.2006.09.055CrossRefMATH

Kolisch R, Sprecher A, Drexl A (1995) Characterization and generation of a general class of resource-constrained project scheduling problems. Manag Sci 41:1693–1703. https://doi.org/10.1287/mnsc.41.10.1693CrossRefMATH

Kruse R, Meyer KD (1987) Statistics with vague data. Part of the theory and decision library book series (TDLB, volume 6). https://doi.org/10.1007/978-94-009-3943-1

Kumar N, Vidyarthi DP (2016) A model for resource-constrained project scheduling using adaptive PSO. Soft Comput 20:1565–1580. https://doi.org/10.1007/s00500-015-1606-8CrossRef

Lambrechts O, Demeulemeester E, Herroelen W (2008) Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities. J Sched 11:121–136. https://doi.org/10.1007/s10951-007-0021-0MathSciNetCrossRefMATH

Lawler EL (1976) Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston, New YorkMATH

Leus R, Herroelen W (2004) Stability and resource allocation in project planning. IIE Trans 36(7):667–682. https://doi.org/10.1080/07408170490447348CrossRef

Liu B (2002a) Theory and practice of uncertainty programming. Part of the studies in fuzziness and soft computing book series (STUDFUZZ, volume 102). Physica-Verlag, Heidelberg. https://doi.org/10.1007/978-3-7908-1781-2

Liu B (2002b) Random fuzzy dependent-chance programming and its hybrid intelligent algorithm. Inform Sci 141(3–4):259–271. https://doi.org/10.1016/S0020-0255(02)00176-7CrossRefMATH

Mahdi Mobini MD, Rabbani M, Amalnik MS et al (2009) Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem. Soft Comput 13:597–610. https://doi.org/10.1007/s00500-008-0337-5CrossRef

Nematian J, Eshghi K, Eshragh-Jahromi A (2010) A resource-constrained project scheduling problem with fuzzy random duration. J Uncertain Syst 4(2):123–132

Pantouvakis JP, Manoliadis OG (2006) A practical approach to resource-constrained project scheduling. Oper Res Int J 6(3):299–309. https://doi.org/10.1007/BF02941258CrossRef

Puri ML, Ralescu DA (1986) Fuzzy random variables. J Math Anal Appl 114(2):409–422. https://doi.org/10.1016/0022-247X(86)90093-4MathSciNetCrossRefMATH

Rostami S, Creemers S, Leus R (2018) New strategies for stochastic resource-constrained project scheduling. J Sched 21(3):349–365. https://doi.org/10.1007/s10951-016-0505-xMathSciNetCrossRefMATH

Sadeh N, Otsuka S, Schelback R (1993) Predictive and reactive scheduling with the microboss production scheduling and control system. In: Proceedings of the IJCAI-93. workshop on knowledge-based production planning, scheduling and control, pp 293–306

Sheng B, Wang H, Xiao Z et al (2019) A novel heuristic algorithm with activity back-shift response model for resource-constrained project scheduling problem. Soft Comput 23:7805–7819. https://doi.org/10.1007/s00500-018-3410-8CrossRef

Sebt MH, Alipouri Y, Alipouri Y (2013) Solving resource-constrained project scheduling problem with evolutionary programming. J Oper Res Soc 64:1327–1335. https://doi.org/10.1057/jors.2012.69CrossRef

Sprecher A, Drexl A (1998) Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. Eur J Oper Res 107(2):431–450. https://doi.org/10.1016/S0377-2217(97)00348-2CrossRefMATH

Sprecher A, Hartmann S, Drexl A (1997) An exact algorithm for project scheduling with multiple modes. Or Spectrum 19(3):195–203. https://doi.org/10.1007/BF01545587MathSciNetCrossRefMATH

Van de Vonder S, Demeulemeester E, Herroelen W (2007) A classification of predictive-reactive project scheduling procedures. J Sched 10:195–207. https://doi.org/10.1007/s10951-007-0011-2MathSciNetCrossRefMATH

Xu J, Zhang Z (2012) A fuzzy random resource-constrained scheduling model with multiple projects and its application to a working procedure in a large-scale water conservancy and hydropower construction project. J Sched 15:253–272. https://doi.org/10.1007/s10951-010-0173-1MathSciNetCrossRefMATH

Ying KC, Lin SW, Lee ZJ (2009) Hybrid-directional planning: improving improvement heuristics for scheduling resource-constrained projects. Int J Adv Manuf Tech 41(3):358–366. https://doi.org/10.1007/s00170-008-1486-5CrossRef

Zadeh LA (1968) Probability measures of fuzzy events. J Math Anal Appl 23:421–427MathSciNetCrossRef

Zamani R (2011) A hybrid decomposition procedure for scheduling projects under multiple resource constraints. Oper Res Int J 11:93–111. https://doi.org/10.1007/s12351-009-0073-3CrossRef

Zhu Y, Liu B (2005) Some Inequalities of random fuzzy variables with application to moment convergence. Comput Math Appl 50(5–6):719–727. https://doi.org/10.1016/j.camwa.2005.04.015MathSciNetCrossRefMATH

Zoulfaghari H, Nematian J, KananiNezhad AA (2016) A resource-constrained project scheduling problem with fuzzy activity times. Int J Fuzzy Syst Appl (IJFSA) 5(4):1–15. https://doi.org/10.4018/IJFSA.2016100101CrossRef

Titel: A resource flow-based branch-and-bound algorithm to solve fuzzy stochastic resource-constrained project scheduling problem
verfasst von: Yaghoub Alipouri
Publikationsdatum: 24.08.2021
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 22/2021
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-021-06147-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 22/2021

Generalized support vector machines (GSVMs) model for real-world time series forecasting

A new hybrid multi-level cross-entropy-based moth-flame optimization algorithm

A remark on the maximum entropy principle in uncertainty theory

Bilevel-search particle swarm optimization for computationally expensive optimization problems

Multiple attribute decision-making based on different types of Dombi aggregation operators under Fermatean fuzzy information

Circle-based Group Recommendation in Social Networks

Premium Partner