Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Islamic Azad University, Firoozkooh Branch, Firoozkooh, Iran.

2 Department of Industrial Engineering, Islamic Azad University, Tehran Markaz Branch,Tehran, Iran.

3 Department of Management, Shahid Beheshti University, Tehran, Iran.

Abstract

Nowadays the Resource Constrained Project Scheduling Problem (RCPSP) has triggered a substantially significant issue among scheduling problems. The purpose of RCPSP is minimizing the duration of the projects due to both limited available resources and precedence constraints. Indeed, it attempts to consume the total resources by finding the best duration for each activity. This paper proposes a new multi-objective mathematical model for multi-mode RCPSP with interruption to minimize the completion time of the project, maximize the Net Present Value (NPV) of the project, and minimize the allocating workforce’s costs to perform required skills of all activities. To solve the proposed model, an efficient method based on Me measure is used to cope with the uncertainties, and TH method is utilized to convert the multi-objective method into the single one. Furthermore, this paper presents a novel hybrid meta-heuristic algorithm based on Imperialist Competitive Algorithms (ICA) named Self-Adaptive Imperialist Competitive Algorithm (SAICA) to solve the mathematical model which has never been used to solve this type of problems before. Also, to evaluate the proposed method, its performance is investigated against some meta-heuristic algorithms: Differential Evolution (DE) and Imperialist Competitive Algorithm (ICA). Then, a numerical example, two case studies and a real case study have been carried out to embody both validity and efficiency of the presented approach. The obtained results embody that the proposed SAICA is more effective and practical in comparison with DE, ICA, and BCO in decreasing the project duration and also, the considerable effect on solutions confirms the quality of the proposed method. 

Keywords

Main Subjects

