Applications of Combinatorial Optimization, 2nd Edition

Preface

This revised and updated second edition of Applications of Combinatorial Optimization is the third and last volume of the Combinatorial Optimization series. It deals with the applications of combinatorial optimization. These are what fully justify the relevance of this scientific domain and widen its fundamental concepts. The subjects of this volume deal with various and diverse problems, more or less classic, but still relevant today. Its chapters are devoted to various problems such as:

– airline crew scheduling;

– transport of goods and planning;

– scheduling of tasks in parallel programming;

– applications of polyhedral combinatorics;

– production planning;

– modeling and optimization of network synthesis and design problems;

– parallel optimization;

– multicriteria task assigning to heterogenous processors, and its robustness.

In Chapter 1, the problem of optimizing the rotation of airline crews is dealt with. This problem consists of covering, with minimum cost, all the flights of the company scheduled in a given time window, with teams made up from cockpit personnel (pilots, copilots) and cabin personnel (hostesses, stewards). With a frequency of several days (of the order of one week), each team leaves the base to which it is assigned, carries out a certain number of flights sequentially, and comes back to the base (this is what we call “turnover”). Drawing up the team turnover for an airline is highly restricted by international, national and internal work regulations, ...