본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

A Looping Population Learning Algorithm for the Makespan/Resource Trade-offs Project Scheduling

Fang, Ying-Chieh    (Department of Industrial Engineering and Management Yuan-Ze University   ); Chyu, Chiuh-Cheng    (Department of Industrial Engineering and Management Yuan-Ze University  );
  • 초록

    Population learning algorithm (PLA) is a population-based method that was inspired by the similarities to the phenomenon of social education process in which a diminishing number of individuals enter an increasing number of learning stages. The study aims to develop a framework that repeatedly applying the PLA to solve the discrete resource constrained project scheduling problem with two objectives: minimizing project makespan and renewable resource availability, which are two most common concerns of management when a project is being executed. The PLA looping framework will provide a number of near Pareto optimal schedules for the management to make a choice. Different improvement schemes and learning procedures are applied at different stages of the process. The process gradually becomes more and more sophisticated and time consuming as there are less and less individuals to be taught. An experiment with ProGen generated instances was conducted, and the results demonstrated that the looping framework using PLA outperforms those using genetic local search, particle swarm optimization with local search, scatter search, as well as biased sampling multi-pass algorithm, in terms of several performance measures of proximity. However, the diversity using spread metric does not reveal any significant difference between these five looping algorithms.


  • 주제어

    Project Scheduling .   Population Learning Algorithms .   Genetic Algorithms .   Particle Swarm Optimization .   Scatter Search .   Forward/Backward Improvement.  

  • 참고문헌 (35)

    1. Blazewicz, J., Lenstra, J. K., and Rinooy Kan, A. H. G. (1983), Scheduling subject to resource constraints: Classification and complexity, Discrete Mathematics, 5, 11-24 
    2. Boctor, F. F. (1990), Some efficient multi-heuristic procedures for resource-constrained project scheduling, European Journal of Operational Research, 49, 3-13 
    3. Debels, D., Reyck, B. D., Leus, R., and Vanhoucke, M. (2006), A hybrid scatter search/electromagnetism meta-heuristic for project scheduling, European Journal of Operational Research, 169, 638-653 
    4. Eberhart, R. C., Simpson, P., and Dobbins, R. (1996), Computational Intelligence PC Tools, Academic Press Professional, 212-226 
    5. Erenguc, S. S., Ahn, T., and Conway, D. G. (2001), The resource constrained project scheduling problem with multiple crashable modes: An exact solution method, Naval Research Logistics, 48, 107-127 
    6. Herroelen, W., Demeulemeester, E. and De Reyck, B. (1999), A classification scheme for project scheduling, edited by J. Weglarz, Project Scheduling: Recent Models, Algorithms and Applications, Academic Publishers, USA, 1-26 
    7. Jedrzejowicz, P. (1999), Social learning algorithm as a tool for solving some different scheduling problems, Foundation of Computing and Decision Science, 24(2), 51-66 
    8. Klein, R. (2000), Bidirectional planning: improving priority rule-based heuristics for scheduling resourceconstrained projects, European Journal of Operational Research, 127, 619-638 
    9. Kolisch, R. and Drexl, A. (1996), Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation, European Journal of Operational Research, 90, 320-333 
    10. Li, K. Y. and Willis, R. J. (1992), An iterative scheduling technique for resource-constrained project scheduling, European Journal of Operational Research, 56, 370-379 
    11. Suganthan, P. N. (1999), Particle swarm optimizer with neighbourhood operator, in Proceedings of the Congress on Evolutionary Computation, (Washington DC, USA), IEEE Service Center, Piscataway, NJ, 1958-1961 
    12. Van Veldhuizen, D. A. (1999), Multiobjective evolutionary algorithms: classifications, analyses, and new Innovations, PhD thesis, Department of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, Wri-ght-Patterson AFB, Ohio 
    13. Zhang, H., Li, X., Li, H., and Hung, F. (2005), Particle swarm optimization-based schemes for resourceconstrained project scheduling, Automation in Construction, 14, 393-404 
    14. Glover, F. (1977), Heuristics for integer programming using surrogate constraints, Decision Sciences, 8, 156-166 
    15. Kolisch, R. and Sprecher, A. (1996), PSPLIB-A project scheduling problem library, European Journal of Operational Research, 96, 205-216 
    16. Vanhoucke, M., Demeulemeester, E., and Herroelen, W. (2002), Discrete time/cost trade-offs in project scheduling with time-switch constraints, Journal of the Operational Research Society, 53(7), 741-751 
    17. Erenguc, S. S. and Icmeli-Tukel, O. (1999), Integrating quality as a measure of performance in resourceconstrained project scheduling problems, edited by Jan Weglarz, Project Scheduling: Recent Models, Algorithms and Applications, Kluwer Academic Publishers, USA, 433-450 
    18. Hsu, C. C. and Kim, D. S. (2005), A new heuristic for the multi-mode resource investment problem, Journal of the Operational Research Society, 56, 406-413 
    19. Alcaraz, J. and Maroto, C. (2001), A Robust Genetic Algorithm for Resource Allocation in Project Scheduling, Annals of Operations Research, 102, 83-109 
    20. Kemmo$\acute{e}$ Tchomt$\acute{e}$, S. and Gourgand, M. (2009), Particle swarm optimization: A study of particle displacement for solving continuous and combinatorial optimization problems, International Journal of Production Economics, doi:10.1016/j.ijpe.2008.03.015 
    21. Yamashita, D. S., Armentano, V. A., and Laguna M. (2006), Scatter search for project scheduling with resource availability cost, European Journal of Operational Research, 169, 623-637 
    22. Deb, K. (2001), Multi-objective optimization using evolutionary algorithm, Wiley, Chichester, 328 
    23. Kennedy, J. and Eberhart, R. C. (1995), Particle swarm optimization, In Proceedings of the 1995 IEEE International Conference on Neural Networks, Piscataway, New Jersey, IEEE Service Center, 1942-1948 
    24. Valls, V., Ballestin, F., and Quintanilla, S. (2005), Justification and RCPSP: A technique that pays, European Journal of Operational Research, 165, 375-386 
    25. Keskin, B. B. and Uster, H. (2007), A scatter searchbased heuristic to locate capacitated transhipment points, Computers and Operations Research, 34, 3112-3125 
    26. Glover, F. and Kochenberge, G. A. (2003), Handbook of Metaheuristics, editors, Kochenberge, Kluwer Academic Publishers 
    27. Jedrzejowicz, P. and Ratajczak, E. (2006), Population learning algorithm for the resource-constrained project scheduling, Perspectives in Modern Project Scheduling, edited by J. J$\acute{o}$zefowska and J. Weglarz, Springer's International Series 
    28. Zitzler, E. and Thiele, L. (1999), Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach, IEEE Transactions on Evolutionary Computation, 3(4), 257-271 
    29. Marti, R., Laguna, M., and Glover, F. (2006), Principle of scatter search, European Journal of Operational Research, 169, 359-372 
    30. Deb, K. and Jain, S. (2002), Running performance metrics for evolutionary multiobjective optimization, Asia-Pacific Conference Simulated Evolution and Learning (SEAL 01), Singapore, 12-20 
    31. Demeulemeester, E. L. and Herroelen, W. S. (2002), Project scheduling: A research handbook, Norwell, MA: Kluwer, 8 
    32. Kolisch, R. and Hartmann, S. (2006), Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling: An update, European Journal of Operational Research, 174, 23-37 
    33. Waligora, G. (2008), Discrete-continuous project scheduling with discounted cash flow-A tabu search approach, Computers and Operations Research, 35, 2141-2153 
    34. J$\acute{o}$zefowska, J., Mika, M., R$\acute{o}$zycki, R, Walig$\acute{o}$ra, G. and Weglarz, J. (1998), Local search metaheuristics for discrete-continuous schedulingproblems, European Journal of Operational Research, 107, 354-370 
    35. Tormos, P. and Lova, A. (2003), An efficient multi-pass heuristic for project scheduling with constrained resources, International Journal of Production Research, 41(5), 1071-1086 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기