Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm

Jiancheng Wang

doi:doi:10.11648/j.sjbm.20160406.18

| Peer-Reviewed

Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm

Jiancheng Wang

Published in Science Journal of Business and Management (Volume 4, Issue 6)

Received: 30 October 2016 Accepted: 22 November 2016 Published: 7 January 2017

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

Due to the development of management idea and the scarcity of some resources, the lean management has become the necessary request to implement effective control of resource constrained project. Resource constrained project scheduling is the significant guarantee to attain the lean management. The resource constrained project scheduling problem (RCPSP), with the objective of minimizing project duration and with the precedence relations described by an activity-on-arrow (AOA) network, is formulated as a combination optimization problem and solved using the priority-based genetic algorithm (GA). The activity priorities are represented by chromosome and serial scheduling scheme (SSS) and parallel scheduling scheme (PSS) are developed and utilized to transform chromosome-represented priorities to an active schedule subject to the logic and resource constraints so that project duration corresponding to each chromosome can be evaluated. The overall framework of the GA for the RCPSP is developed and the basic components of the algorithm are designed. Simulation is provided so as to investigate the performance of the priority-based GA with SSS and PSS as decoding method, respectively. The optimal solution to a small-sized resource constrained benchmark instance is scheduled to find the shortest project duration. Comparative simulation results demonstrate not only the effectiveness and efficiency of GA with SSS or PSS as decoding methods in solution to RCPSP with precedence relation of activities diagramed as an AOA network but also the effect of different evolution parameter settings on solution quality of the problem.

Published in	Science Journal of Business and Management (Volume 4, Issue 6)
DOI	10.11648/j.sjbm.20160406.18
Page(s)	229-237
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Resource Constrained, Project Duration Optimization, Equipment Support, Genetic Algorithm, Network Planning, Activity-on-Arc Network, Serial Scheduling Scheme, Parallel Scheduling Scheme

References

[1]	E. W. DAVIS and J. H. Patterson, “A comparison of heuristic and optimum solutions in resource-constrained project scheduling,” Management Science, vol. 21, pp. 944–955, April 1975.
[2]	B. Gavish and H. Pirkul, “Algorithms for multi-resource generalized assignment problem,” Management Science, vol. 37, pp. 695–713, June 1991.
[3]	R. Klein, “Project scheduling with time-varying resource constraints,” International Journal of Production Research, vol. 38, pp. 3937–3952, November 2000.
[4]	J. Buddhakulsomsiri and D. S. Kim, “Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting,” Eur. J. Oper. Res., vol. 175, pp. 279–295, November 2006.
[5]	R. Kolisch and S. Hartmann, “Experimental investigation of heuristics for resource-constrained project scheduling: an update,” Eur. J. Oper. Res., vol. 174, pp. 23–37, October 2006.
[6]	J. Buddhakulsomsiri and D. S. Kim, “Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting,” Eur. J. Oper. Res., vol. 178, pp. 374–390, April 2007.
[7]	P.-H. Chen and H. Weng, “A two-phase GA model for resource-constrained project scheduling,” Autom. Constr., vol. 18, pp. 485–498, July 2009.
[8]	D. Heon Jun and K. El-Rayes, “Multiobjective optimization of resource leveling and allocation during construction scheduling,” J. Constr. Eng. Manag., vol. 137, pp. 1080–1088, December 2011.
[9]	P. Ghoddousi, E. Eshtehardian, S. Jooybanpour, and A. Javanmardi, “Multi-mode resource-constrained discrete time-cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm,” Autom. Constr., vol. 30, pp. 216–227, March 2013.
[10]	V. V. Peteghem and M. Vanhoucke, “An experimental investigation of metaheuristics for the multi-mode resource-cons-trained project scheduling problem on new dataset instances,” Eur. J. Oper. Res., vol. 235, pp. 62–72, May 2014.
[11]	C. Kellenbrink and S. Helber, “Scheduling resource-constrained projects with a flexible project structure,” Eur. J. Oper. Res., vol. 246, pp. 379–391, October 2015.
[12]	J. Cheng, J. Fowler, K. Kempf, and S. Mason, “Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting,” Computers & Oper. Research, vol. 53, pp. 275–287, January 2015.
[13]	M. Vanhoucke and J. Coelho, “An approach using SAT solvers for the RCPSP with logical constraints,” Eur. J. Oper. Res., vol. 249, pp. 577–591, March 2016.
[14]	S. Kreter, J. Rieck, and J. Zimmermann, “Models and solution procedures for the resource-constrained project scheduling problem with general temporal constraints and calendars,” Eur. J. Oper. Res., vol. 251, pp. 387–403, June 2016.
[15]	A. Mingozzi, V. Maniezzo, S. Ricciardelli, and L. Bianco, “An exact algorithm for the resource constrained project scheduling problem based on a new mathematical formulation,” Management Science, vol. 44, pp. 714–729, May 1998.
[16]	P. Brucker, S. Knust, A. Schoo, and O. Thiele, “A branch-and-bound algorithm for the resource constrained project scheduling problem,” Eur. J. Oper. Res., vol. 107, pp. 272–288, June 1998.
[17]	R. Klein and A. Scholl, “Scattered branch and bound: an adaptive search strategy applied to resource-constrained project scheduling,” Cent. Eur. J. Oper. Res., vol. 7, pp. 177–201, January 1998.
[18]	A. Sprecher, “Scheduling resource-constrained projects competitively at modest memory requirements,” Manag. Sci., vol. 46, pp. 710–723, May 2000.
[19]	A. Naber and R. Kolisch, “MIP models for resource-constrained project scheduling with flexible resource profiles,” Eur. J. Oper. Res., vol. 239, pp. 335–348, December 2014.
[20]	L. James, “A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support,” Mathematical Programming, vol. 146, pp. 219–244, August 2014.
[21]	S.-E. Sampson and E.-N. Weiss, “Local search techniques for the generalized resource-constrained project scheduling problem,” Naval Research Logistics, vol. 40, pp. 665–675, August 1993.
[22]	E. Pinson, C. Prins, and F. Rullier, “Using tabu search for solving the resource-constrained project scheduling problem,” in Proceedings of the Fourth International Workshop on Project Management and Scheduling, E. Demeulemeester and W. Herroelen, eds. Leuven: Research Center for Operations Management, 1994, pp. 102–106.
[23]	J.-K. Lee and Y.-D. Kim, “Search heuristics for resource constrained project scheduling,” Journal of the Operational Research Society, vol. 47, pp. 678–689, May 1996.
[24]	S. Hartmann, “A competitive genetic algorithm for resource-constrained project scheduling,” Naval Research Logistics, vol. 45, pp. 733–750, October 1998.
[25]	T. Baar, P. Brucker, and S. Knust, “Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem,” in Meta-heuristics: advances and trends in local search paradigms for optimization, S. Voss, S. Martello, I. Osman, and C. Roucairol, Eds. Dordrecht: Kluwer Academic Publishers, 1998, pp. 1–8.
[26]	K. Bouleimen and H. Lecocq, “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple modes version,” Eur. J. Oper. Res., vol. 149, pp. 268–281, September 2003.
[27]	R. Kolisch and S. Hartmann, “Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis,” in Project Scheduling: Recent Models, Algorithms and Applications, J. Weglarz, Ed. Berlin: Kluwer Academic Publishers, 1999, pp. 147–178.
[28]	S. Hartmann and R. Kolisch, “Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem,” Eur. J. Oper. Res., vol. 127, pp. 394–407, December 2000.
[29]	H. Wang, T.-L. Li, and D. Lin, “Efficient genetic algorithm for resource-constrained project scheduling problem,” Trans. of Tianjin University, vol. 16, pp. 376–382, October 2010.
[30]	F. Gargiulo and D. Quagliarella, “Genetic algorithms for the resource constrained project scheduling problem,” in Proc. the 13th IEEE International Symp. Computational Intelligence and Informatics (CINTI 2012). Budapest: IEEE Press, 2012, pp. 39–47.
[31]	A. Lim, H. Ma, and B. Rodrigues, “New meta-heuristics for the resource-constrained project scheduling problem,” Flexible Services and Manufacturing Journal, vol. 25, pp. 48–73, June 2013.
[32]	M. Mori and C. C. Tseng, “A genetic algorithm for multi-mode resource constrained project scheduling problem,” Eur. J. Oper. Res., vol. 100, pp. 134–141, July 1997.
[33]	V. Valls, F. Ballestín, and S. Quintanilla, “A hybrid genetic algorithm for the resource-constrained project scheduling problem,” Eur. J. Oper. Res., vol. 185, pp. 495–508, March 2008.
[34]	R. Zamani, “A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem,” Eur. J. Oper. Res., vol. 229, pp. 552–559, September 2013.
[35]	H. Zhang, X. Li, H. Li, and F. Huang, “Particle swarm optimization-based schemes for resource-constrained project scheduling,” Autom. Constr., vol. 14, pp. 393–404, June 2005.
[36]	H. Zhang, H. Li, and C. Tam, “Particle swarm optimization for resource-constrained project scheduling,” Int. J. Proj. Manag., vol. 24, pp. 83–92, January 2006.
[37]	D. Merkle, M. Middendorf, and H. Schmeck, “Ant colony optimization for resource-constrained project scheduling,” IEEE Trans. Evol. Comput., vol. 6, pp. 333–346, August 2002.
[38]	J.-G. He, X.-D. Chen, and X. Chen, “A filter-and-fan approach with adaptive neighborhood switching for resource-constrained project scheduling,” Computers & Operations Research, vol. 71, pp. 71–81, July 2016.
[39]	R. Klein, “Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects,” Eur. J. Oper. Res., vol. 127, pp. 619–638, December 2000.
[40]	A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: a review,” ACM Comput. Surv., vol. 31, pp. 264–323, September 1999.
[41]	A. El Imrani, A. Bouroumi, H. Zine El Abidine, M. Limouri, and A. Essaïd, “A fuzzy clustering-based niching approach to multimodal function optimization,” Cogn. Syst. Res., vol. 1, pp. 119–133, June 2000.
[42]	J. Alami, A. E. Imrani, and A. Bouroumi, “A multipopulation cultural algorithm using fuzzy clustering,” Appl. Soft Comput., vol. 7, pp. 506–519, March 2007.
[43]	J. C. Bezdek, R. Ehrlich, and W. Full, “FCM: the fuzzy c-means clustering algorithm,” Comput. Geosci., vol. 10, pp. 191–203, December 1984.
[44]	W. Kwedlo, “A clustering method combining differential evolution with the K-means algorithm,” Pattern Recogn. Lett., vol. 32, 1613–1621, September 2011.
[45]	Y.-J. Wang, J.-S. Zhang, and G.-Y. Zhang, “A dynamic clustering based differential evolution algorithm for global optimization,” Eur. J. Oper. Res., vol. 183, pp. 56–73, November 2007.
[46]	Z. Cai, W. Gong, C.-X. Ling, and H. Zhang, “A clustering-based differential evolution for global optimization,” Appl. Soft Comput., vol. 11, pp. 1363–1379, January 2011.
[47]	M.-Y. Cheng and K.-Y. Huang, “Genetic algorithm-based chaos clustering approach for nonlinear optimization,” J. Mar. Sci. Technol., vol. 18, pp. 435–441, June 2010.
[48]	R. Caponetto, L. Fortuna, S. Fazzino, and M. G. Xibilia, “Chaotic sequences to improve the performance of evolutionary algorithms,” IEEE Trans. Evol. Comput., vol. 7, pp. 289–304, June 2003.
[49]	B. Li and W.-S. Jiang, “Optimizing complex functions by chaos search,” Cybern. Syst. vol. 29, pp. 409–419, January 1998.
[50]	A. Thammano and A. Phu-ang, “A hybrid evolutionary algorithm for the resource-constrained project scheduling problem,” Artificial Life and Robotics, vol. 17, pp. 312–316, December 2012.
[51]	D. Debels and M. Vanhoucke, “A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem,” Operations Research, vol. 55, pp. 457–469, May-June 2007.
[52]	M.-Y. Cheng, D.-H. Tran, and Y.-W. Wu, “Using a fuzzy clustering chaotic-based differential evolution with serial method to solve resource-constrained project scheduling problems,” Automation in Construction, vol. 37, pp. 88–97, January 2014.
[53]	J. Gonçalves, M. Resende, and J. Mendes, “A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem,” Journal of Heuristics, vol. 17, pp. 467–486, October 2011.
[54]	R. Kolisch, “Serial and parallel resource-constrained project scheduling methods revisited: theory and computation,” Eur. J. Oper. Res., vol. 90, pp. 320–333, April 1996.
[55]	W. Spears and K. Dejong, “On the virtues of parameterized uniform crossover,” in Proceedings of the Fourth International Conference on Genetic Algorithms, R. Belew and L. Booker Eds. San Diego: Morgan Kaufmann Publishers Inc., 1991, pp. 230–236.
[56]	D. Goldberg, Genetic algorithms in search optimization and machine learning. Reading: Addison-Wesley, 1989, p. 115.

