Combinatorial optimization problems in planning and decision making. Theory and applications (Q1727934)

This book, comprising nine chapters, studies combinatorial optimization methods in the context of mathematical modeling of planning and decision making problems. The book begins with a brief introduction to combinatorial optimization, followed by a chapter on optimal scheduling for a single machine, for which two efficient heuristic algorithms are presented with examples. The next chapter extends the study to several machines working in parallel and several algorithms for the solution of this problem are presented. The detailed fourth chapter contains a key theoretical result, namely the description of an efficient algorithm for the general problem which is known to be NP-hard. The authors also describe some conditions under which the proposed algorithm is polynomial. The fifth chapter considers the case of minimization of the total earliness or tardiness in relation to the due date for a single machine, which is in the general case an intractable problem. The authors develop an approximation algorithm which can solve this problem efficiently. The next chapter extents these results to a more general case consisting of several identical machines, while the seventh chapter considers the addition of precedence relations between the tasks. The last two chapters, consisting of approximately one third of the book, present an overview of the known models, techniques and software for the solution of optimal planning problems. The comparison highlights in great detail the advantages and limitations of each method, including the results of computational experimentation. Each chapter of this very interesting book concludes with a list of relevant references.