Scheduling
Theory, Algorithms, and Systems
Fifth Edition
Copyright By PowCoder代写 加微信 powcoder
Scheduling
Scheduling
Theory, Algorithms, and Systems Fifth Edition
IOMS Dept Rm 8-59 KMC NYU Stern School of Business , NY, USA
Additional material to this book can be downloaded from http://extras.springer.com ISBN 978-3-319-26578-0 ISBN 978-3-319-26580-3 (eBook)
DOI 10.1007/978-3-319-26580-3
Library of Congress Control Number: 2015955728
Heidelberg Dordrecht London
© Springer Science+Business Media, LLC 2016
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, 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.
The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made.
Printed on acid-free paper
Springer International Publishing AG Switzerland is part of Springer Science+Business Media (www. springer.com)
To: Paula,
Esti, Jaclyn, Danielle,
Eddie, Jeffrey, Ralph,
Franciniti, Morris, E., Charles, ., and
(1861–1919)
Henry was born in , Maryland, in 1861. When he was 19 he graduated from Johns Hopkins University and subsequently received a master’s of engineering degree from the Stevens Institute of Technology. He made a career as an industrial engineer and became a close associate of . Taylor. He developed his now famous charts during World War I in order to evaluate production schedules. One year before his death, Gantt discussed the underlying principles in his paper “Efficiency and Democracy,” which he presented at the annual meeting of the American Society of Mechanical Engineers in in 1918. The Gantt charts currently in use in decision support systems are often quite different from the originals, in their purpose as well as in their design.
Preface to the First Edition
Sequencing and scheduling is a form of decision-making that plays a crucial role in manufacturing and service industries. In the current competitive en- vironment, effective sequencing and scheduling have become a necessity for survival in the marketplace. Companies have to meet shipping dates that have been committed to customers, as failure to do so may result in a significant loss of goodwill. They also have to schedule activities in such a way as to use the resources available in an efficient manner.
Scheduling began to be taken seriously in manufacturing at the beginning of this century with the work of and other pioneers. However, it took many years for the first scheduling publications to appear in the industrial engineering and operations research literature. Some of the first publications appeared in the Naval Research Logistics Quarterly in the early fifties and contained results by W.E. Smith, S.M. Johnson, and J.R. Jackson. During the 1960s a significant amount of work was done on dynamic programming and integer programming formulations of scheduling problems. After Richard Karp’s famous paper on complexity theory, the research in the 1970s focused mainly on the complexity hierarchy of scheduling problems. In the 1980s several different directions were pursued in academia and industry with an increasing amount of attention paid to stochastic scheduling problems. Also, as personal computers started to permeate manufacturing facilities, scheduling systems were being developed for the generation of usable schedules in practice. This system design and development was, and is, being done by computer scientists, operations researchers, and industrial engineers.
This book is the result of the development of courses in scheduling theory and applications at Columbia University. The book deals primarily with machine scheduling models. The first part covers deterministic models and the second
viii Preface
part stochastic models. The third and final part deals with applications. In this last part scheduling problems in practice are discussed, and the relevance of the theory to the real world is examined. From this examination it becomes clear that the advances in scheduling theory have had only a limited impact on scheduling problems in practice. Hopefully there will be in a couple of years a second edition in which the applications part will be expanded, showing a stronger connection with the more theoretical parts of the text.
This book has benefited from careful reading by numerous people. and Wolf went through the manuscript with a fine- tooth comb. , , , , Chung- , Young- , , , , , , , and the hundreds of students who had to take the (required) scheduling courses at Columbia provided many helpful comments which improved the manuscript.
The author is grateful to the National Science Foundation for its continued summer support, which made it possible to complete this project.
, 1994 . Pinedo
Preface to the Second Edition
The book has been extended in a meaningful way. Five chapters have been added. In the deterministic part it is the treatment of the single machine, the job shop, and the open shop that have been expanded considerably. In the stochastic part a completely new chapter focuses on single machine scheduling with release dates. This chapter has been included because of multiple requests from instructors who wanted to see a connection between stochastic scheduling and priority queues. This chapter establishes such a link. The applications part, Part III, has been expanded the most. Instead of a single chapter on general purpose procedures, there are now two chapters. The second chapter covers various techniques that are relatively new and that have started to receive a fair amount of attention over the last couple of years. There is also an additional chapter on the design and development of scheduling systems. This chapter focuses on rescheduling, learning mechanisms, and so on. The chapter with the examples of systems implementations is completely new. All systems described are of recent vintage. The last chapter contains a discussion on research topics that could become of interest in the next couple of years.
The book has a website:
http://www.stern.nyu.edu/∼mpinedo
The intention is to keep the site as up to date as possible, including links to other sites that are potentially useful to instructors as well as students.
Preface ix
Many instructors who have used the book over the last couple of years have sent very useful comments and suggestions. Almost all of these comments have led to improvements in the manuscript.
, as usual, went with a fine-tooth comb through the manuscript. , , , Chung- , , , , , , and all made comments that led to substantial improvements.
A number of students, including , Yo Huh, , , , , and , have pointed out various errors in the original manuscript.
Without the help of a number of people from industry, it would not have been possible to produce a meaningful chapter on industrial implementations. Thanks are due to and of SAP, of IBM, Margie Bell of i2, and of Cybertec, and of SynQuest.
, 2001 . Pinedo
Preface to the Third Edition
The basic structure of the book has not been changed in this new edition. The book still consists of three parts and a string of Appendixes. However, several chapters have been extended in a meaningful way, covering additional topics that have become recently of interest. Some of the new topics are more methodological, whereas others represent new classes of models.
The more methodological aspects that are receiving more attention include Polynomial Time Approximation Schemes (PTAS) and Constraint Program- ming. These extensions involve new material in the regular chapters as well as in the Appendixes. Since the field of online scheduling has received an enormous amount of attention in recent years, a section focusing on online scheduling has been added to the chapter on parallel machine scheduling.
Two new classes of models are introduced in the chapter on more advanced single machine scheduling, namely, single machine scheduling with batch pro- cessing and single machine scheduling with job families.
Of course, as in any new edition, the chapter that describes implementations and applications had to be revamped and made up to date. That has happened here as well. Two new software systems have been introduced, namely, a system that is currently being implemented at AMD (Advanced Micro Devices) and a generic system developed by .
For the first time, a CD-ROM has been included with the book. The CD- ROM contains various sets of PowerPoint slides, minicases provided by com- panies, the LEKIN Scheduling system, and two movies. The PowerPoint slides
were developed by (when he taught a scheduling course at the University of Michigan- ), (from the University of Twente in Holland), (from the State University of at Buffalo), (from the University of Dortmund in Germany), and (from the University of Leeds in England).
A website will be maintained for this book at
http://www.stern.nyu.edu/∼mpinedo
The intention is to keep this website as up to date as possible, including links to other sites that are potentially useful to instructors as well as to students.
A hardcopy of a solutions manual is available from the author for instructors who adopt the book. The solutions provided in this manual have been prepared by (Columbia University), (Michigan), (Waterloo), (Leeds), (Waterloo), and (Georgia Tech).
I am very grateful to a number of colleagues and students in academia who have gone over the new sections and have provided some very useful comments, namely, (Siena), (T.J. Watson Research Labo- ratories, IBM), (Kiel), (Arizona), (Wa- terloo), (TU Twente, the Netherlands), (AMD), Gianluca de Pascale (Siena, Italy), Paulus (TU Twente, the Nether- lands), ( , Prague), and (TU Eindhoven). Gerhard provided me with the chapters he wrote on Polynomial Time Approximation Schemes. His material has been incredibly useful.
Without the help of a number of people from the industry, it would not have been possible to produce a meaningful chapter on industrial implementations. Thanks are due to of SAP, and of AMD, and Donald of .
The technical production of the book would not have been possible with- out the invaluable help from (Stanford University) and (Springer). Without the continued support of the National Science Foundation, this book would never have been written.
Spring 2008 . Pinedo
Preface to the Fourth Edition
The text has undergone a number of enhancements and corrections. The presen- tations and proofs of various results in Chapters 4 and 5 have been changed and simplified. Chapter 6 now contains a new section that focuses on proportionate flow shops. Chapter 19 contains a significant amount of new material as well;
Preface xi
two new sections have been added that describe the Asprova APS and the Pre- actor scheduling systems. The other chapters have undergone minor changes; however, a significant number of new references have been added in order to keep the book up to date.
A website for this book is still being maintained on the author’s homepage
http://www.stern.nyu.edu/∼mpinedo
The intention is to keep this website as up to date as possible, including links to other sites that are potentially useful to instructors as well as to students.
The third edition of this book contained a CD-ROM. The material on the CD-ROM has been expanded significantly; but, in this new edition, this mate- rial is not included as a CD-ROM. This supplementary electronic material is available for download from the author’s homepage as well as from the Springer site
http://extras.springer.com
This supplementary electronic material will also be included in the e-book ver- sion of this text.
A hardcopy of a solutions manual is still available from the author for in- structors who adopt the book. The solutions provided in the manual have been prepared by (Columbia University), (Michigan), (Waterloo), (Leeds), (Waterloo), and (Georgia Tech).
I am very grateful to a number of colleagues and students in academia who have gone over the new sections and have provided some very useful comments, namely, (Wuppertal), (Southamp- ton), ( ), , and (Pitts- burgh), (Wuppertal), (University Dort- mund), ( , Prague), (University of Melbourne), and ( ).
Without the help from various individuals in the industry, it would not have been possible to produce a meaningful chapter on industrial implementations. With respect to these changes, thanks are due to Oh Ki from Asprova and from Preactor.
The technical production of the book would, again, not have been possible without the invaluable help from (Stanford University), (Springer), and (NYU). The continued support of the National Science Foundation is still very much being appreciated.
Fall 2011 . Pinedo
xii Preface
Preface to the Fifth Edition
The text has been extended in various directions and underwent a fair amount of polishing. Chapter 3 now contains a new section that focuses on online schedul- ing in a single machine environment; it introduces a new rule, the so-called Weighted Round Robin (WRR) rule. Chapter 12 introduces for a parallel ma- chine environment with machine eligibility constraints a preemptive rule that assigns at any point in time the Least Flexible Job to the Fastest Machine (LFJ- FM). Chapter 19 contains a certain amount of new material as well; a new section has been added that describes the ORTEMS scheduling system. The other chapters have undergone minor changes. The tables in Appendixes E, F, and G have been expanded in a meaningful way. A significant number of new references have been added in order to keep the book up to date.
The website for this book is still being maintained on the author’s home- page at
http://www.stern.nyu.edu/∼mpinedo
The intention is to keep this site up to date and include links to other sites that may be useful to instructors and to students.
Supplementary electronic material is still available for download from the author’s homepage as well as from the Springer site
http://extras.springer.com
This supplementary electronic material is also included in the e-book version of this text.
A hardcopy of a solutions manual is still available from the author for instruc- tors who adopt the book for teaching a course. The solutions provided in the manual have been prepared by (Columbia University), – lason (Michigan), (Waterloo), (Leeds), (Waterloo), and (Georgia Tech).
I am very grateful to all my colleagues in academia who have gone over the new sections and have provided some very useful comments, including (NYU), (Wuppertal), (Haifa), (Aachen), Kangbok Lee (CUNY), (Nantes), (Pittsburgh), (Berkeley), (Amsterdam), (Shanghai Jiao Tong), and Guohua Wan (Shanghai Jiao Tong).
The technical production of the book, again, would not have been possible without the invaluable help from at Stanford University and , , and at Springer and at SPi Global. The support of the National Science Foundation has, as always, been appreciated very much.
Summer 2015 . Pinedo
Preface ………………………………………………… vii
Supplementary Electronic Material ……………………….. xix
1 Introduction………………………………………… 1
1.1 The Role of Scheduling……………………………… 1
1.2 The Scheduling Function in an Enterprise ………………. 4
1.3 Outline of the Book………………………………… 7
Part I Deterministic Models
2 Deterministic Models: Preliminaries …………………… 13
2.1 Framework and Notation ……………………………. 13
2.2 Examples………………………………………… 20
2.3 Classes of Schedules ……………………………….. 21
2.4 Complexity Hierarchy………………………………. 25
3 Single Machine Models (Deterministic) ………………… 33
3.1 The Total Weighted Completion Time …………………. 34
3.2 The Maximum Lateness …………………………….. 40
3.3 The Number of Tardy Jobs ………………………….. 45
3.4 TheTotalTardiness-DynamicProgramming……………. 49
3.5 The Total Tardiness – An Approximation Scheme…………. 53
3.6 The Total Weighted Tardiness ……………………….. 56
3.7 Online Scheduling …………………………………. 59
3.8 Discussion……………………………………….. 64
4 Advanced Single Machine Models (Deterministic) . . . . . . . . . . 71 4.1 TheTotalEarlinessandTardiness…………………….. 72
4.2 Primary and Secondary Objectives ……………………. 79
4.3 Multiple Objectives: A Parametric Analysis……………… 81
4.4 The Makespan with Sequence Dependent Setup
Times…………………………………………… 84
4.5 Job Families with Setup Times……………………….. 93
4.6 Batch Processing ………………………………….. 100
4.7 Discussion……………………………………….. 106
5 Parallel Machine Models (Deterministic) ………………. 113
5.1 The Makespan without Preemptions …………………… 114
5.2 The Makespan with Preemptions ……………………… 124
5.3 The Total Completion Time without Preemptions . . . . . . . . . . . . 131
5.4 The Total Completion Time with Preemptions …………… 135
5.5 Due Date Related Objectives ………………………… 137
5.6 Online Scheduling …………………………………. 139
5.7 Discus
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com