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 multipur
- PDF / 26,237,247 Bytes
- 353 Pages / 439.37 x 666.142 pts Page_size
- 105 Downloads / 222 Views
Springer-Verlag Berlin Heidelberg GmbH
Peter Brucker
Scheduling Algorithms Second, Revised and Enlarged Edition With 76 Figures and 18 Tables
i
Springer
Prof. Dr. Peter Brucker Universitat Osnabriick Fachbereich Mathematikllnformatik Albrechtstr. 28 D-49076 Osnabriick
Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Brucker, Peter: Scheduling algorithms: with 18 tables I Peter Brucker. - 2., rev. and enl. ed. ISBN 978-3-662-03614-3 ISBN 978-3-662-03612-9 (eBook) DOI 10.1007/978-3-662-03612-9 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-Verlag Berlin Heidelberg GmbH. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1995, 1998
Originally published by Springer-Verlag Berlin Heidelberg New York in 1998 Softcover reprint of the hardcover 2nd edition 1998
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. Hardcover-Design: Erich Kirchner, Heidelberg SPIN 10655823
42/2202-5 4 3 2 I 0 - Printed on acid-free paper
Preface of the Second Edition In this revised edition new material has been added. In particular, the chapters on batching problems and multiprocessor task scheduling have been augmented. Also the complexity columns at the end of each chapter have been updated. In this connection I would like thank Jan Karel Lenstra for providing the current results of the program MSPCLASS. I am grateful for the constructive comments of Jacek Blazewicz, Johann Hurink, Sigrid Knust, Svetlana Kravchenko, Erwin Pesch, Maurice Queyranne, Vadim Timkowsky, Jiirgen Zimmermann which helped to improve the first edition. Finally, again special thanks go to Marianne Gausmann and Teresa Gehrs for the 'lEX typesetting and for improving the English. Osnabriick, November 1997
Peter Brucker
Preface This is a book about scheduling algorithms. The first such algorithms were formulated in the mid fifties. Since then there has been a growing interest in scheduling. During the seventies, computer scientists discovered scheduling as a tool for improving the performance of computer systems. Furthermore, scheduling problems have been investigated and classified with respect to their computational complexity. During the last few years, new and interesting scheduling problems have been formulated in connection with flexible manufacturing. Most parts of the book are devot