[1]      Brucker, P., Drexl, A., Möhring, R., Neumann, K., & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European journal of operational research112(1), 3-41.
[2]      Kolisch, R., & Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European journal of operational research174(1), 23-37.
[3]      Hartmann, S., & Kolisch, R. (2000). Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European journal of operational research127(2), 394-407.
[4]      Petrović, R. (1968). Optimization of resource allocation in project planning. Operations research16(3), 559-568.
[5]      Demeulemeester, E. L., & Herroelen, W. S. (1997). New benchmark results for the resource-constrained project scheduling problem. Management science43(11), 1485-1492.
[6]      Brucker, P., Knust, S., Schoo, A., & Thiele, O. (1998). A branch and bound algorithm for the resource-constrained project scheduling problem1. European journal of operational research107(2), 272-288.
[7]      Mingozzi, A., Maniezzo, V., Ricciardelli, S., & Bianco, L. (1998). An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Management science, 44(5), 714–729.
[8]      Klein, R., & Scholl, A. (1999). Progress: Optimally solving the generalized resource constrained project scheduling problem. Mathematical methods of operations research, 52(3), 467–488.
[9]      Blazewicz, J., Lenstra, J. K., & Kan, A. R. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete applied mathematics, 5(1), 11-24.
[10]  Kolisch, R., & Hartmann, S. (1999). Heuristic algorithms for solving the resource constrained project scheduling problem: Classification and computational analysis. In J. Weglarz (Ed.), Project scheduling, recent models, algorithms and applications (pp. 147– 178). Boston: Kluwer Academic.
[11]  Ballestín, F., Barrios, A., & Valls, V. (2011). An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags. Journal of scheduling14(4), 391-406.
[12]  Kima, K. W., Gen, M., Yamazaki, G. (2003). Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling. Applied soft computing, 2(3), 174–188.
[13]  Cervantes, M., Lova, A., Tormos, P., Barber, F. (2008). A dynamic population steady-state genetic algorithm for the resource-constrained project scheduling problem. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer.
[14]  Goncalves, J. F., Mendes, J. J. M., Resende, M. G. C. (2008). A genetic algorithm for the resource constrained multi-project scheduling problem. European journal of operational research,189(3), 1171–1190.
[15]  Mendes, J. J. D. M., Gonçalves, J. F., & Resende, M. G. (2009). A random key based genetic algorithm for the resource constrained project scheduling problem. Computers & operations research36(1), 92-109.
[16]  Valls, V., Ballestin, F., & Quintanilla, S. (2008). A hybrid genetic algorithm for the resource-constrained project scheduling problem. European journal of operational research185(2), 495-508.
[17]  Zamani, R. (2013). A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem. European journal of operational research229(2), 552-559.
[18]  Bouleimen, K. L. E. I. N., & Lecocq, H. O. U. S. N. I. (2003). A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European journal of operational research149(2), 268-281.
[19]  Boctor, F.F., (1996). Resource-constrained project scheduling by simulated annealing.
International journal of production research, 34(8), 2335–2351.
[20]  Valls, V., Quintanilla, S., & Ballestı́n, F. (2003). Resource-constrained project scheduling: A critical activity reordering heuristic. European journal of operational research149(2), 282-301.
[21]  Glover, F. (1989). Tabu search—part I. ORSA journal on computing1(3), 190-206.
[22]  Thomas, P. R., & Salhi, S. (1998). A tabu search approach for the resource constrained project scheduling problem. Journal of heuristics4(2), 123-139.
[23]  Merkle, D., Middendorf, M., & Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling. IEEE transactions on evolutionary computation6(4), 333-346.
[24]  Luo, S., Wang, C., & Wang, J. (2003, November). Ant colony optimization for resource-constrained project scheduling with generalized precedence relations. , 2003. Proceedings of 15th IEEE international conference on tools with artificial intelligence (pp. 284-289). IEEE.
[25]  Zhang, H., Li, X., Li, H., & Huang, F. (2005). Particle swarm optimization-based schemes for resource-constrained project scheduling. Automation in construction14(3), 393-404.
[26]  Zhang, H., Li, H., & Tam, C. M. (2006). Particle swarm optimization for resource-constrained project scheduling. International journal of project management24(1), 83-92.
[27]  Luo, X., Wang, D., Tang, J., & Tu, Y. (2006, June). An improved pso algorithm for resource-constrained project scheduling problem. 2006 6th world congress on intelligent control and automation (pp. 3514-3518). Dalian, China: IEEE.
[28]  Amiri, M., & Barbin, J. P. (2015). New approach for solving software project scheduling problem using differential evolution algorithm. International journal in foundations of computer science & technology (IJFCST)5(1).
[29]  Storn, R., & Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization11(4), 341-359.
[30]  Damak, N., Jarboui, B., Siarry, P., & Loukil, T. (2009). Differential evolution for solving multi-mode resource-constrained project scheduling problems. Computers & operations research36(9), 2653-2659.
[31]  Rahimi, A., Karimi, H., & Afshar-Nadjafi, B. (2013). Using meta-heuristics for project scheduling under mode identity constraints. Applied soft computing13(4), 2124-2135.
[32]  Jarboui, B., Damak, N., Siarry, P., & Rebai, A. (2008). A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied mathematics and computation195(1), 299-308.
[33]  Akeshteh, Z., & Mardukhi, F. (2017). An imperialist competitive algorithm for resource constrained project scheduling with activities flotation. IJCSNS17(5), 125.
[34]  Panahi, I., & Nahavandi, N. (2017). An efficient imperialist competitive algorithm for resource constrained project scheduling problem. Journal of industrial engineering, 51(2), 161-174.
[35]  Namazi, S., Fard, M. R. Z., Mousavi, S. M. R., & Nasab, M. B. (2014). Solving multi-mode resource constrained project scheduling with IC algorithm and compare it with pso algorithm. Advances in life sciences4(3), 140-145.
[36]  Wang, X., & Huang, W. (2010). Fuzzy resource-constrained project scheduling problem for software development. Wuhan university journal of natural sciences15(1), 25-30.
[37]  Maghsoudlou, H., Afshar-Nadjafi, B., & Niaki, S. T. A. (2016). A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem. Computers & chemical engineering88, 157-169.
[38]  Mendes, J. J. D. M., Gonçalves, J. F., & Resende, M. G. (2009). A random key based genetic algorithm for the resource constrained project scheduling problem. Computers & operations research36(1), 92-109.
[39]  Ulusoy, G., & Cebelli, S. (2000). An equitable approach to the payment scheduling problem in project management. European journal of operational research127(2), 262-278.
[40]  Torabi, S. A., & Hassini, E. (2008). An interactive possibilistic programming approach for multiple objective supply chain master planning. Fuzzy sets and systems, 159(2), 193-214.
[41]  Rabbani, M., Zhalechian, M., & Farshbaf‐Geranmayeh, A. (2016). A robust possibilistic programming approach to multiperiod hospital evacuation planning problem under uncertainty. International transactions in operational research, 25(1), 157-189.
[42]  Xu, J., & Zhou, X. (2013). Approximation based fuzzy multi-objective models with expected objectives and chance constraints: Application to earth-rock work allocation. Information sciences, 238, 75-95.
[43]  Dubois, D., & Prade, H. (2012). Possibility theory. Computational complexity (pp. 2240-2252). New York, NY: Springer.
[44]  Zahiri, B., Tavakkoli-Moghaddam, R., Mohammadi, M., & Jula, P. (2014). Multi-objective design of an organ transplant network under uncertainty. Transportation research part E: Logistics and transportation review72, 101-124.
[45]  Mohammadi, M., Torabi, S. A., & Tavakkoli-Moghaddam, R. (2014). Sustainable hub location under mixed uncertainty. Transportation research part E: Logistics and transportation review62, 89-115.
[46]  Storn, R., & Price, K. (1996, May). Minimizing the real functions of the ICEC'96 contest by differential evolution. Proceedings of IEEE international conference on evolutionary computation (pp. 842-844). IEEE.
[47]  Eshraghi, A. (2016). A new approach for solving resource constrained project scheduling problems using differential evolution algorithm. International journal of industrial engineering computations7(2), 205-216.
[48]  Lucic, P., & Teodorovic, D. (2001). Bee system: modeling combinatorial optimization transportation engineering problems by swarm intelligence. Preprints of the TRISTAN IV triennial symposium on transportation analysis (pp. 441-445). Sao Miguel, Azores Islands, Portugal.
[49]  Lucić, P., Teodorovic, D. (2002). Transportation modeling: an artificial life approach. Proceedings of the 14th IEEE international conference on tools with artificial intelligence (216-223). Washington, DC.
[50]  Lučić, P., & Teodorović, D. (2003). Computing with bees: Attacking complex transportation engineering problems. International journal on artificial intelligence tools12(03), 375-394.
[51]  Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: An algorithm for optimization inspired by imperialist competitive.  2007 IEEE congress on evolutionary computation. Singapore, Singapore: IEEE.
[52]  Ardalan, Z., Karimi, S., Poursabzi, O., & Naderi, B. (2015). A novel imperialist competitive algorithm for generalized traveling salesman problems. Applied soft computing, 26, 546-555.
[53]  Afruzi, E. N., Najafi, A. A., Roghanian, E., & Mazinani, M. (2014). A multi-objective imperialist competitive algorithm for solving discrete time, cost and quality trade-off problems with mode-identity and resource-constrained situations. Computers & operations research50, 80-96.
[54]  Sivanandam, S. N., & Deepa, S. N. (2008). Genetic algorithm optimization problems. Introduction to genetic algorithms (pp. 165-209). Berlin, Heidelberg: Springer. 
[55]  Mohammadi, M., Tavakkoli-Moghaddam, R., Siadat, A., & Dantan, J. Y. (2016). Design of a reliable logistics network with hub disruption under uncertainty. Applied mathematical modelling40(9-10), 5621-5642.
[56]  Wu, L., Wang, Y., & Zhou, S. (2010). Improved differential evolution algorithm for resource-constrained project scheduling problem. Journal of systems engineering and electronics21(5), 798-805.
[57]  Jun, D. H., & El-Rayes, K. (2009). Multi-objective optimization of resource scheduling in construction projects. Building a sustainable future (pp. 806-815). Seattle, Washington, United States.
[58]  Chen, P. H., & Weng, H. (2009). A two-phase GA model for resource-constrained project scheduling. Automation in construction18(4), 485-498.
[59]  Yang, K. K., Tay, L. C., & Sum, C. C. (1995). A comparison of stochastic scheduling rules for maximizing project net present value. European journal of operational research85(2), 327-339.