Scheduling Unrelated Parallel Machines- Algorithms Complexity and Performance

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 oftenhas to balance the load on parallel machines e.g. on computer processors.By minimizing the makespan an excellent load balance can be ensured. Thebook considers the problem of scheduling independent jobs on unrelatedparallel machines without preemption. The problem belongs to the mostdifficult problems of theoretical computer science. The first part gives anintroduction to the scheduling theory. Next nine new methods designed tosolve the scheduling problem are introduced. The algorithms proposed hereuse various algorithmic techniques like network flows linear programmingcolumn generation branch-and-price cutting planes or randomizedrounding. The last part presents a comprehensive evaluation of eighteenmethods new and old ones using algorithmic approaches discussed earlier.The book is addressed to all interested in new results in the schedulingtheory especially to computer scientists operations research analysts andindustrial engineers.