Complex Scheduling

ISBN-13: 9783642239281 / Angielski / Twarda / 2011 / 342 str.

Peter Brucker; Sigrid Knust

Opis

This book presents models and algorithms for complex scheduling problems. Besides resource-constrained project scheduling problems with applications also job-shop problems with flexible machines, transportation or limited buffers are discussed. Discrete optimization methods like linear and integer programming, constraint propagation techniques, shortest path and network flow algorithms, branch-and-bound methods, local search and genetic algorithms, and dynamic programming are presented. They are used in exact or heuristic procedures to solve the introduced complex scheduling problems. Furthermore, methods for calculating lower bounds are described. Most algorithms are formulated in detail and illustrated with examples. In this second edition some errors were corrected, some parts were explained in more detail, and new material has been added. In particular, further generalizations of the RCPSP, additional practical applications and some more algorithms were integrated.

In this revised edition some errors were corrected and new material has been added. In particular, further generalizations of the RCPSP, additional practical applications and some more algorithms were integrated.§Since in recent years commercial and non-commercial solvers for mixed integer linear programs or satisfiability problems became much more efficient, they may be a good alternative for calculating exact (or heuristic) solutions. Hence, we provided new sections on MIP-formulations and a SAT-formulation for the RCPSP. Furthermore, a description of ant colony optimization was added to the section on heuristic methods for solving the RCPSP. The section on lower bounds was augmented by bounds based on Lagrangian relaxation. In connection with the new methods for solving the RCPSP, basic concepts for SAT solvers, Lagrangian relaxation, and ant colony optimization have been added to Chapter 2. We also wrote a new basic section on constraint programming and corrected the input-or-output test.

Recenzje

From the reviews of the second edition:

"This book is a joint production by two veteran researchers in the field of scheduling algorithms. This second edition comes six years after the first and adds close to 60 pages of new material. Most notable is the addition of information on the resource-constrained project scheduling problem (RCPSP), which represents the major focus application of many of the techniques presented in the four sections of the book. ... This book clearly reflects the authors' efforts and is a serious treatment of the topic." (Minette Carl, ACM Computing Reviews, June, 2012)

Spis treści

Scheduling Models.- Algorithms and Complexity.- Resource-Constrained Project Scheduling.- Complex Job-Shop Scheduling.

Blurb

Reihentext:

GOR   The German Society of Operations Research - and its members provide numerous significant contributions to Operations Research/Management Science, with respect to both theory and practice. In order to demonstrate the high standards of these contributions and to make them more easily available, in particular to researchers and practitioners from outside the German-speaking countries, GOR has created this book series. It publishes high-quality monographs and collections of papers on all aspects of Operations Research/Management Science, which deal with a single topic of current interest and originate from or are related to the activities of GOR.

Back cover copy text:

This book presents models and algorithms for complex schedul-
ing problems. Besides resource-constrained project scheduling
problems with applications also job-shop problems with flexible
machines, transportation or limited buffers are discussed. Dis-
crete optimization methods like linear and integer program-
ming, constraint propagation techniques, shortest path and net-
work flow algorithms, branch-and-bound methods, local search
and genetic algorithms, and dynamic programming are present-
ed. They are used in exact or heuristic procedures to solve the
introduced complex scheduling problems. Furthermore, meth-
ods for calculating lower bounds are described. Most algorithms
are formulated in detail and illustrated with examples.

In this second edition some errors were corrected, some parts were
explained in more detail, and new material has been added. In particular, further generalizations of the RCPSP, additional practical applications and some more algorithms were integrated.