Scheduling Algorithms

Besides scheduling problems for single and parallel machines and shop scheduling problems the book covers advanced models involving due-dates, sequence dependent changeover times and batching. Also multiprocessor task scheduling and problems with multi-pu

  • PDF / 3,630,797 Bytes
  • 378 Pages / 444.373 x 666.142 pts Page_size
  • 97 Downloads / 278 Views

DOWNLOAD

REPORT


Peter Brucker

Scheduling Algorithms Fifth Edition

With 77 Figures and 32 Tables

123

Professor Dr. Peter Brucker Universität Osnabrück Fachbereich Mathematik/Informatik Albrechtstraße 28a 49069 Osnabrück Germany [email protected]

Library of Congress Control Number: 2006940721

ISBN 978-3-540-69515-8 Springer Berlin Heidelberg New York ISBN 978-3-540-20524-1 4th ed. Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is part of Springer Science+Business Media springer.com © Springer-Verlag Berlin Heidelberg 2001, 2004, 2007 The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Production: LE-TEX Jelonek, Schmidt & Vockler GbR, Leipzig ¨ Cover-design: WMX Design GmbH, Heidelberg SPIN 11970705

42/3100YL - 5 4 3 2 1 0

Printed on acid-free paper

Preface of the Fifth and Fourth Edition In these editions new results have been added to the complexity columns. Furthermore, the bibliographies have been updated. Again many thanks go to Marianne Gausmann for the typesetting and to Dr. Sigrid Knust for taking care of the complexity columns which can be found under the www-address http://www.mathematik.uni-osnabrueck.de/research/OR/class. Osnabr¨ uck, October 2006

Peter Brucker

vi

Preface

Preface of the Third Edition In this edition again the complexity columns at the end of each chapter and the corresponding references have been updated. I would like to express may gratitude to Dr. Sigrid Knust for taking care of a corresponding documentation of complexity results for scheduling problems in the Internet. These pages can be found under the world-wide-web address http://www.mathematik.uni-osnabrueck.de/research/OR/class. In addition to the material of the second edition some new results on scheduling problems with release times and constant processing times and on multiprocessor task problems in which each task needs a certain number of processors have been included. The new edition has been rewritten in LATEX 2ε . Many thanks go to Marianne Gausmann for the new typesetting and to Christian Strotmann for creating the bibliography database files. Osnabr¨ uck, March 2001

Peter Brucker

Preface of the Second Edition In this revised edition new material has been added. In particular, the chapters on batching problems and multiprocesso