Naslov
Complexity Comparison of Integer Programming and Genetic Algorithms for Resource Constrained Scheduling Problems

Autori
Čorić, Rebeka ; Đumić, Mateja ; Jakobović, Domagoj

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
MIPRO 2017 Int. Conf. Proceedings. / Biljanović, Petar - Opatija : Hrvatska udruga za informacijsku i komunikacijsku tehnologiju, elektroniku i mikroelektroniku - MIPRO, 2017, 1394-1400

ISBN
978-953-233-093-9

Skup
MIPRO 2017, 40th Jubilee International Convention

Mjesto i datum
Opatija, Hrvatska, 22.05.2017. - 26.05.2017

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
scheduling, RCPSP, GA, IP

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA