Scheduling Unrelated Parallel Machines

A bank of parallel machines is an important setting in computer science. When dealing with parallel machines, the minimization of the maximal load (makespan) becomes an objective of significant interest. In practice one often has to balance the load on parallel machines, e.g., on computer processors. By minimizing the makespan an excellent load balance can be ensured. The book considers the problem of scheduling independent jobs on unrelated parallel machines without preemption. The problem belongs to the most difficult problems of theoretical computer science. The first part gives an introduction to the scheduling theory. Next nine new methods designed to solve the scheduling problem are introduced. The algorithms proposed here use various algorithmic techniques like network flows, linear programming, column generation, branch-and-price, cutting planes, or randomized rounding. The last part presents a comprehensive evaluation of eighteen methods, new and old ones, using algorithmic approaches discussed earlier. The book is addressed to all interested in new results in the scheduling theory, especially to computer scientists, operations research analysts, and industrial engineers.