Kaynak kısıtlı proje çizelgeleme probleminde tekrarsız kromozom destekli paralel genetik algoritma uygulaması

Abstract

Kaynak kısıtlı proje çizelgeleme bir kombinatorial optimizasyon problemidir ve kaynak optimizasyonuna yönelik olarak Proje ve Yapım Yönetimi alanında kullanılan önemli bir araçtır. Projeyi oluşturan aktivitelerin süreleri, kaynak ihtiyaçları, öncelik-sonralık ilişkileri ve kullanılacak kaynakların sınırları belirlenmiştir. Proje tamamlanma süresinin minimize edilmesi hedeflenir. Tanımı basitçe yapılsa da, kaynak kısıtlı proje çizelgeleme problemi, NP-Hard optimizasyon problemlerinin sınıfına aittir ve aslında pratikte en zorlu klasik problemlerden biridir. Kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için geliştirilen kesin yöntemler, özellikle büyük problemlerin çözümünde -pratikte kullanılamayacak kadar çok- zaman alıcıdırlar. Meta-sezgisel algoritmalar ise büyük boyutlara ve çok karmaşık kısıtlamalara sahip problemlere makul hesaplama zamanlarında yeteri kadar iyi çözümler üretebilirler. Kaynak kısıtlı proje çizelgeleme problemlerinin meta-sezgisel algoritmalara çözümü yoğun çalışılan bir alandır. Literatür taraması ve boşluk analizi sırasında, Genetik Algoritma'ya yönelik güçlendirme ve desteklerin etkili olabileceği görülmüştür. Doktora tezinde uygulanan güçlendirme ve desteklerin ardındaki ana fikir: tekrarsızlığın sağlanması ve çeşitlendirilmenin arttırılmasıdır. Genetik Algoritma'ya yönelik olarak aktarılan tekrarsız kromozom güçlendirmesi: Tekrarlanan kromozomların uzaklaştırılması ve yerlerine -çeşitliliği sağlamak üzere- yenilerinin konması esasına dayanmaktadır. Kaynak kısıtlı proje çizelgeleme problemine yönelik olarak aktarılan tekrarsız kromozom güçlendirmesi ise farklı görünen ama aynı kaynak profilini üreten kromozomların elenmesi ve yerlerine yenilerinin konulmasını sağlamaktadır. Hibrit Simulated Annealing desteği: yerel iyiden kaçmak ve daha iyi çözümler içerebilecek patikalara sıçramak için kullanılmaktadır. Paralel Genetik Algorirma desteği, Genetik Algoritma'ya göre daha hızlı sonuca ulaşmak, daha küçük popülasyonla çalışmak, daha yüksek çeşitlilik sağlamak ve daha yüksek çözüm kalitesi elde etmek için kullanılmaktadır. Doktora tezinde geliştirilen uygulama MATLAB ortamında hazırlanmıştır ve kaynak kısıtlı proje çizelgeleme problemlerinin başarım değerlerinin ölçülmesinde standart olarak kullanılan PSPLIB problemleri üzerinde sınanmıştır. Problemlerinin çözümü sonucunda elde edilen ortalama sapma değerleri: J30 ve J60 problemlerinde aynı çözüm değerlerini veren diğer çalışmalarla birlikte en üst bantta, J120 problemlerinde altıncı sırada yer almaktadır. Çözümler sırasında J120_35_5 numaralı problemde, -daha önceki çalışmalarda elde edilmemiş- en iyi değere erişilmiştir. Problemin çözümü onaylanmış ve PSPLIB problemlerini barındıran Münih Teknik Üniversitesi resmi web sitesinde yer almıştır. Doktora tezinde uygulanan güçlendirmeler ve destekler, kaynak kısıtlı proje çizelgeleme problemlerine yönelik olarak yapılacak yeni çalışmalarda yol gösterici olarak kullanılabilir.

