×

Particle swarm optimization for scheduling problems. (English) Zbl 1190.90004

Berichte aus der Wirtschaftsinformatik. Aachen: Shaker Verlag; Hamburg: Univ. Hamburg (Diss.) (ISBN 978-3-8322-9058-0/pbk). xxvi, 225 p. (2010).
From the introduction: The research presented in this thesis aims at adapting particle swarm optimization to combinatorial optimization problems. Based on own experiments and approaches proposed in the literature we develop a general framework which incorporates particle swarm essentials and is applicable to (all) combinatorial optimization problems. We validate the framework by extensive computational experiments on two well-known scheduling problems. Furthermore, we use the framework to develop a search methodology for an intelligent decision support system.
Beside Chapter 1, Chapter 2 is also of an introductory manner. In Section 2.1 it provides an introduction to decision making. In Section 2.2 we provide an introduction to optimization problems in general and to combinatorial optimization problems in particular. In Section 2.3 we discuss complexity theoretical aspects of solving (combinatorial) optimization problems. We review the Turing machine as a theoretical concept in complexity theory and discuss important classes of problems. We will see that for NP-hard problems no efficient algorithms are known. How those problems can be tackled is subject of Section 2.4. We provide a short overview of approximation algorithms, heuristics, and metaheuristics. In Sections 2.5.1 and 2.5.2 we review two main variants of metaheuristic approaches, namely local search and evolutionary computation. We develop a general framework for evolutionary computation algorithms which we utilize in this thesis. In Section 2.5.3 we discuss the No Free Lunch theorems and their implications for the development of optimization algorithms. We conclude this chapter with a review of the concept of a fitness landscape and its analysis in Section 2.5.4.
Chapter 3 is devoted to particle swarm optimization. We first review the particle swarm optimizer in its canonical form (Section 3.1), its most significant changes proposed (Section 3.4), and we illustrate the dynamics of the system (Section 3.2). In Section 3.3 we review neighborhood structures as one approach to tackle the problem of premature convergence. In Section 3.5 we discuss the adaptation of particle swarm optimization to combinatorial optimization problems. We provide an extensive review of the related literature and incorporate the swarm intelligence paradigm into the general framework for evolutionary computation algorithms.
In Chapters 4, 5, and 6 we use the proposed particle swarm optimization algorithm to solve three combinatorial scheduling problems.
In Chapter 4 we consider the no-wait (continuous) flow-shop scheduling problem. It consists of a set of jobs which have to be processed in an identical order on a given number of machines without interrupting the processing of any job once it has started on the first machine. We analyze the fitness landscape of problem instances and use the results to design a competitive algorithm that is able to improve some of the results reported in the literature. Furthermore we investigate the importance of different algorithm components.
In Chapter 5 we consider the non-preemptive single mode resource-constrained project scheduling problem with the objective to minimize the total project duration (makespan). It consists in scheduling a set of activities with deterministic processing times, resource requirements, and precedence relations between activities. The aim is to find a schedule with minimum makespan (total project duration) respecting both precedence relations and resource limits. We use the results of the fitness landscape analysis to design a competitive particle swarm algorithm that is able to improve some of the results reported in the literature. Furthermore we investigate how the used topology influences the performance of the particle swarm optimizer.
In Chapter 6 we investigate the development of an intelligent decision support system to aid in solving the task of crew scheduling. Staff or crew scheduling consists of the assignment of appropriate employees to the appropriate workstations while considering various constraints. This research area lies at the interface between operational research and computer science and involves understanding the real-world system, the modeling of such a system and the development of a search methodology for a decision support system to aid the decision maker in the task of crew scheduling.
In the final Chapter 7 of this work we draw some conclusions.

MSC:

90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: Link