Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Using Genetic Algorithms for Large Scale Optimizationof Assignment, Planning and Rescheduling Problems
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

There has always been a need to solve real-life large-scale problems, suchas efficiently allocating limited resources, and other complex and conflicting situations related to combinatorial optimization genre. A class of combinato- rial optimization problems is NP-hard and, among many well-known, several of them are assignment, planning and rescheduling problems. Assignment problems can deal with optimal assignment of teams of collaborating agents; planning problems can be effects-based planning that search for promising plans to get desired end states with minimal cost; rescheduling problems can be multi-criteria optimization of rescheduling resources that modify existing original schedule. These large scale optimization problems are complex with intractable and highly complex search spaces. Currently, there are no known algorithms with polynomial time complexity, which can solve these problems. Genetic Algorithms have been successfully applied to solve many complex optimization problems but not to the specific problems mentioned above.

The aim of the research, presented in this thesis, is to use Genetic Algo- rithms for large scale optimization of assignment, planning and rescheduling problems. More specifically, the contributions of the thesis are to: (i) adapt existing and develop new efficient Genetic Algorithms to solve large scale as- signment problems, and (ii) adapt existing Genetic Algorithms to solve large scale effects-based planning, and multi-objective rescheduling optimization problems.In case of assignment, we solve a team assignment problem and investigate specific regions in a solution space for assignment problems with huge search spaces.

For the team assignment, an existing Genetic Algorithm is adapted and applied for optimal assignment of tasks to teams of collaborating agents. The algorithm is scalable, stable, robust and produces a near optimal solution. The results of the team assignment problem show that the existing Genetic Algorithms are not efficient for optimal assignment of tasks to teams of agents. Hence, to solve larger instances of the problem efficiently, new Genetic Algo- rithms are developed with emphasis on the construction of crossover opera- tors. Since teams assignment can be multi-criteria, a multi-objective model is constructed and two widely used multi-objective evolutionary algorithms are applied. Further, for the assignment problems with huge search spaces, an existing Genetic Algorithm is adapted to extract possible combinations of input parameters from a specified solution space region. To solve the large scale effects-based planning, a multi-objective optimization problem is formu- lated for the evaluation of operational plans and a multi-objective Genetic Algorithm is adapted and applied to the problem. The results show that the suggested algorithm is much more efficient than A*. For the rescheduling problem, a multi-objective optimization model for rescheduling of resources is proposed and a multi-objective Genetic Algorithm is adapted and applied to obtain the Pareto-optimal solutions.

The research presented in this thesis confirms that Genetic Algorithms can be used for large scale assignment, planning and rescheduling problems since they have shown to be suitable in solving these problems efficiently.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology , 2014. , 202 p.
Series
TRITA-ICT-ECS AVH, ISSN 1653-6363 ; 14:06
National Category
Computer Systems
Research subject
SRA - ICT
Identifiers
URN: urn:nbn:se:kth:diva-143671ISBN: 978-91-7595-047-1 (print)OAI: oai:DiVA.org:kth-143671DiVA: diva2:708381
Public defence
2014-04-25, Sal D, Forum, Isafjordsgatan 39, Kista, Stockholm, 13:00 (English)
Opponent
Supervisors
Note

QC 20140328

Available from: 2014-03-28 Created: 2014-03-27 Last updated: 2014-03-28Bibliographically approved
List of papers
1. Optimization of Task Assignment to Collaborating Agents
Open this publication in new window or tab >>Optimization of Task Assignment to Collaborating Agents
2011 (English)In: IEEE SSCI 2011 - Symposium Series on Computational Intelligence - CISched 2011, Paris, France: IEEE Computational Intelligence Society , 2011, 17-24 p.Conference paper, Published paper (Refereed)
Abstract [en]

The classic task assignment problem (AP) assigns m agents to n tasks, where each task is assigned to exactly one agent. This problem and many of its variations, including the case where a task is assigned to a group of agents working independently, have been discussed extensively in the literature. We consider a specific class of task assignment problems where each task is assigned to a group of collaborating agents that work as a team. Thus, changing one of the group members may have a vital impact on the output of the group. We assume that each agent has a set of capabilities and each task has certain requirements. The objective is to assign agents to teams such that the gain is maximized.

We suggest a Genetic Algorithm (GA) for finding a near optimal solution to this class of task assignment problems. To the best of our knowledge, this class of APs has not been considered in the literature, probably due to the difficulty of evaluating the performance of a team of agents. Recently, we have developed a formal method for measuring performance of a team which is used in this paper to formulate the objective function of our GA. We analyze the quality of the obtained solution by comparing the result of our GA with (a) the exact solution of some smaller problems, and (b) with the results of the exact solution of specific cases that can be obtained by the Hungarian algorithm. We provide experimental results on efficiency, stability, robustness and scalability of the solution obtained by our GA.

