×

Evolutionary algorithms for multi-objective stochastic resource availability cost problem. (English) Zbl 07319766

Summary: This paper investigates the resource availability cost problem in a PERT-type network, where both activities duration and resource requirement are considered as stochastic parameters. The problem has two objective functions in which the first one, namely the project’s makespan, is to minimize the project’s duration. However, the second one tries to minimize the total cost of resources. Since its NP-hardness is proven in a strong sense, four well-known evolutionary algorithms including strength pareto evolution algorithm II, non-dominated sorting genetic algorithm II, multi-objective particle swarm optimization, and pareto envelope-based selection algorithm II are proposed to solve the problem. Furthermore, to enhance the algorithms’ performance, some efficient mutation and crossover operators, as well as two novel operators called local search and movement, are employed to solution structure for producing new generations. Also, in order to tackle uncertainty, Monte-carlo simulation is utilized. In order to tune the effective parameters, the Taguchi method is used. The performance of our proposed algorithms is evaluated by numerical test problems in different size which generated based on PSPLIB benchmark problems. Finally, to assess the relative performance of the four proposed algorithms, six well-known performance criteria are employed. Using relative percentage deviation and TOPSIS approach, the performance of algorithms is elucidated.

MSC:

90Bxx Operations research and management science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arjmand, M.; Najafi, AA, Solving a multi-mode bi-objective resource investment problem using meta-heuristic algorithms, Adv. Comput. Tech. Electromagn., 1, 2015, 1-18 (2015)
[2] Baradaran, S.; Fatemi-Ghomi, SMT, A hybrid heuristic rule for constrained resource allocation in PERT type networks, World Appl. Sci. J., 7, 10, 1324-1330 (2009)
[3] Baradaran, S.; Fatemi-Ghomi, SMT; Mobini, M.; Hashemin, SS, A hybrid scatter search approach for resource-constrained project scheduling problem in PERT-type networks, Adv. Eng. Softw., 41, 966-975 (2010)
[4] Baradaran, S.; Fatemi-Ghomi, SMT, Multi-mode renewable resource-constrained allocation in PERT networks, Appl. Soft Comput., 12, 2012, 82-90 (2012)
[5] Beg, I.; Rashid, T., Multi-criteria trapezoidal valued intuitionistic fuzzy decision making with Choquet integral based TOPSIS, Opsearch, 51, 1, 98-129 (2013) · Zbl 1337.90087
[6] Blazewicz, J.; Lenstra, JK; Rinnooy Kan, AHH, Scheduling subject to resource constraints, Discrete Appl Math, 5, 11-24 (1983) · Zbl 0516.68037
[7] Charnes, A.; Cooper, W.; Thompson, G., Critical path analysis via chance constrained and stochastic programming, Oper. Res., 12, 460-470 (1964) · Zbl 0125.09602
[8] Chen, Z.; Demeulemeester, E.; Bai, S.; Guo, Y., Efficient priority rules for the stochastic resource-constrained project scheduling problem, Eur. J. Oper. Res., 270, 3, 957-967 (2018) · Zbl 1403.90383
[9] Cochran, WG; Cox, GM, Experimental Designs (1992), New York: Wiley, New York · Zbl 0850.62005
[10] Coello-Coello, CA; Van Veldhuizen, DA; Lamont, GB, Evolutionary Algorithms for Solving Multi-Objective Problems (2002), Berlin: Kluwer Academic Publishers, Berlin · Zbl 1130.90002
[11] Corne, D.W., Joshua, N.J., Knowles, D., Oates, M. J.: Region-based selection in evolutionary multi-objective optimization (2003)
[12] Creemers, S., The preemptive stochastic resource-constrained project scheduling problem, Eur. J. Oper. Res., 277, 1, 238-247 (2019) · Zbl 1430.90299
[13] Deb, K., Multi-objective Optimization Using Evolutionary Algorithms (2001), Chichester: Wiley, Chichester · Zbl 0970.90091
[14] Demeulemeester, E., Minimizing resource availability costs in time-limited project networks, Manag. Sci., 41, 1590-1598 (1995) · Zbl 0861.90071
[15] Demeulemeester, EL; Herroelen, W., Project Scheduling: A Research Handbook (2002), Boston: Kluwer Academic Publishers, Boston · Zbl 1059.90068
[16] Drexl, A.; Kimms, A., Optimization guided lower and upper bounds for the resource investment problem, J. Oper, Res. Soc, 52, 340-351 (2001) · Zbl 1131.90378
[17] Elmaghraby, S., On the expected duration of PERT type networks, Manag. Sci., 13, 299-306 (1967) · Zbl 0158.38303
[18] Elmaghraby, SE, Activity nets: a guided tour through some recent developments, Eur. J. Oper. Res., 13, 64, 199-215 (1995) · Zbl 0910.90175
[19] Fatemi Ghomi, SMT; Hashemin, SS, A New Analytical Algorithm and Generation of Gaussian Quadrature Formula for Stochastic Network, Eur. J. Oper. Res., 114, 610-625 (1999) · Zbl 0949.90012
[20] Freeman, RJ, A generalized PERT, Oper. Res., 8, 281-293 (1960)
[21] Golenko-Ginzburg, D.; Gonik, A., Stochastic Network Project Scheduling with Non-consumable Limited Resources, Int. J. Prod. Econ., 48, 29-37 (1997)
[22] Goto, H., Forward-compatible framework with critical-chain project management using a max-plus linear representation, OPSEARCH, 54, 1, 201-216 (2016) · Zbl 1375.90150
[23] Hartmann, S.; Briskorn, D., A survey of variants and extensions of the resource constrained project scheduling problem, Eur. J. Oper. Res., 207, 1-14 (2010) · Zbl 1205.90123
[24] Herroelen, W.; De Reyck, B.; Demeulemeester, EL, Resource-constrained project scheduling: a survey of recent developments, Comput. Oper. Res., 25, 279-302 (1999) · Zbl 1040.90525
[25] Hwang, CL; Yoon, K., Multiple Attribute Decision Making (1981), Berlin: Springer, Berlin · Zbl 0453.90002
[26] Icmeli, O.; Erenguç, SS; Zappe, CJ, Project scheduling problems: a survey, Int. J. Oper. Prod. Manag., 13, 80-91 (1993)
[27] Khalilzadeh, M.; Shakeri, H.; Gholami, H.; Amini, L., A heuristic algorithm for project scheduling with fuzzyparameters, Proc. Comput. Sci., 121, 2017, 63-71 (2017)
[28] Ke, H.; Liu, B., Project scheduling problem with stochastic activity duration times, Appl. Math. Comput., 168, 1, 342-353 (2005) · Zbl 1076.94044
[29] 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
[30] Kelley, JE; Muth, J.; Thompson, G., The critical-path method: resources planning and scheduling, Industrial Scheduling, 347-365 (1963), Upper Saddle River, NJ: Prentice-Hall, Upper Saddle River, NJ
[31] Kolisch, R.; Hartmann, S., Experimental investigation of heuristics for resource constrained project scheduling: an update, Eur. J. Oper. Res., 174, 23-37 (2006) · Zbl 1116.90047
[32] Kolisch, R.; Hartmann, S.; Weglarz, J., Heuristic algorithms for solving the resource constrained project scheduling problem: classification and computational analysis, Project Scheduling: Recent Models, Algorithms and Applications, 147-178 (1998), Boston: Kluwer Academic Publishers, Boston
[33] Kolisch, R., Padman, R.: An integrated survey of project scheduling. Technical Report 463, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universitat Kiel (1997)
[34] Kolisch, R., Serial and parallel resource-constrained project scheduling methods revisited: theory and computation, Eur. J. Oper. Res., 90, 320-333 (1996) · Zbl 0916.90151
[35] Kulkarni, V.; Adlakha, V., Markov and Markov-regenerative PERT networks, Oper. Res., 34, 769-781 (1986) · Zbl 0615.90042
[36] Lambrechts, O.; Demeulemeester, E.; Herroelen, W., Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities, J. Sched., 11, 2, 121-136 (2008) · Zbl 1168.90453
[37] Lambrechts, O.; Demeulemeester, E.; Herroelen, W., A tabu search procedure for developing robust predictive project schedules, Int. J. Prod. Econ., 111, 2, 493-508 (2008)
[38] Lambrechts, O.; Demeulemeester, E.; Herroelen, W., Time slack-based techniques for robust project scheduling subject to resource uncertainty, Ann. Oper. Res., 186, 1, 443-464 (2011) · Zbl 1225.90062
[39] Ma, Z.; Demeulemeester, E.; He, Z.; Wang, N., A computational experiment to explore better robustness measures for project scheduling under two types of uncertain environments, Comput. Ind. Eng., 131, 382-390 (2019)
[40] Martin, J., Distribution of the time through a directed acyclic network, Oper. Res., 13, 46-66 (1980) · Zbl 0137.39302
[41] Möhring, RF, Minimizing costs of resource requirements in project networks subject to a fixed completion time, Oper. Res., 32, 89-120 (1984) · Zbl 0531.90049
[42] Möhring, RH; Stork, F., Linear preselective policies for stochastic project scheduling, Math. Methods Oper. Res., 52, 501-515 (2000) · Zbl 1023.90033
[43] Mukherjee, S.; Basu, K., Solution of interval PERT/CPM network problems by a simplified tabular method, Opsearch, 48, 4, 355-370 (2011) · Zbl 1353.90031
[44] Nadjafi, B., Multi-mode resource availability cost problem with recruitment and release dates for resources, Appl. Math. Model., 38, 5347-5355 (2014) · Zbl 1428.90065
[45] Ning, M.; He, Z.; Wang, N., Metaheuristics for multi-mode cash flow balanced project scheduling with stochastic duration of activities, Autom. Constr., 81, 224-233 (2017)
[46] Nooramin, AS; Sayareh, J.; Moghadam, MK; Alizmini, HR, TOPSIS and AHP techniques for selecting the most efficient marine container yard gantry crane, Opsearch, 49, 2, 116-132 (2012) · Zbl 1256.90024
[47] Palmer, C., Kershenbaum, A.: Representing trees in genetic algorithms. In: Proceedings of the first IEEE International Conference on Evolutionary Computation, New York, pp. 376-84 (1994)
[48] Rahmati, SHA; Hajipour, V.; Niaki, STA, A softcomputing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem, Appl. Soft Comput., 13, 1728-1740 (2013)
[49] Rahmati, SHA; Zandieh, M.; Yazdani, M., Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem, Int. J. Adv. Manuf. Technol., 64, 915-932 (2012)
[50] Rangaswamy, M.: Multiple Resource Planning and Allocation in Resource-Constrained Project Networks, Ph.D. Thesis, Graduate School of Business, University of Colorado (1998)
[51] Ranjbar, M.; Kianfar, F.; Shadrokh, S., Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm, Appl. Math. Comput., 196, 879-888 (2008) · Zbl 1178.90161
[52] Rodrigues, S.; Yamashita, D., An exact algorithm for minimizing resource availability costs in project scheduling, Eur. J. Oper. Res., 206, 562-568 (2010) · Zbl 1188.90108
[53] Schott, J.R.: Fault tolerant design using single and multi-criteria genetic algorithms optimization. Master’s thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA (1995)
[54] Shadrokh, S.; Kianfar, F., A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty, Eur. J. Oper. Res., 181, 86-101 (2007) · Zbl 1121.90062
[55] Stork, F.: Branch-and-bound algorithms for stochastic resource-constrained project scheduling, Technical rep. 702-2000. Combinatorial optimization & graph algorithms group, Technische Universität Berlin (2000)
[56] Taguchi, G.: Introduction to Quality Engineering: Designing Quality into Products and Processes. Asian Productivity Organization, Tokyo (1986)
[57] Tao, S.; Dong, ZS, Scheduling resource-constrained project problem with alternative activity chains, Comput. Ind. Eng., 114, 2017, 288-296 (2017)
[58] Tao, S.; Wu, C.; Sheng, Z.; Wang, X., Stochastic project scheduling with hierarchical alternatives, Appl. Math. Model., 58, 181-202 (2017) · Zbl 1480.90150
[59] Tao, S.; Dong, ZS, Multi-mode resource-constrained project scheduling problem with alternative project structures, Comput. Ind. Eng., 125, 2018, 333-347 (2018)
[60] Tsai, YW; Gemmil, DD, Using tabu search to schedule activities of stochastic resource-constrained projects, Eur. J. Oper. Res., 111, 129-141 (1998) · Zbl 0948.90072
[61] Van Peteghem, V.; Vanhoucke, M., An artificial immune system algorithm for the resource availability cost problem, Flexible. Serv. Manuf. J., 1, 1 (2011) · doi:10.1007/s10696-011-9117-0
[62] Xuebin, L., Study of multi-objective optimization and multi-attribute decision making for economic and environmental power dispatch, Electr. Power Syst. Res., 79, 789-795 (2009)
[63] Yamashita, D.; Armentano, V.; Laguna, M., Scatter search for project scheduling with resource availability cost, Eur. J. Oper. Res., 169, 623-637 (2006) · Zbl 1079.90066
[64] Yellapu, G.; Penmestsa, SK, Modeling od a scheduling problem with expected availability of resources, Opsearch, 52, 4, 771-781 (2015) · Zbl 1365.90150
[65] Zitzler, E.: Evolutionary Algorithms for Multi-objective Optimization: Methods and Applications. PhD. Thesis, Dissertation ETH No. 13398, Swiss Federal Institute of Technology (ETH), Zürich, Switzerland (1999)
[66] Zitzler, E., Laumanns, M., Thiele, L.: Improving the Strength Pareto Evolutionary Algorithm, Computer Engineering and Network Laboratory (2001) · Zbl 1074.68065
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.