TY  - BOOK
AU  - Brucker,Peter
TI  - Scheduling algorithms / 
SN  - 9783540695158 (alk. paper)
U1  - 005.1   22
PY  - 2007///
CY  - Berlin ; ,  New York : 
PB  -  Springer, 
KW  - Computer capacity
KW  -  Planning
KW  - Production scheduling
KW  - Computer algorithms
N1  - 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
N2  - 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
ER  -