Scheduling algorithms / Peter Brucker.

Includes bibliographical references and index.

Preface -- Classification of Scheduling Problems -- Scheduling Problems -- Job Data -- Job Characteristics -- Machine Environment -- Optimality Criteria -- Examples -- Some Problems in Combinatorial Optimization -- Linearand Integer Programming -- Transshipment Problems -- The Maximum Flow Problem -- Bipartite Matching Problems -- The Assignment Problem -- Arc Coloring of Bipartite Graphs -- Shortest Path Problems and Dynamic Programming -- Computational Complexity -- The Classes <$>{\cal P}<$> and <$>{\cal N}{\cal P}<$> -- <$>{\cal N}{\cal P}<$>-complete and <$>{\cal N}{\cal P}<$>-hard Problems -- Simple Reductions Between Scheduling Problems -- Living with <$>{\cal N}{\cal P}<$>-hard Problems -- Local Search Techniques -- Branch-and-Bound Algorithms -- Single Machine Scheduling Problems -- Minimax Criteria -- Lawler's Algorithm for 1 prec fmax -- 1 -- Maximum Lateness and Related Criteria -- Total Weighted Completion Time -- 1 tree <$>\sum<$>wjCj -- 1 sp-graph <$>\sum<$>wjCj -- Weighted Number of Late Jobs -- 1 rj; pj = 1 <$>\sum<$>wjUj -- 1 pj = 1 <$>\sum<$>wjUj -- 1 <$>\sum<$>Uj -- 1 rj; pmtn <$>\sum<$>wjUj -- Total Weighted Tardiness -- Problems with Release Times and Identical Processing Times -- 1 rj; pj = p <$>\sum<$>wjUj -- 1 rj; pj = p <$>\sum<$>wjCj and 1 rj; pj = p <$>\sum<$>Tj -- Complexity of Single Machine Problems -- Parallel Machines -- Independent Jobs -- Identical Machines -- Uniform Machines -- Unrelated Machines -- Jobs with Precedence Constraints -- P tree; pi = 1 Lmax-Problems -- Problem P2 prec; pi = 1 Lmax -- Complexity Results -- Shop Scheduling Problems -- The Disjunctive Graph Model -- Open Shop Problems -- Arbitrary Processing Times -- Unit Processing Times -- Flow Shop Problems -- Minimizing Makespan -- Job Shop Problems -- Problems with Two Machines -- Problems with Two Jobs.A Geometric Approach -- Job Shop Problemswith Two Machines -- A Branch-and-Bound Algorithm -- Applying Tabu-Search to the Job Shop Problem -- Mixed Shop Problems -- Problemswith Two Machines -- Problemswith Two Jobs -- Complexityof Shop Scheduling Problems -- Due-Date Scheduling -- Problem 1 dopt <$>\sum<$>wi L¿(i) + w0 c d -- Problem 1 -- Problem 1 -- Problem 1 -- Problem 1 -- Problem 1 -- Problem 1 -- Batching Problems -- Single Machine s-Batching Problems -- Single Machine p-Batching Problems -- The Unbounded Model -- The Bounded Model -- Complexity Results for Single Machine Batching Problems -- Changeover Times and Transportation Times -- Single Machine Problems -- Problems with Parallel Machines -- General Shop Problems -- Multi-Purpose Machines -- MPM Problems with Identical and Uniform Machines -- MPM Problems with Shop Characteristics -- Arbitrary Processing Times -- Unit Processing Times -- Complexity Results -- Multiprocessor Tasks -- Multiprocessor Task Systems -- Shop Problems with MPT: Arbitrary Processing Times -- Shop Problems with MPT: Unit Processing Times -- Multi-Mode Multiprocessor-Task Scheduling Problems -- Complexity Results.

Besides scheduling problems for single and parallel machines and shop scheduling problems, this book covers advanced models involving due-dates, sequence dependent changeover times and batching. Discussion also extends to multiprocessor task scheduling and problems with multi-purpose machines. Among the methods used to solve these problems are linear programming, dynamic programming, branch-and-bound algorithms, and local search heuristics. The text goes on to summarize complexity results for different classes of deterministic scheduling problems.

1