Search

This work reviews the most important results regarding the use of the α-point in Scheduling Theory. It provides a number of different LP-relaxations for scheduling problems and seeks to explain their polyhedral consequences. It also explains the concept of the α-point and how the conversion algorithm works, pointing out the relations to the sum of the weighted completion times. Lastly, the book explores the latest techniques used for many scheduling problems with different constraints, such as release dates, precedences, and parallel machines. This reference book is intended for advanced undergraduate and postgraduate students who are interested in scheduling theory. It is also inspiring for researchers wanting to learn about sophisticated techniques and open problems of the field.

This textbook presents a wide range of tools for a course in mathematical optimization for upper undergraduate and graduate students in mathematics, engineering, computer science, and other applied sciences. Basic optimization principles are presented with emphasis on gradient-based numerical optimization strategies and algorithms for solving both smooth and noisy discontinuous optimization problems. Attention is also paid to the difficulties of expense of function evaluations and the existence of multiple minima that often unnecessarily inhibit the use of gradient-based methods. This second edition addresses further advancements of gradient-only optimization strategies to handle discontinuities in objective functions. New chapters discuss the construction of surrogate models as well as new gradient-only solution strategies and numerical optimization using Python. A special Python module is electronically available (via springerlink) that makes the new algorithms featured in the text easily accessible and directly applicable. Numerical examples and exercises are included to encourage senior- to graduate-level students to plan, execute, and reflect on numerical investigations. By gaining a deep understanding of the conceptual material presented, students, scientists, and engineers will be able to develop systematic and scientific numerical investigative skills.

Sebastian Goderbauer zeigt, dass das Einteilen von Wahlkreisen für die Deutsche Bundestagswahl aufgrund der gesetzlichen Vorgaben als ein mathematisches Optimierungsproblem angesehen werden kann. Er gibt eine detaillierte Komplexitätsanalyse des zugrundeliegenden Partitionsproblems an und untersucht, welches die beste Wahlkreisanzahl für Deutschland ist. Der Autor entwickelt einen optimierungsbasierten Algorithmus zum Einteilen von Wahlkreisen und wendet diesen auf deutsche Bevölkerungsdaten an.

This monograph deals with a general class of solution approaches in deterministic global optimization, namely the geometric branch-and-bound methods which are popular algorithms, for instance, in Lipschitzian optimization, d.c. programming, and interval analysis.It also introduces a new concept for the rate of convergence and analyzes several bounding operations reported in the literature, from the theoretical as well as from the empirical point of view. Furthermore, extensions of the prototype algorithm for multicriteria global optimization problems as well as mixed combinatorial optimization problems are considered. Numerical examples based on facility location problems support the theory. Applications of geometric branch-and-bound methods, namely the circle detection problem in image processing, the integrated scheduling and location makespan problem, and the median line location problem in the three-dimensional space are also presented.The book is intended for both researchers and students in the areas of mathematics, operations research, engineering, and computer science.

Manufacturing systems work with scarce resources in dynamic environments. Managers need to assign production facilities to parallel activities, respecting operational constraints and deadlines while keeping costs low. Old scheduling approaches are inadequate when a task both requires a set of different resources and a trade-off between objectives. More sophisticated models and algorithms are needed by these managers. This book provides robust methods for achieving effective resource allocation. It also solves problems such as resource levelling, sizing of machines and production layouts, cost optimization in production planning and scheduling that occur daily and often generate cost overruns. The quantitative methods used cover both mathematical programming and algorithms, leading to high quality solutions. Details of experimentation put these techniques in a practical perspective. This book is a valuable resource for postgraduate students and researchers in business, engineering or computer science.

In 1995 the Handbook of Global Optimization (first volume), edited by R. Horst, and P.M. Pardalos, was published. This second volume of the Handbook of Global Optimization is comprised of chapters dealing with modern approaches to global optimization, including different types of heuristics. Topics covered in the handbook include various metaheuristics, such as simulated annealing, genetic algorithms, neural networks, taboo search, shake-and-bake methods, and deformation methods. In addition, the book contains chapters on new exact stochastic and deterministic approaches to continuous and mixed-integer global optimization, such as stochastic adaptive search, two-phase methods, branch-and-bound methods with new relaxation and branching strategies, algorithms based on local optimization, and dynamical search. Finally, the book contains chapters on experimental analysis of algorithms and software, test problems, and applications.

Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872-1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed con­ jecture that P -=/= NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of ap­ proximation algorithms as it stands today. It is reasonable to expect the picture to change with time. This book is divided into three parts. In Part I we cover combinato­ rial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected - nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly cat­ egorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving them.