Genetic algorithm for the personnel assignment problem with multiple objectives

Date

2007-02-01

Author

Toroslu, İsmail Hakkı

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

135
views

0
downloads

The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the standard assignment problem, any node in one partition can be matched with any node in the other partition without any restriction. In this paper, variations of the standard assignment problem are defined with matching constraints by introducing structures in the partitions of the bipartite graph, and by defining constraints on these structures. According to the first constraint, the matching between the two partitions should respect the hierarchical-ordering constraints defined by forest and level graph structures produced by using the nodes of the two partitions respectively. In order to define the second constraint, the nodes of the partitions of the bipartite graph are distributed into mutually exclusive sets. The set-restriction constraint enforces the rule that in one of the partitions all the elements of each set should be matched with the elements of a set in the other partition. Even with one of these constraints the assignment problem becomes an NP-hard problem. Therefore, the extended assignment problem with both the hierarchical-ordering and set-restriction constraints becomes an NP-hard multi-objective optimization problem with three conflicting objectives; namely, minimizing the numbers of hierarchical-ordering and set-restriction violations, and maximizing the summation of the weights of the edges of the matching. Genetic algorithms are proven to be very successful for NP-hard multi-objective optimization problems. In this paper, we also propose genetic algorithm solutions for different versions of the assignment problem with multiple objectives based on hierarchical and set constraints, and we empirically show the performance of these solutions.

Subject Keywords

Genetic algorithm, Multiobjective optimization problem, NP-complete, Set constraint, Hierarchical-ordering constraint, Matching, Bipartite graph, Assignment problem

URI

https://hdl.handle.net/11511/42227

Journal

INFORMATION SCIENCES

DOI

https://doi.org/10.1016/j.ins.2006.07.032

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Genetic algorithm for personnel assignment problem with multiple objectives Arslanoğlu, Yılmaz; Toroslu, İsmail Hakkı; Department of Computer Engineering (2006) This thesis introduces a multi-objective variation of the personnel assignment problem, by including additional hierarchical and team constraints, which put restrictions on possible matchings of the bipartite graph. Besides maximization of summation of weights that are assigned to the edges of the graph, these additional constraints are also treated as objectives which are subject to minimization. In this work, different genetic algorithm approaches to multi-objective optimization are considered to solve th...
Optimization of the array geometry for direction finding Özaydın, Seval; Koç, Seyit Sencer; Tanık, Yalçın; Department of Electrical and Electronics Engineering (2003) In this thesis, optimization of the geometry of non-uniform arrays for direction finding yielding unambiguous results is studied. A measure of similarity between the array response vectors is defined. In this measure, the effects of antenna array geometry, source placements and antenna gains are included as variable parameters. Then, assuming that the antenna gains are known and constant, constraints on the similarity function are developed and described to result in unambiguous configurations and maximum r...
Genetic algorithm for the multiple-query optimization problem Bayir, Murat Ali; Toroslu, İsmail Hakkı; Coşar, Ahmet (2007-01-01) Producing answers to a set of queries with common tasks efficiently is known as the multiple-query optimization (MQO) problem. Each query can have several alternative evaluation plans, each with a different set of tasks. Therefore, the goal of MQO is to choose the right set of plans for queries which minimizes the total execution time by performing common tasks only once. Since MQO is an NP-hard problem, several, mostly heuristics based, solutions have been proposed for solving it. To the best of our knowle...
Intelligent design objects applied to the spatial allocation problem Zaratiegui Fernandez, Javier Ignacio; Sorguç, Arzu; Computational Design and Fabrication Technologies in Department of Architecture (2014) This thesis approaches the spatial allocation problem as a multi-objective optimization problem. It proposes the use of Intelligent Design Objects (IDO) model to help designers with this task. Solutions are generated and evaluated, according the user defined criteria. Iterative improvement is proposed as a help to visualize candidate solutions and conceive the desired spatial relations. By defining the criteria and rating it numerically, both designer and client are able compare the solutions obtained. The ...
Continuous optimization approaches for clustering via minimum sum of squares Akteke-Ozturk, Basak; Weber, Gerhard Wilhelm; Kropat, Erik (2008-05-23) In this paper, we survey the usage of semidefinite programming (SDP), and nonsmooth optimization approaches for solving the minimum sum of squares problem which is of fundamental importance in clustering. We point out that the main clustering idea of support vector clustering (SVC) method could be interpreted as a minimum sum of squares problem and explain the derivation of semidefinite programming and a nonsmooth optimization formulation for the minimum sum of squares problem. We compare the numerical resu...

Citation Formats

İ. H. Toroslu, “Genetic algorithm for the personnel assignment problem with multiple objectives,” INFORMATION SCIENCES, pp. 787–803, 2007, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/42227.