many-objective MS-RCPSP
In iMOPSE a
Multi-Skill Resource-Constrained Project Scheduling Problem (MS-RCPSP) is defined and
benchmark dataset to support automated solvers. The MS-RCPSP problem can be defined as one objective optimisation (e.g. cost or makespan), multi objective optimisation (eg. cost
and makespan) or many-objecive optimisation. In MS-RCPSP problem 5 objectives have been defined: standard cost and duration, average cashflow, average usage of resources and skill overuse measure.
Some inital results of NTGA2 method for multi- and many- objective optimisation have been presented in follwing publication. Mainly, the publication shows results of NTGA2 for optimisation in multiobjective Traveling Thief Problem and MS-RCPSP.
Myszkowski P.B., Laszczyk M.,
"Diversity based selection for many-objective evolutionary optimisation problems with constraints",
Information Sciences 546 (2021) 665–700,
https://doi.org/10.1016/j.ins.2020.08.118
|
More detailed data about NTGA2 applied to 5-objective optimisation have been presented in publication:
Myszkowski P.B., Laszczyk M.,
"Investigation of benchmark dataset for many–objective Multi–Skill Resource Constrained Project Scheduling Problem",
Applied Soft Computing
https://doi.org/10.1016/j.asoc.2022.109253
abstract:
The paper presents a redefinition of Multi–Skill Resource–Constrained Project
Scheduling Problem as a many-objective optimisation problem. In consequence
it brings the problem closer to the real-world applications. Five objectives have
been defined: standard cost and duration, average cashflow, average usage of
resources and skill overuse measure. In the paper, a short survey (years 2015-2021) of MS–RCPSP solving methods has been presented to summarize its usage. Moreover, results of investigation of many–objective MS–RCPSP for classic
(greedy algorithm, NTGA-II), single objective (decomposition based) (DEGR)
and state-of-the-art methods (NTGA2) have been presented. Additionally, results are analysed using multi-objective quality measures (such as PFS, HV,
IGD) to verify the efficiency of used methods. Finally, the paper is concluded
by summary, and proposition of future work.
keywords: Many-Objective optimization, MS-RCPSP, dataset, Benchmark
|
Antkiewicz M., Myszkowski P.B.,
"A new selection operator in Balanced Non-dominated Tournament Genetic Algorith (B-NTGA) for multi- and many-objective optimization with constraints",
[19.02.2023] submitted to Applied Soft Computing
abstract:
The paper presents a new balanced selection operator applied to Balanced Non-dominated Tournament Genetic Algorithm (B-NTGA) to solve multi- and many-objective optimization problems. The main motivation is to make B-NTGA more efficient in exploring Pareto Front Approximation (PFa), focusing on ”gaps” and reducing some PFa regions’ sampling too frequently. Such a balancing mechanism allows B-NTGA to be more adaptive and focus on less explored PFa regions. The proposed B-NTGA is investigated on two benchmark multi- and many-objective optimization real-world problems, like Thief Traveling Problem and Multi-Skill Resource-Constrained Project Scheduling Problem. The results of experiments show that B-NTGA has a higher efficiency and better performance than state-of-the-art methods.
keywords: multi-objective optimization, many-objective optimization, domination relation, evolutionary
computation, balanced selection
The approximated Pareto Front gained by B-NTGA is better and more 'balanced' than NTGA2 (see Figure below).
Each sphere presented in Figure (above) represents the single individual (solution) stored in the 'archive' (after 2000’th generations), where the sphere’s radius reflects its selection count. High-radius spheres in the middle area of the NTGA2’s PF mark the larger “gaps”.
|
detailed data for many-objective MS-RCPSP
small instances (6 instances)
The small iMOPSE dataset prepared specially for educational usage and investigation of optimisation methods.
The
small dataset (~4,3Kb) inludes 6 small instances with 10-15 resources.
|
Notice: most of small iMOPSE dataset instances could be solved by bruteforce (results are given in paper).
Therefore, True Pareto Front (TPF) is known, and all many-objective methods could be investigated and compared to TPF.
|
Fig. 1. Example of 5-objective optimisation for small instance (10_7_10_7_2).
Detailed results for investigated method NTGA2 --
gained Pareto Fronts (~800kB).
All graphs of 5-objective optimisations for three methods can be found --
all graphs (~6,4MB).
iMOPSE instances (36 instances)
The iMOPSE benchmark dataset is full dataset to investigate optimisation methods and compare results.
The
iMOPSE dataset (~65Kb) includes 36 instances of MS-RCPSP problem with 100-200 resources.
Fig. 1. Example of 5-objective optimisation NTGA2 results for MS-RCPSP
Approximated Pareto Fronts for all imopse instances
approx_pf.zip (ZIP, ~202MB) using all examined methods (NTGA2, Theta-DEA and U-NSGA-III).
Adittionally, all graphs of approximations pareto fronts for all imopse instances
graphs.zip (ZIP, ~105MB).