Place, publisher, year, edition, pages
Paris, France: IEEE Computational Intelligence Society, 2011
Keyword
Task Assignment Problem, Genetic Algorithms, Evolutionary Algorithms, Optimization
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-45938 (URN)10.1109/SCIS.2011.5976547 (DOI)2-s2.0-80052082446 (Scopus ID)978-161284196-0 (ISBN)
Conference
IEEE Symposium on Computational Intelligence in Scheduling. Paris, 11 April 2011 - 15 April 2011
Note

QC 20111102

Available from: 2011-11-01 Created: 2011-11-01 Last updated: 2014-03-28Bibliographically approved
2. Efficient Genetic Algorithms for Optimal Assignment of Tasks to Teamsof Agents
Open this publication in new window or tab >>Efficient Genetic Algorithms for Optimal Assignment of Tasks to Teamsof Agents
(English)Manuscript (preprint) (Other academic)
Abstract [en]

The problem of optimally assigning agents (resources) to a given set oftasks is known as the Assignment Problem (AP). The classical AP and manyof its variations have been discussed extensively in the literature. In thispaper, we present a specific class of Assignment Problems (APs) in which eachtask is assigned to a group of collaborating agents. In this AP, collaborationof all agents is required to perform the task and an agent cannot individuallydo it.

We present a mathematical model for this type of AP and use GeneticAlgorithm (GA) to solve the model, since there are no known polynomial timealgorithms for this class of APs. We show that for larger instances of the problem,the GA with one-point crossover operator cannot efficiently find nearoptimalsolutions. In general, the efficiency of the GA depends on the choiceof genetic operators (selection, crossover, mutation) and associated parameters.In order to design an efficient GA for finding near optimal assignment oftasks to collaborative teams, we focus on construction of crossover operators.We compare and analyze the efficiency of several well-known crossover operatorssuch as one-point, two-point, three-point, position-based and order-basedcrossover operators. We suggest modifications to these operators by addinga shuffled repair list to them and show that their efficiency is enhanced forsolving the presented AP. Furthermore, we introduce two new crossover operators,team-based and team-based shuffled list crossover operators, whichsolve large-scale models of our AP efficiently.

Keyword
Genetic algorithms, Combinatorial optimization, Evolutionary computations, Heuristics, Large scale optimization, Team assignment problem
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-143762 (URN)
Note

QS 2014

Available from: 2014-03-27 Created: 2014-03-27 Last updated: 2014-03-28Bibliographically approved
3. Optimization of assignment of tasks to teams using multi-objective metaheuristics
Open this publication in new window or tab >>Optimization of assignment of tasks to teams using multi-objective metaheuristics
2013 (English)In: GECCO 2013 - Proceedings of the 2013 Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery (ACM), 2013, 103-104 p.Conference paper, Published paper (Refereed)
Abstract [en]

A highly interesting but not thoroughly addressed optimization problem is a variation of the Assignment Problem (AP) where tasks are assigned to groups of collaborating agents (teams). In this paper, we address this class of AP as a bi-objective optimization problem, in which the cost is minimized and the quality is maximized. To solve the model, we adopt Non-dominated Sorting Genetic Algorithm-II (NSGAII) and Strength Pareto Evolutionary Algorithm 2 (SPEA2). We conduct several experiments on problems with varying sizes to compare the NSGA-II and SPEA2 algorithms.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2013
Keyword
Multi-objective optimization, combinatorial optimization, metaheuristics, assignment problem
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-125914 (URN)10.1145/2464576.2464624 (DOI)2-s2.0-84882367332 (Scopus ID)978-1-4503-1964-5 (ISBN)
Conference
15th Annual Conference on Genetic and Evolutionary Computation, GECCO 2013; Amsterdam; Netherlands; 6 July 2013 through 10 July 2013
Note

QC 20140128

Available from: 2013-08-16 Created: 2013-08-16 Last updated: 2014-03-28Bibliographically approved
4. Using Genetic Algorithms for investigating specific regions of the solution space
Open this publication in new window or tab >>Using Genetic Algorithms for investigating specific regions of the solution space
2011 (English)In: Proceedings of the 2011 African Conference on Software Engineering and Applied Computing (ACSEAC 2011), 2011Conference paper, Published paper (Refereed)
Abstract [en]

In many practical cases decision makers are interested to understand the whole solution space, including possible outliers. By outlier we mean there is a solution that is theoretically possible, though with very low probability that it occurs. In many combinatorial problems, this is a very challenging task. During the past decade, the Data Farming community has done substantial work on developing methods and techniques for better understanding of the solution space. The data farming community has also looked at the design of experiments and used Latin hypercube (LH) techniques for this purpose. The LH is proven to be one of the important sampling methods for selecting a representative subset of the input space. In this paper, we consider a company X that wants to outsource m subprojects of a given project P. We assume that there are n potential subcontractors for each subproject. Thus, there will be n^m ways to assign the subprojects to the potential subcontractors. The project manager is interested to find those assignments that complete the project within a given time and a given cost frame. An exhaustive examination of all assignments is not feasible, if m and n are big numbers. We propose an objective-based genetic algorithm (GA) for finding the set of assignments that are mapped onto a given subset of the solution space. It means, as opposed to the design of experiment techniques, we start from the solution space and try to find the combinations of the input parameter values that can lead to a specific region of the solution space. By some numerical examples, we show how our GA identifies the set of such feasible assignments.

