Complexity Comparison of Integer Programming and Genetic Algorithms for Resource Constrained Scheduling Problems (CROSBI ID 652208)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Čorić, Rebeka ; Đumić, Mateja ; Jakobović, Domagoj
engleski
Complexity Comparison of Integer Programming and Genetic Algorithms for Resource Constrained Scheduling Problems
Resource constrained project scheduling problem (RCPSP) is one of the most intractable combinatorial optimization problems. RCPSP belongs to the class of NP hard problems. Integer Programming (IP) is one of the exact solving methods that can be used for solving RCPSP. IP formulation uses binary decision variables for generating a feasible solution and with different boundaries eliminates some of solutions to reduce the solution space size. All exact methods, including IP, search through entire solution space so they are impractical for very large problem instances. Due to the fact that exact methods are not applicable to all problem instances, many heuristic approaches are developed, such as genetic algorithms. In this paper we compare the time complexity of IP formulations and genetic algorithms when solving the RCPSP. We present two different solution representations for genetic algorithms, permutation vector and vector of floating point numbers. Two formulations of IP and and their time and convergence results are compared for the aforementioned approaches.
scheduling, RCPSP, GA, IP
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
1394-1400.
2017.
objavljeno
Podaci o matičnoj publikaciji
MIPRO 2017 Int. Conf. Proceedings.
Biljanović, Petar
Opatija: Hrvatska udruga za informacijsku i komunikacijsku tehnologiju, elektroniku i mikroelektroniku - MIPRO
978-953-233-093-9
1847-3938
Podaci o skupu
MIPRO 2017
predavanje
22.05.2017-26.05.2017
Opatija, Hrvatska