Cite This Article

Plain Text BibTeX RIS

APA Style

Jiancheng Wang. (2017). Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm. Science Journal of Business and Management, 4(6), 229-237. https://doi.org/10.11648/j.sjbm.20160406.18

Copy | Download

ACS Style

Jiancheng Wang. Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm. Sci. J. Bus. Manag. 2017, 4(6), 229-237. doi: 10.11648/j.sjbm.20160406.18

Copy | Download

AMA Style

Jiancheng Wang. Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm. Sci J Bus Manag. 2017;4(6):229-237. doi: 10.11648/j.sjbm.20160406.18

Copy | Download

@article{10.11648/j.sjbm.20160406.18,
  author = {Jiancheng Wang},
  title = {Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm},
  journal = {Science Journal of Business and Management},
  volume = {4},
  number = {6},
  pages = {229-237},
  doi = {10.11648/j.sjbm.20160406.18},
  url = {https://doi.org/10.11648/j.sjbm.20160406.18},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.sjbm.20160406.18},
  abstract = {Due to the development of management idea and the scarcity of some resources, the lean management has become the necessary request to implement effective control of resource constrained project. Resource constrained project scheduling is the significant guarantee to attain the lean management. The resource constrained project scheduling problem (RCPSP), with the objective of minimizing project duration and with the precedence relations described by an activity-on-arrow (AOA) network, is formulated as a combination optimization problem and solved using the priority-based genetic algorithm (GA). The activity priorities are represented by chromosome and serial scheduling scheme (SSS) and parallel scheduling scheme (PSS) are developed and utilized to transform chromosome-represented priorities to an active schedule subject to the logic and resource constraints so that project duration corresponding to each chromosome can be evaluated. The overall framework of the GA for the RCPSP is developed and the basic components of the algorithm are designed. Simulation is provided so as to investigate the performance of the priority-based GA with SSS and PSS as decoding method, respectively. The optimal solution to a small-sized resource constrained benchmark instance is scheduled to find the shortest project duration. Comparative simulation results demonstrate not only the effectiveness and efficiency of GA with SSS or PSS as decoding methods in solution to RCPSP with precedence relation of activities diagramed as an AOA network but also the effect of different evolution parameter settings on solution quality of the problem.},
 year = {2017}
}

Copy | Download

TY  - JOUR
T1  - Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm
AU  - Jiancheng Wang
Y1  - 2017/01/07
PY  - 2017
N1  - https://doi.org/10.11648/j.sjbm.20160406.18
DO  - 10.11648/j.sjbm.20160406.18
T2  - Science Journal of Business and Management
JF  - Science Journal of Business and Management
JO  - Science Journal of Business and Management
SP  - 229
EP  - 237
PB  - Science Publishing Group
SN  - 2331-0634
UR  - https://doi.org/10.11648/j.sjbm.20160406.18
AB  - Due to the development of management idea and the scarcity of some resources, the lean management has become the necessary request to implement effective control of resource constrained project. Resource constrained project scheduling is the significant guarantee to attain the lean management. The resource constrained project scheduling problem (RCPSP), with the objective of minimizing project duration and with the precedence relations described by an activity-on-arrow (AOA) network, is formulated as a combination optimization problem and solved using the priority-based genetic algorithm (GA). The activity priorities are represented by chromosome and serial scheduling scheme (SSS) and parallel scheduling scheme (PSS) are developed and utilized to transform chromosome-represented priorities to an active schedule subject to the logic and resource constraints so that project duration corresponding to each chromosome can be evaluated. The overall framework of the GA for the RCPSP is developed and the basic components of the algorithm are designed. Simulation is provided so as to investigate the performance of the priority-based GA with SSS and PSS as decoding method, respectively. The optimal solution to a small-sized resource constrained benchmark instance is scheduled to find the shortest project duration. Comparative simulation results demonstrate not only the effectiveness and efficiency of GA with SSS or PSS as decoding methods in solution to RCPSP with precedence relation of activities diagramed as an AOA network but also the effect of different evolution parameter settings on solution quality of the problem.
VL  - 4
IS  - 6
ER  -

Copy | Download

Author Information

Jiancheng Wang

Department of Equipment Command, Equipment Academy, Beijing, China

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Jiancheng Wang. (2017). Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm. Science Journal of Business and Management, 4(6), 229-237. https://doi.org/10.11648/j.sjbm.20160406.18

Copy | Download

ACS Style

Jiancheng Wang. Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm. Sci. J. Bus. Manag. 2017, 4(6), 229-237. doi: 10.11648/j.sjbm.20160406.18

Copy | Download

AMA Style

Jiancheng Wang. Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm. Sci J Bus Manag. 2017;4(6):229-237. doi: 10.11648/j.sjbm.20160406.18

Copy | Download

@article{10.11648/j.sjbm.20160406.18,
  author = {Jiancheng Wang},
  title = {Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm},
  journal = {Science Journal of Business and Management},
  volume = {4},
  number = {6},
  pages = {229-237},
  doi = {10.11648/j.sjbm.20160406.18},
  url = {https://doi.org/10.11648/j.sjbm.20160406.18},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.sjbm.20160406.18},
  abstract = {Due to the development of management idea and the scarcity of some resources, the lean management has become the necessary request to implement effective control of resource constrained project. Resource constrained project scheduling is the significant guarantee to attain the lean management. The resource constrained project scheduling problem (RCPSP), with the objective of minimizing project duration and with the precedence relations described by an activity-on-arrow (AOA) network, is formulated as a combination optimization problem and solved using the priority-based genetic algorithm (GA). The activity priorities are represented by chromosome and serial scheduling scheme (SSS) and parallel scheduling scheme (PSS) are developed and utilized to transform chromosome-represented priorities to an active schedule subject to the logic and resource constraints so that project duration corresponding to each chromosome can be evaluated. The overall framework of the GA for the RCPSP is developed and the basic components of the algorithm are designed. Simulation is provided so as to investigate the performance of the priority-based GA with SSS and PSS as decoding method, respectively. The optimal solution to a small-sized resource constrained benchmark instance is scheduled to find the shortest project duration. Comparative simulation results demonstrate not only the effectiveness and efficiency of GA with SSS or PSS as decoding methods in solution to RCPSP with precedence relation of activities diagramed as an AOA network but also the effect of different evolution parameter settings on solution quality of the problem.},
 year = {2017}
}

Copy | Download

TY  - JOUR
T1  - Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm
AU  - Jiancheng Wang
Y1  - 2017/01/07
PY  - 2017
N1  - https://doi.org/10.11648/j.sjbm.20160406.18
DO  - 10.11648/j.sjbm.20160406.18
T2  - Science Journal of Business and Management
JF  - Science Journal of Business and Management
JO  - Science Journal of Business and Management
SP  - 229
EP  - 237
PB  - Science Publishing Group
SN  - 2331-0634
UR  - https://doi.org/10.11648/j.sjbm.20160406.18
AB  - Due to the development of management idea and the scarcity of some resources, the lean management has become the necessary request to implement effective control of resource constrained project. Resource constrained project scheduling is the significant guarantee to attain the lean management. The resource constrained project scheduling problem (RCPSP), with the objective of minimizing project duration and with the precedence relations described by an activity-on-arrow (AOA) network, is formulated as a combination optimization problem and solved using the priority-based genetic algorithm (GA). The activity priorities are represented by chromosome and serial scheduling scheme (SSS) and parallel scheduling scheme (PSS) are developed and utilized to transform chromosome-represented priorities to an active schedule subject to the logic and resource constraints so that project duration corresponding to each chromosome can be evaluated. The overall framework of the GA for the RCPSP is developed and the basic components of the algorithm are designed. Simulation is provided so as to investigate the performance of the priority-based GA with SSS and PSS as decoding method, respectively. The optimal solution to a small-sized resource constrained benchmark instance is scheduled to find the shortest project duration. Comparative simulation results demonstrate not only the effectiveness and efficiency of GA with SSS or PSS as decoding methods in solution to RCPSP with precedence relation of activities diagramed as an AOA network but also the effect of different evolution parameter settings on solution quality of the problem.
VL  - 4
IS  - 6
ER  -

Copy | Download