Models and Algorithms of Time-Dependent Scheduling

Third Auflage 2026
ISBN: 978-3-662-74753-7
Verlag: Springer

Buch, Englisch, Format (B × H): 155 mm x 235 mm

Reihe: Monographs in Theoretical Computer Science. An EATCS Series

This is the of the only monograph on time-dependent scheduling problems. The book presents the results of more than 45 years of research in this dynamically developing domain of modern scheduling.

This monograph is a comprehensive study of all main results concerning single, parallel and dedicated machine time-dependent scheduling problems. The previous two editions of the book focused on models of time-dependent job processing times, algorithms for solving time-dependent scheduling problems, and computational complexity issues. This edition, in addition to the above topics, discusses various proof methods and proof techniques used in time-dependent scheduling.

Topics and features:

·Detailed analysis of scheduling problems in which job processing times are functions of job starting times

·More than 450 proofs of time-dependent scheduling results

·More than 100 algorithms for time-dependent scheduling problems

·More than 150 examples illustrating the discussed results and algorithms

·Almost 50 figures and tables facilitating the understanding of the concepts discussed and results

The book is intended for researchers and Ph.D. students working in time-dependent scheduling. It is also suitable for researchers working on problem complexity, and approximation, heuristic, local search and metaheuristic algorithms for scheduling problems. While the book offers introductory material on algorithms, NP-completeness and scheduling, a familiarity with the basics of calculus, discrete mathematics and combinatorial optimization theory is expected.

Stanislaw Gawiejnowicz is affiliated with the Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznan, Poland, where he is Full Professor and Head of the Algorithmics Research Unit.

Zielgruppe

Research

Autoren/Hrsg.

Gawiejnowicz, Stanislaw

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Theoretische Informatik
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Wirtschaftswissenschaften Betriebswirtschaft Unternehmensforschung
• Mathematik | Informatik Mathematik Operations Research

Inhaltsverzeichnis

Part I FUNDAMENTALS.- Chapter 1: Basic concepts and results.- Chapter 2: Problems.- Chapter 3: Algorithms.- Chapter 4: NP-completeness.- Part II MODELS.- Chapter 5: Classical  model.- Chapter 6: Time-independent models.- Chapter 7: Time-dependent models.- Part III POLYNOMIAL PROBLEMS.- Chapter 8: Polynomial single machine problems.- Chapter 9: Polynomial parallel machine problems.- Chapter 10: Polynomial dedicated machine problems.- Part IV NP-HARD PROBLEMS.- Chapter 11: NP-hard single machine problems.- Chapter 12: NP-hard parallel machine problems.- Chapter 13: NP-hard dedicated machine problems.- Part V ALGORITHMS.- Chapter 14: Exact algorithms.- Chapter 15: Approximation algorithms.- Chapter 16: Approximation schemes.- Chapter 17: Signature-based greedy algorithms.- Chapter 18: Heuristic algorithms.- Chapter 19: Local search algorithms.- Chapter 20: Meta-heuristic algorithms.- Part VI ADVANCED TOPICS.- Chapter 21: Precedence-constrained time-dependent scheduling.- Chapter 22: Matrix methods in time-dependent scheduling.- Chapter 23: Mutually related time-dependent scheduling problems.- Chapter 24: Bi-criteria time-dependent scheduling.- Chapter 25: Two-agent time-dependent scheduling.- Chapter 26: Time-dependent scheduling on machines with limited availability.- Part VII NEW TOPICS.- Chapter 27: Time-dependent scheduling with job rejection.- Chapter 28: Time-dependent scheduling with mixed job deterioration.- Chapter 29: Time-dependent scheduling games.

Über Autor(innen)

Stanislaw Gawiejnowicz is affiliated with the Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznan, Poland, where he is Full Professor and Head of the Algorithmics Research Unit.