A Two-Part Self-Adaptive Technique in Genetic Algorithms for Project Scheduling Problems
Keywords:
Genetic Algorithm, Project Scheduling, Parameter Control, Self-AdaptiveAbstract
The present paper introduces a novel two-part self-adaptive technique in designing the genetic algorithm for project scheduling problems. One part of the algorithm includes a self-adaptive mechanism for genetic operators like crossover and mutation. The second part contains another self-adaptive mechanism for genetic parameters such as crossover probability. The parts come in turn repeatedly within a loop feeding each other with the information regarding the performance of operators or parameters. The capability of the method is tested and confirmed in comparison to metaheuristic and exact algorithms based on well-known benchmarks.
References
L. Demeulemeester, and W. Herrolen, Project Scheduling a Research Handbook. Kluwer Academic Publishers, Boston/Dordrecht/London, 2002.
R. Kolisch, and S. Hartmann, “Experimental investigation of heuristics for resource-constrained project scheduling: an update,” Euro. J. Oper. Res. vol. 174, pp. 23-37, 2006.
W. Chan, D. K. H. Chua, and G. Kannan, “Construction resource scheduling with genetic algorithms,” J. Const. Eng. Manage. vol. 122, pp. 125–132, 1996.
S. Hartmann, “A competitive genetic algorithm for resource-constrained project scheduling,” Nav. Res. Log. vol. 45, pp. 733–750, 1998.
T. Hegazy, “Optimization of resource allocation and leveling using genetic algorithms,” J. Const. Eng. Manage. vol. 125, pp. 167-175, 1999.
J. Alcaraz, and C. Maroto, “A robust genetic algorithm for resource allocation in project scheduling,” Ann. Oper. Res. vol. 102, pp. 83–109, 2001.
S. Hartmann, “A self-adapting genetic algorithm for project scheduling under resource constraints,” Nav. Res. Log. vol. 49, pp. 433–448, 2002.
K. S. Hindi, H. Yang, and K. Fleszar, “An evolutionary algorithm for resource-constrained project scheduling,” IEEE T. Evolut. Comput. vol. 6, pp. 512–518, 2002.
Y. C. Toklu, “Application of genetic algorithms to construction scheduling with or without resource constraints,” Can. J. Civ. Eng. vol. 29, pp. 421–429, 2002.
A. Senouci, and N. Eldin, “Use of genetic algorithms in resource scheduling of construction projects,” J. Const. Eng. Manage. vol. 130, pp. 869-877, 2004.
A. A. Najafi, and S. T. A. Niaki, “A genetic algorithm for resource investment problem with discounted cash flows,” Appl. Math. Comput. vol. 183, pp. 1057–70, 2006.
S. Shadrokh, and F. Kianfar, “A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty,” Euro. J. Oper. Res. vol. 181, pp. 86–101, 2007.
J. Mendes, J. Goncalves, and M. Resende, “A random key based genetic algorithm for the resource–constrained project scheduling problem,” Comput. Oper. Res. vol. 36, pp. 92-109, 2009.
A. A. Najafi, S. T. A. Niaki, and M. Shahsavar, “A parameter-tuned genetic algorithm for resource investment problem with discounted cash flows and generalized precedence relations,” Comput. Oper. Res. vol. 36, pp. 2994-3001, 2009.
M. Shahsavar, S. T. A. Niaki, and A. A. Najafi, “An efficient genetic algorithm to maximize net present value of project payments under inflation and bonus-penalty policy in resource investment problem,” Adv. Eng. Softw. vol. 41, pp. 1023-1030, 2010.
B. Afshar-Nadjafi, and M. Arani, “Multimode preemptive resource investment problem subject to due dates for activities: formulation and solution procedure,” Advances in Operations Research. 2014, doi:10.1155/2014/740670.
M. Arjmand, and A. A. Najafi, “Solving a multimode biobjective resource investment problem using metaheuristic algorithms,” Advanced Computational Techniques in Electromagnetics. vol. 2015(1), pp. 41-58.
J. Holland, Adaptation in Natural and Artificial Systems. University of Michigan Press, Boston, 1975.
H. P. Schwefel, Numerical Optimization of Computer Models. John Wiley & Sons, New York, 1981.
K. A. De Jong and W. M. Spears, “An analysis of the interacting roles of population size and crossover in genetic algorithms,” in Proceeding of the first Workshop on Parallel Problems Solving from Nature, H. P. Schwefel and R Manner Eds. Springer-Verlag, London, 1990, pp 38-47.
T. P. Bagchi, and K. Deb, “Calibration of GA parameters: the design of experiments approach,” Computer Science and Informatics. vol. 26, pp. 45-56, 1996.
A. W. M. Ng, and B. J. C. Perera, “Selection of genetic algorithm operators for river water quality model calibration,” Eng. Appl. Artif. Intell. vol. 16, pp. 529–541, 2003.
A. Czarn, C. MacNish, K. Vijayan, B. A. Turlach, and R. Gupta, “Statistical exploratory analysis of genetic algorithms,” IEEE T. Evolut. Comput. vol. 8, pp. 405–421, 2004.
C. B. Costa, M. M. R. Wolf, and F. R. Maciel, “Factorial design technique applied to genetic algorithm parameters in a batch cooling crystallization optimization,” Comput. Chem. Eng. vol. 29, pp. 2229–2241, 2005.
B. Adenso-Diaz, and M. Laguna, “Fine-tuning of algorithms using fractional experimental designs and local Search,” Oper. Res. vol. 54, pp. 99-114, 2006.
R. Ruiz, and C. Maroto, “A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility,” Euro. J. Oper. Res. vol. 169, pp. 781-800, 2006.
R. Ruiz, C. Maroto, and J. Alcaraz, “Two new robust genetic algorithms for the flowshop scheduling problem,” Omega. vol. 34, pp. 461-476, 2006.
C. B. Costa, E. A. Ccopa-Rivera, M. C. A. F. Rezende, M. M. R. Wolf, and F. R. Maciel “Prior detection of genetic algorithm significant parameters: coupling factorial design technique to genetic algorithm,” Chemical Engineering Science. vol. 62, pp. 4780-4801, 2007.
F. G. Lobo, C. F. Lima, and Z. Michalewicz, Parameter Setting in Evolutionary Algorithms. Springer Velarg, Berlin, 2007.
M. Shahsavar, A. A. Najafi, and S. T. A. Niaki, “Statistical design of genetic algorithms for combinatorial optimization problems,” Math. Probl. Eng. vol. 2011(2), pp. 1-17, doi:10.1155/2011/872415.
A. E. Eiben, R. Hinterding, and Z. Michalewicz “Parameter control in evolutionary algorithms,” IEEE T. Evolut. Comput. vol. 3, pp. 124–141, 1999.
T. Back, “Optimal mutation rates in genetic search,” in Proceedings of the Fifth International Conference on Genetic Algorithms, S. Forrest, Ed. San Mateo, CA, Morgan Kaufmann, 1993, pp. 2-8.
B. A. Julstrom, “What have you done for me lately? adapting operator probabilities in a steady-state genetic algorithm,” in Proceedings of the Sixth International Conference on Genetic Algorithms, L. Eshleman Ed. San Mateo, CA, Morgan Kaufmann, 1995, pp. 81-87.
W. M. Spears, “Adapting crossover in evolutionary algorithms,” in Evolutionary Programming IV. Proceedings of the Fourth Annual Conference on Evolutionary Programming, J. Mcdonnell, R. Reynolds, D. Fogel, Eds. MIT Press, Cambridge, MA, 1995, pp 367-84.
J. Lis, “Parallel genetic algorithm with the dynamic control parameter,” in Proceedings of IEEE International Conference on Evolutionary Computation. Nagoya, Japan, 1996, pp 324–329.
J. J. Grefenstette, “Optimization of control parameters for genetic algorithms,” IEEE Trans. Syst. Man. Cybern. vol. 16, pp. 122-128, 1986.
Q. T. Pham, “Competitive evolution: a natural approach to operator selection,” in Progress in Evolutionary Computation. Lecture Notes in Artificial Intelligence, X. Yao Ed. Springer-Verlag, Heidelberg, 1995, pp 49-60.
C. Chunlei and F. Yanjun, “An adaptive mutation method for GA based on relative importance’” in Proceedings of the 2010 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE). Chengdu, China, 2010, pp. 111-113.
G. Chen, “Intelligent adaptive genetic algorithm and its application,” in Proceedings of the 2011 International Conference on Intelligent Computation Technology and Automation (ICICTA). 2011, pp. 163-166.
C. Jassadapakorn, and P. Chongstitvatana, “Self-adaption mechanism to control the diversity of the population in genetic algorithms,” International Journal of Computer Science & Information Technology. vol. 3(4), pp. 111-127, 2011.
B. Tessema and G. G. Yen, “A self adaptive penalty function based algorithm for constrained optimization,” in Evolutionary Computation, 2006. CEC 2006. IEEE Congress on , Vancouver, BC , 2006, pp. 246 – 253.
R. Perzina, and J. Ramik, “Timetabling problem with fuzzy constraints: a self-learning genetic algorithm,” International Journal of Engineering and Innovative Technology. vol. 3(4), pp. 105-113, 2013.
R. Perzina, and J. Ramik, “Self-learning genetic algorithm for timetabling problem with fuzzy constraints,” International Journal of Innovative Computing, Information and Control. vol. 9(11), pp. 1349-4198, 2013.
A. F. Ali, “Genetic local search algorithm with self-adaptive population resizing for solving global optimization problems. I.J. Information Engineering and Electronic Business. vol. 3, pp. 51-63, 2014.
F. Espinoza, B. S. Minsker, and D. Goldberg, “An adaptive hybrid genetic algorithm for groundwater remediation design. J. Water Resour. Plann. Manage. vol. 131(1), pp. 14–24, 2005.
F. Espinoza, and B. S. Minsker, “Development of the enhanced self-adaptive hybrid genetic algorithm (e-SAHGA),” Water Resourc. Res. vol. 42(8), 2006, doi:10.1029/2005WR004221.
T. E. Mihoub, L. Nolle, G. Schaefer, T. Nakashima, and A. Hopgood, “A self-adaptive hybrid genetic algorithm for color clustering,” in 2006 IEEE International Conference on Systems, Man, and Cybernetics, Taipei, Taiwan, 2006, pp. 3158-3163.
T. Lili, K. Xiangdong, Z. Weimin, and Q. Feng, “Modified self-adaptive immune genetic algorithm for optimization of combustion side reaction of p-Xylene oxidation. Chin. J. Chem. Eng. vol. 20(6), pp. 1047-1052, 2012.
Y. Liu, Y. Feng, and P. Gilmore Pontius Jr, “Spatially-explicit simulation of urban growth through self-adaptive genetic algorithm and cellular automata modeling,” Land. vol. 3, pp. 719-738, 2014.
R. Zamani, “A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem,” RAIRO - Operations Research. vol. 46 (1), pp. 23-39, 2012.
J. L. Ponz-Tienda, V. Yepes, E. Pellicer, and J. Moreno-Flores, “The Resource Leveling Problem with multiple resources using an adaptive genetic algorithm,” Autom. Constr. vol. 29, pp. 161–172, 2013.
R. H. Möhring, “Minimizing costs of resource requirements in project networks subject to a fix completion time,” Oper. Res. vol. 32, pp. 89-120, 1984.
K. Neumann, and J. Zimmermann, “Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints,” Euro. J. Oper. Res. vol. 127, pp. 425-443, 2000
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Aria Shahsavar, Seyed Taghi Akhavan Niaki, Amir Abbas Najafi
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
