Evolutionary Algorithms for Resource Constrained Project Scheduling

dc.contributor.advisor Sarker, Ruhul en_US
dc.contributor.advisor Ray, Tapabrata en_US
dc.contributor.advisor Elsayed, Saber en_US Ali, Ismail en_US 2022-03-22T12:34:56Z 2022-03-22T12:34:56Z 2016 en_US
dc.description.abstract Resource constrained project scheduling problems (RCPSPs) are well-known NP hard combinatorial problems. Due to the drawbacks of existing solution approaches, many researchers have proposed different evolutionary algorithms (EAs) for solving them. Although EAs are able to achieve near-optimal solutions, they cannot guarantee optimality and, in fact, no single EA has consistently been able to solve all types of problems. This has led to the emergence of hybrid methods which have shown good performances but their search capabilities for solving RCPSPs have not yet been fully explored. In this thesis, to efficiently solve RCPSPs, an algorithmic framework involving multiple methodologies is introduced. Firstly, a memetic algorithm (MA) consisting of a new heuristic for converting infeasible solutions to feasible ones in the initial population and multiple local search (MLS) strategies for increasing the exploitation capability of the algorithm is proposed. Secondly, an improved differential evolution (DE) algorithm containing new search operators that can guarantee the generation of feasible solutions, even from infeasible ones, is introduced. Finally, motivated by the encouraging performances of the proposed MA and DE, a bi-evolutionary algorithm (bi-EA) that utilizes the good search features of both these algorithms by automatically switching between them according to their performance, which implies placing more emphasis on the best-performing one during the evolutionary process, is proposed. In addition, two heuristic approaches developed to guide the solutions in both the initial population and every generation towards feasibility are adopted. All the algorithms proposed in this thesis are tested on a set of well-known project scheduling problems taken from the PSPLIB, with the results for instances of 30, 60, 90 and 120 activities compared with both each other and state-of-the-art algorithms. It is found that: (1) the heuristic method improves the performance of the traditional GA by 80.66% in terms of quality of solutions; (2) the use of MLS techniques leads to much better solutions (11.83%) and saves 20.21% of the GA’s computational time; (3) adopting the heuristic method in DE improves the quality of solutions by 28.96% and saves 10.62% of CPU time; (4) the improved DE operators provide much better solutions and greater savings in computational time than a traditional one; (5) bi-EA outperforms both MA and DE in terms of solution quality, especially for large-scale problems as, on average, it obtains 4.33% and 3.5% higher-quality solutions than MA and DE, respectively, and also provides competitive solutions compared with those from state-of-the-art-algorithms. en_US
dc.language English
dc.language.iso EN en_US
dc.publisher UNSW, Sydney en_US
dc.rights CC BY-NC-ND 3.0 en_US
dc.rights.uri en_US
dc.subject.other evolutionary algorithms en_US
dc.subject.other Resource constrained project scheduling en_US
dc.subject.other scheduling problems en_US
dc.subject.other genetic algorithm en_US
dc.subject.other differential evolution en_US
dc.subject.other memetic algorithm en_US
dc.subject.other multiple local searches en_US
dc.subject.other hybrid algorithms en_US
dc.subject.other multiple methodologies en_US
dc.title Evolutionary Algorithms for Resource Constrained Project Scheduling en_US
dc.type Thesis en_US
dcterms.accessRights open access
dcterms.rightsHolder Ali, Ismail
dspace.entity.type Publication en_US
unsw.identifier.doi en_US
unsw.relation.faculty UNSW Canberra
unsw.relation.originalPublicationAffiliation Ali, Ismail, Engineering & Information Technology, UNSW Canberra, UNSW en_US
unsw.relation.originalPublicationAffiliation Sarker, Ruhul, Engineering & Information Technology, UNSW Canberra, UNSW en_US
unsw.relation.originalPublicationAffiliation Ray, Tapabrata, Engineering & Information Technology, UNSW Canberra, UNSW en_US
unsw.relation.originalPublicationAffiliation Elsayed, Saber, Engineering & Information Technology, UNSW Canberra, UNSW en_US School of Engineering and Information Technology *
unsw.thesis.degreetype Masters Thesis en_US
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
public version.pdf
10.38 MB
Resource type