Resource constrained project scheduling is a combinatorial optimization problem and is an important tool used in Project and Construction Management for resource optimization. The duration of the activities, resource requests, precedence relations and the limits of the resources to be used were strictly determined. The goal is minimizing the makespan of project. Despite the simplicity of its definition, the resource constrained project scheduling problems belongs to the class of NP-Hard optimization problems and is actually one of the most intractable classical problems in practice. The exact methods developed to solve resource constrained project scheduling problems are time consuming and useless, especially when solving large problems. Metaheuristics are mostly useful to reach good quality solutions in reasonable computational times and are suitable for practical problems, which often have large dimensions and very complex constraints. The solution of resource constrained project scheduling problems with Meta-heuristics is one of the intensive working areas. It was determined during the literature review and gap analysis what improvements and supports for Genetic Algorithm could be effective. The main idea behind the improvement and support applied in this PhD Thesis is to achieve nonrepetition and increase diversification. Nonrepetitive chromosome improvement for the Genetic Algorithm: It is based on the removal of repetitive chromosomes and the replacement of new ones in order to provide diversity. The nonrepetitive chromosome improvement for the resource constrained project-scheduling problem allows the elimination of chromosomes producing the same source profile and replacing them with new ones. Hybrid Simulated Annealing support: used to escape from the local optimum and to leap forward into pathways that may include better solutions. Parallel Genetic Algorithm support is used to achieve faster results than Genetic Algorithm, to work with smaller populations, to provide higher diversity and to achieve higher solution quality. The application in this PhD Thesis has been developed on MATLAB environment and has been tested on PSPLIB problems, which are used as standard for measuring the performance values of resource constrained project scheduling problems. The average deviation values obtained as a result of the solutions of the problems: J30 and J60 problems are at the top band with other top studies having equal results, J120 problems are ranked as sixth and have minor gaps comparing with other top studies. The best new solution has been reached on problem J120_35_5. The solution has been approved and appended on the official website of the Technical University of Munich, which hosted the PSPLIB problems. Improvements and supports applied in this PhD Thesis can be used as a guide for new studies on resource constrained project-scheduling problems. The aim of the doctoral thesis is to develop a genetic algorithm for the solution of the resource constrained project scheduling problems, which shows high performance value compared to the current studies examined in the literature. This thesis consists of the following five chapters. In the first chapter, background, motivation, purpose, contribution to science, methods-tools and organization of thesis are explained. In the second chapter, a recent literature survey on resource constrained project scheduling problems is presented. The literature research is presented under the headings of classification, solution methods, schedule presentation schemes and work towards solution. In the third chapter, GA was examined in detail. This chapter is presented under the headings of metaheuristic optimization, No Free Lunch Theory, GA and PGA. In the fourth chapter, hybrid parallel GA application which was prepared for resource constrained project scheduling problems was introduced. The conceptual principles behind the application, the algorithms used and the results obtained are discussed. Two improvement approaches, one for GA and the other for resource constrained project scheduling problems were given, followed by PGA and hybrid SA supports. At the end of the fourth chapter, the results obtained from the application are compared with the studies in the literature. Finally, Chapter five concludes the research of this thesis by summarizing its significant technical contributions in the domain of resource constrained project scheduling problems research produced during this study and the major conclusions that can be drawn from the experiments conducted. Also, some conceivable directions for further research are also suggested. Metaheuristic algorithms are techniques that independent of the problem structure and aim to obtain good quality solutions at reasonable computational times. Metaheuristic algorithms are generally well suited for practical problems with large dimensions and very complex constraints. The use of metaheuristic algorithms is not efficient when solution already known problems. If the search space is too big, the complexity of the problem is high, the mathematical modeling of the problem and the solution is very difficult, then metaheuristic algorithms can be used. Pure metaheuristic algorithms can produce good results or be inadequate for solving hard combinatorial optimization problems. In order to achieve better results, the problem specific neighborhood structures, search space constraints and guiding rules should be studied carefully and any improvements that are accessible should be used. In particular, the solution of linear equations, constraints or simply solvable nonlinear equations should be done within the model, and solutions of such problems should not be left to the metaheuristic algorithms. If it is possible, the solution design should be based on searching in feasible areas. Although it is possible to use penalty functions for the unacceptable areas, it should be considered as the last option. In this case, the value of the penalty function should be designed in such a way that it can point towards the feasible region. Whenever possible, the power of exact solution algorithms must be used, and metaheuristic algorithms should be used to efficiently navigate in search space and produce new solutions. GA works to improve the solution quality of population, as opposed to the local search strategies that work to improve the single solution. After creating an initial population, the operators carry out successive generation and evaluate the results. Once the new generation has been produced, the most appropriate solutions are kept to create the next generation, while the bad solutions are eliminated. The fitness value is used to measure the quality of the solution and is usually calculated from the objective function of the optimization problem to be solved. The PGA is used to shorten the long-lasting solution time in GA's wide search spaces and provides gains in terms of both performance and solution quality. Parallel running hill climbing algorithms cannot share information among themselves, whereas the lower GAs belonging to the PGA can share solutions depending on the chosen migration mechanism. Thus, both the permeability and diversity processes are enriched in a balanced manner. Instead of over-optimization, simple but effective, guiding rules should be sought. In general, no superiority of any metaheuristic algorithm can be determined. Some algorithms seem to be appropriate for some specific problem structures, but there is no significant difference in long-term averages that will show dominance. Recent studies on the No Free Lunch theorem suggest that problem-specific metaheuristic algorithms can be more successful than general metaheuristic algorithms. The hybrid algorithm approach that has emerged in recent years can benefit in achieving better results. If possible, different algorithms should be combined. Hyper metaheuristics can be an important area of study for selecting algorithms to be used in problem solving. Algorithms that are not ambitious about achieving the best results but approaching reasonable results quickly should not be ignored. In many cases, the cost of a unit recovery may be too extreme to be tolerated in practice. Resource constrained project scheduling problems with repeated activities or repeated subprojects may be an interesting area of study. New presentation and calculation methods can be developed for such projects. Although the number of activities increases a lot, activity blocks remain the same. Algorithms to be developed over the same sequence of activity blocks can significantly reduce the search space. It is important to pay attention to hold on the a false assumptions made, when working on the resource constrained project scheduling problems. Activity times are predetermined and are based on significant assumptions. Resource constraints may change throughout the project. A small improvement in resource constraints can significantly reduce project completion time. Similarly, the divisibility of activities should be examined. By dividing the activity into several activities connected in series, it can provide better planning and modeling facilities. If the activity does not have to continue uninterruptedly or there is no cost for intermittent execution, resource balancing process options will be increased and a shorter total project completion time can be obtained. The resource requirement can be concentrated before activity or at the beginning of the activity and may appear as a single load at any time. These features should be examined well and should not be considered as a uniformly distributed load with an extremely rough approach. Sensitivity analysis for the source and time relationship may be guiding. There should be a reasonable point between extreme detailism and extreme roughness in the implementation of the RCPSP, and should concentrate on places that have a leverage effect on the behavior of the system. If possible, the resource limit should be increased and the risks on the expected resource supply profile should be reduced by using time and resource buffers. Simulation approaches, which are entered into the system according to the probability distributions of both activity periods and resources, can help with more accurate estimations of possible reality. It may be useful to use the improvements and supports applied in the RCPSP for the following purposes: To prevent the presence of chromosomes in the population that appear different but represent the same solution, to provide greater diversity in the population, to reach a solution with a smaller population, to reduce the time to reach a solution and improving the quality of the solution. The performance values of the application developed in thesis are evaluated through the black-box approach. The contribution of each of the improvements and supports on the solution performance can be transformed into the white-box approach and explained together with the performance values to be obtained through different test problems.