Keyword
Data Farming, Design of Experiments, Assignment Problem, Genetic Algorithms, Evolutionary Algorithms, Decision-support Systems, Project Management
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-53038 (URN)
Conference
2011 African Conference on Software Engineering and Applied Computing
Note
QC 20111228Available from: 2011-12-21 Created: 2011-12-21 Last updated: 2014-03-28Bibliographically approved
5. Using genetic algorithms in effects-based planning
Open this publication in new window or tab >>Using genetic algorithms in effects-based planning
2013 (English)In: Proceedings of the 2013 IEEE International Conference on Systems, Man, and Cybernetics (SMC), IEEE Computer Society, 2013, 438-443 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we propose a genetic algorithm-based method for evaluation of operational plans within effects-based planning. We formulate the effects-based planning problem as a bi-objective optimization problem, in which the distance from the initial state to the current state (g) and the distance from the current state to the desired end state (h) are minimized. To solve the problem, we adopt Non-dominated Sorting Genetic Algorithm-II (NSGA-II). Considering an expeditionary operation scenario, we simulate a subset of possible plans and present the decision maker with a set of promising plans which are capable of approaching the desired end state efficiently. In order to discuss the efficiency and effectiveness of the algorithm, we compare the results of NSGA-II with the results of A*. The computational results show that NSGA-II is much more efficient than A* with regard to g. On the other hand A* is a little more effective with regard to h.

Place, publisher, year, edition, pages
IEEE Computer Society, 2013
Series
IEEE International Conference on Systems Man and Cybernetics Conference Proceedings, ISSN 1062-922X
Keyword
Effects-based planning, Genetic algorithms, Optimization, Path planning, Search algorithms
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-139367 (URN)10.1109/SMC.2013.80 (DOI)000332201900074 ()2-s2.0-84893539170 (Scopus ID)978-1-4799-0652-9 (ISBN)
Conference
The 2013 IEEE International Conference on Systems, Man, and Cybernetics, 13-16 Oct. 2013 Manchester, UK
Note

QC 20140128

Available from: 2014-01-10 Created: 2014-01-10 Last updated: 2014-04-24Bibliographically approved
6. Solving Battalion Rescheduling Problem Using Multi-objective Genetic Algorithms
Open this publication in new window or tab >>Solving Battalion Rescheduling Problem Using Multi-objective Genetic Algorithms
Show others...
2013 (English)In: Asiasim 2013: 13th International Conference on Systems Simulation. Proceedings, Singapore, November 6-8, 2013., Springer Berlin/Heidelberg, 2013, 93-104 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we consider the problem of rescheduling human resources in a battalion where new activities are assigned to the battalion by higher headquarters, requiring modification of an existing original schedule. The problem is modeled as a multi-criteria optimization problem with three objectives: (i) maximizing the number of tasks that are performed, (ii) minimizing the number of high-priority tasks that are missed, and (iii) minimizing the difference between the original schedule and the modified one. In order to solve the optimization model, we adopt Non-dominated Sorting Genetic Algorithm-II (NSGA-II). The accuracy of NSGA-II in this context is verified by considering a small-sized problem where it is easy to verify solutions. Furthermore, we consider a realistic problem instance for a battalion with 400 agents and 66 tasks in the initial schedule. We present the computational result of rescheduling when unpredictable activities emerge.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
Series
Communications in Computer and Information Science, ISSN 1865-0929 ; 402
Keyword
Battalion rescheduling, Multi-objective optimization, Genetic algorithms
National Category
Computer Science Computer Science
Identifiers
urn:nbn:se:kth:diva-139366 (URN)10.1007/978-3-642-45037-2_9 (DOI)2-s2.0-84893870796 (Scopus ID)978-3-642-45036-5 (ISBN)
Conference
13th International Conference on Systems Simulation. Singapore, November 6-8, 2013
Note

QC 20140128

Available from: 2014-01-10 Created: 2014-01-10 Last updated: 2014-03-28Bibliographically approved

Open Access in DiVA

Thesis(823 kB)2184 downloads
File information
File name FULLTEXT01.pdfFile size 823 kBChecksum SHA-512
02ab394bfbe374932628dcababd010b78a77ea2eb4fe9b51f085382bf90a4c587ce1175cb955ae86946348cd90afb04c2a116cd0b34a9b2e17df0bc74b9f9e0b
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Younas, Irfan
By organisation
Software and Computer systems, SCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 2184 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 615 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf