×

A new class of parallel scheduling algorithms. (English) Zbl 1245.90028

Wrocław: Oficyna Wydawnicza Politechniki Wrocławskiej (ISBN 978-83-7493-564-7/pbk). 280 p. (2010).
This monograph, which has 280 pages, deals with the solution of different types of scheduling problems in parallel computation environments such as multiprocessor computers, clusters or distributed calculation nodes in networks. In particular, algorithms are applied which use various parallelization technologies, starting from multiple calculation threads up to distributed calculation processes.
The first part gives an introduction to parallelism and job scheduling. This part consists of three chapters. Chapter 1 presents theoretical and practical basics of parallel computations such as performance metrics for parallel algorithms, different parallel architectures and gives some introductory comments on parallelization strategies for metaheuristics. Chapter 2 surveys the methodologies of parallelizing metaheuristics. It first discusses parallel local search methods and then parallel population-based algorithms. Then, in Chapter 3, some basic introduction into the different types of scheduling problems is given.
The core of the book are Parts II and III which are based on the research of the author. While Part II (Chapters 4–7) deals with single-walk parallelizations, Part III considers multi-walk parallelizations.
Chapter 4 discusses the methodology of transferring local search methods using huge neighborhoods into a parallel environment. The approach is discussed on several single machine problems. Chapter 5 introduces a methodology for the effective cost function determination for the job shop scheduling problem in a parallel computation environment. The PRAM (parallel random access machine) model is applied to analyze theoretically the efficiency of the algorithm. Chapter 6 presents a single-walk approach to the problem of determining a neighborhood and showing how to search it in a parallel environment. The approach is illustrated using the flexible job shop problem. At the end of Part II, Chapter 7 gives some new theoretical results in single-walk exploration.
Chapter 8 presents a methodology of designing a parallel algorithm based on memetic search. This approach is illustrated on a single machine scheduling problem with earliness and tardiness penalties. A population-based approach is given in Chapter 9 which is described on the single machine scheduling problem with setup times and minimizing total weighted tardiness. It uses the idea of concurrent local minima searching. Chapter 10 describes a methodology of transforming a sequential branch and bound algorithm into a parallel algorithm. Both the variants of an exact as well as a restricted branch and bound algorithm (i.e., as a heuristic) are treated. Load balancing of processors is discussed. For describing this approach, the single machine problem of minimizing total weighted tardiness is considered. Chapter 11 discusses the methodology of designing a parallel simulated annealing algorithm. Two approaches are considered, namely a classical multiple-walk algorithm with parallel generation of the trajectories (used for the flow shop problem with makespan minimization) and a more expanded algorithm using additional backtrack jumps, multi-moves and temperature steering which allows one to intensify and diversify the search process (used for the flow shop problem with the total flow time criterion). Chapter 12 discusses a parallel scatter search, again applied to the flow shop problem. In some cases, the effect of a superlinear speedup has been observed. Then, in Chapter 13, a multi-walk parallelization of the island model based genetic algorithm is given, applied to the flow shop problem with the total flow time criterion. The approach makes use of the multi-step crossover fusion operator (MSXF) for the inter-island communication. It turned out that parallelization increases the quality of the solutions when compared with a sequential algorithm. Chapter 14 discusses two double-level metaheuristic optimization algorithms, which are applied to the flexible job shop problem with minimizing the makespan. The algorithms suggested have two major modules: a machine selection module and an operation scheduling module. Finally, in Chapter 15, a new methodology of a parallel tabu search using a cooperation between concurrently running searching threads is given. It has been tested on the flow shop problem, and it has also been applied to a roadwork scheduling problem. Chapter 16 gives some final remarks including some open problems in this area.
This book is interesting both for advanced students as well as for researchers and professionals working in the field of discrete optimization or related areas.

MSC:

90B35 Deterministic scheduling theory in operations research
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
68W10 Parallel algorithms in computer science
68W40 Analysis of algorithms
PDFBibTeX XMLCite