Scheduling - Theory, Algorithms, and Systems, 4th edition (Springer, 2012, 14614.pdf

1、Scheduling Michael L.PinedoSchedulingTheory,Algorithms,and SystemsFourth Editionpermission of the publisher(Springer Science+Business Media,LLC,233 Spring Street,New York,NY10013,USA),except for brief excerpts in connection with reviews or scholarly analysis.Use in connectionwith any form of informa

2、tion storage and retrieval,electronic adaptation,computer software,or by similaror dissimilar methodology now known or hereafter developed is forbidden.The use in this publication of trade names,trademarks,service marks,and similar terms,even if they arenot identified as such,is not to be taken as a

3、n expression of opinion as to whether or not they are subjectto proprietary rights.Printed on acid-free paperSpringer is part of Springer Science+Business Media()Springer New York Dordrecht Heidelberg LondonISBN 978-1-4614-1986-0e-ISBN 978-1-4614-2361-4DOI 10.1007/978-1-4614-2361-4 Springer Science+

4、Business Media,LLC 201All rights reserved.This work may not be translated or copied in whole or in part without the writtenMathematics Subject Classification(2010):Library of Congress Control Number:268Mxx,68M20,90Bxx,90B35Michael L.PinedoNew York New York UniversityNY,USA2011945105mpinedostern.nyu.

5、eduTo Paula,Esti,Jaclyn,and Danielle,Eddie,Jeffrey,and Ralph,Franciniti,Morris,Izzy,and baby Michael.HFrWpratinthHenrredeWar rinct then 19he ory LericI tociplee an918.origiLauck Wo ees innu.ThinalurenW.evalin hual he Gls,bnce Tayuathis meeGanbothGylore ppapetinntt ch inHEanttr.Hprodper ng ocharn puE

6、NRt wHe dduct“Efof trts curpoRY was devetionfficthe currose LA(1anelopn sccienAmrenandAUR1861n inpedchedncy meritly d inRE1-19 ndud hiduleandicanin un deNC919stris noes.d Dn Souse esignCE G9)ial ow GaDemociearen.GAengfamantt mocrety e tyANTginemoudisracyof ypicTTeer us cscusy,”Meallyancharssedwhecha

7、y a nd arts dd thichanicsima ddurhe uhecalmplidiscringunde preEnificacipleg Wderlyesenginatioe oWorldyingntedneeron oof d g d rs of PrefacePreface to the First EditionSequencing and scheduling is a form of decision-making that plays a crucial rolein manufacturing and service industries.In the curren

8、t competitive environmenteffective sequencing and scheduling has become a necessity for survival in themarket-place.Companies have to meet shipping dates that have been committedto customers,as failure to do so may result in a significant loss of goodwill.Theyalso have to schedule activities in such

9、 a way as to use the resources availablein an efficient manner.Scheduling began to be taken seriously in manufacturing at the beginningof this century with the work of Henry Gantt and other pioneers.However,ittook many years for the first scheduling publications to appear in the industrialengineerin

10、g and operations research literature.Some of the first publications ap-peared in Naval Research Logistics Quarterly in the early fifties and containedresults by W.E.Smith,S.M.Johnson and J.R.Jackson.During the sixties asignificant amount of work was done on dynamic programming and integer pro-grammi

11、ng formulations of scheduling problems.After Richard Karp s famouspaper on complexity theory,the research in the seventies focused mainly on thecomplexity hierarchy of scheduling problems.In the eighties several differentdirections were pursued in academia and industry with an increasing amountof at

12、tention paid to stochastic scheduling problems.Also,as personal comput-ers started to permeate manufacturing facilities,scheduling systems were beingdeveloped for the generation of usable schedules in practice.This system designand development was,and is,being done by computer scientists,operationsr

13、esearchers and industrial engineers.This book is the result of the development of courses in scheduling theory andapplications at Columbia University.The book deals primarily with machinescheduling models.The first part covers deterministic models and the secondpart stochastic models.The third and f

14、inal part deals with applications.In thislast part scheduling problems in practice are discussed and the relevance ofthe theory to the real world is examined.From this examination it becomesviiviiiPrefaceclear that the advances in scheduling theory have had only a limited impacton scheduling problem

15、s in practice.Hopefully there will be in a couple of yearsa second edition in which the applications part will be expanded,showing astronger connection with the more theoretical parts of the text.This book has benefited from careful reading by numerous people.Reha Uz-soy and Alan Scheller Wolf went

16、through the manuscript with a fine tooth comb.Len Adler,Sid Browne,Xiuli Chao,Paul Glasserman,Chung-Yee Lee,Young-Hoon Lee,Joseph Leung,Elizabeth Leventhal,Rajesh Sah,Paul Shapiro,JimThompson,Barry Wolf,and the hundreds of students who had to take the(re-quired)scheduling courses at Columbia provide

17、d many helpful comments whichimproved the manuscript.The author is grateful to the National Science Foundation for its continuedsummer support,which made it possible to complete this project.Michael PinedoNew York,1994.Preface to the Second EditionThe book has been extended in a meaningful way.Five

18、chapters have beenadded.In the deterministic part it is the treatment of the single machine,thejob shop and the open shop that have been expanded considerably.In thestochastic part a completely new chapter focuses on single machine schedulingwith release dates.This chapter has been included because

19、of multiple requestsfrom instructors who wanted to see a connection between stochastic schedulingand priority queues.This chapter establishes such a link.The applications part,Part III,has been expanded the most.Instead of a single chapter on generalpurpose procedures,there are now two chapters.The

20、second chapter coversvarious techniques that are relatively new and that have started to receive a fairamount of attention over the last couple of years.There is also an additionalchapter on the design and development of scheduling systems.This chapterfocuses on rescheduling,learning mechanisms,and

21、so on.The chapter with theexamples of systems implementations is completely new.All systems describedare of recent vintage.The last chapter contains a discussion on research topicsthat could become of interest in the next couple of years.The book has a website:http:/www.stern.nyu.edu/mpinedoThe inte

22、ntion is to keep the site as up-to-date as possible,including links toother sites that are potentially useful to instructors as well as students.Many instructors who have used the book over the last couple of years havesent very useful comments and suggestions.Almost all of these comments haveled to

23、 improvements in the manuscript.Reha Uzsoy,as usual,went with a fine tooth comb through the manuscript.Salah Elmaghraby,John Fowler,Celia Glass,Chung-Yee Lee,Sigrid Knust,PrefaceixJoseph Leung,Chris Potts,Levent Tuncel,Amy Ward,and Guochuan Zhangall made comments that led to substantial improvements

24、.A number of students,including Gabriel Adei,Yo Huh,Maher Lahmar,SoniaLeach,Michele Pfund,Edgar Possani,and Aysegul Toptal,have pointed outvarious errors in the original manuscript.Without the help of a number of people from industry,it would not havebeen possible to produce a meaningful chapter on

25、industrial implementations.Thanks are due to Heinrich Braun and Stephan Kreipl of SAP,Rama Akkirajuof IBM,Margie Bell of i2,Emanuela Rusconi and Fabio Tiozzo of Cybertec,and Paul Bender of SynQuest.Michael PinedoNew York,2001.Preface to the Third EditionThe basic structure of the book has not been c

26、hanged 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 additionaltopics that have become recently of interest.Some of the new topics are moremethodological,whereas others represent new clas

27、ses of models.The more methodological aspects that are receiving more attention includePolynomial Time Approximation Schemes(PTAS)and Constraint Program-ming.These extensions involve new material in the regular chapters as well asin the Appendixes.Since the field of online scheduling has received an

28、 enormousamount of attention in recent years,a section focusing on online scheduling hasbeen added to the chapter on parallel machine scheduling.Two new classes of models are introduced in the chapter on more advancedsingle machine scheduling,namely single machine scheduling with batch pro-cessing a

29、nd single machine scheduling with job families.Of course,as in any new edition,the chapter that describes implementationsand applications had to be revamped and made up-to-date.That has happenedhere as well.Two new software systems have been introduced,namely a systemthat is currently being implemen

30、ted at AMD(Advanced Micro Devices)and ageneric system developed by Taylor Software.For the first time,a CD-ROM has been included with the book.The CD-ROM contains various sets of power point slides,minicases provided by com-panies,the LEKIN Scheduling system,and two movies.The power point slideswere

31、 developed by Julius Atlason(when he taught a scheduling course at theUniversity of Michigan-Ann Arbor),Johann Hurink(from the University ofTwente in Holland),Rakesh Nagi(from the State University of New York atBuffalo),Uwe Schwiegelshohn(from the University of Dortmund in Germany),Natalia Shakhlevi

32、ch(from the University of Leeds in England).xPrefaceA website will be maintained for this book athttp:/www.stern.nyu.edu/mpinedoThe intention is to keep this website as up-to-date as possible,including linksto other sites that are potentially useful to instructors as well as to students.A hardcopy o

33、f a solutions manual is available from the author for instructorswho adopt the book.The solutions provided in this manual have been preparedby Clifford Stein(Columbia University),Julius Atlason(Michigan),Jim Geelen(Waterloo),Natalia Shakhlevich(Leeds),Levent Tuncel(Waterloo),and MartinSavelsbergh(Ge

34、orgia Tech).I am very grateful to a number of colleagues and students in academia whohave gone over the new sections and have provided some very useful comments,namely Alessandro Agnetis(Siena),Ionut Aron(T.J.Watson Research Labo-ratories,IBM),Dirk Briskhorn(Kiel),John Fowler(Arizona),Jim Geelen(Wa-

35、terloo),Johann Hurink(TU Twente,the Netherlands),Detlef Pabst(AMD),Gianluca de Pascale(Siena,Italy),Jacob Jan Paulus(TU Twente,the Nether-lands),Jiri Sgall(Charles University,Prague),and Gerhard Woeginger(TUEindhoven).Gerhard provided me with the chapters he wrote on PolynomialTime Approximation Sch

36、emes.His material has been incredibly useful.Without the help of a number of people from industry,it would not havebeen possible to produce a meaningful chapter on industrial implementations.Thanks are due to Stephan Kreipl of SAP,Shekar Krishnaswamy and Peng Quof AMD,and Robert MacDonald of Taylor

37、Software.The technical production of the book would not have been possible withoutthe invalualable help from Adam Lewenberg(Stanford University)and AchiDosanjh(Springer).Without the continued support of the National ScienceFoundation this book would never have been written.Michael PinedoSpring 2008N

38、ew YorkPreface to the Fourth EditionThe 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 andsimplified.Chapter 6 now contains a new section that focuses on proportionateflow shops.Chapter 19 contains a

39、significant amount of new material as well;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 tokeep the book up-to-date.PrefacexiA

40、 website for this book is still being maintained on the author s homepagehttp:/www.stern.nyu.edu/mpinedoThe intention is to keep this website as up-to-date as possible,including linksto other sites that are potentially useful to instructors as well as to students.The third edition of this book conta

41、ined a CD-ROM.The material on theCD-ROM has been expanded significantly;but,in this new edition,this ma-terial is not included as a CD-ROM.This supplementary electronic materialSpringer sitehttp:/This supplementary electronic material will also be included in the ebook ver-sion of this text.A hardco

42、py of a solutions manual is still available from the author for in-structors who adopt the book.The solutions provided in the manual have beenprepared by Clifford Stein(Columbia University),Julius Atlason(Michigan),Jim Geelen(Waterloo),Natalia Shakhlevich(Leeds),Levent Tuncel(Waterloo),and Martin Sa

43、velsbergh(Georgia Tech).I am very grateful to a number of colleagues and students in academia whohave gone over the new sections and have provided some very useful comments,namely Stefan Bock(Wuppertal),Banafsheh Khosravi(Southampton),ScottMason(Clemson University),Martin Picha,Kirk Pruhs(Pittsburgh

44、),ChristianRathjen(Wuppertal),Uwe Schwiegelshohn(University Dortmund),Jiri Sgall(Charles University,Prague),Andrew Wirth(University of Melbourne),andLirong Xia(Duke University).Without the help from various individuals in industry,it would not have beenpossible to produce a meaningful chapter on ind

45、ustrial implementations.Withrespect to these changes,thanks are due to Oh Ki from Asprova and GregoryQuinn from Preactor.The technical production of the book would,again,not have been possiblewithout the invaluable help from Adam Lewenberg(Stanford University),AchiDosanjh(Springer),and Danielle Benz

46、aken(NYU).The continued support ofthe National Science Foundation is still very much being appreciated.Michael PinedoFall 2011New Yorkis available for download from the authors homepage as well as from the ContentsPreface.viiSupplementary Electronic Material.xix1Introduction.11.1The Role of Scheduli

47、ng.11.2The Scheduling Function in an Enterprise.41.3Outline of the Book.6Part I Deterministic Models2Deterministic Models:Preliminaries.132.1Framework and Notation.132.2Examples.202.3Classes of Schedules.212.4Complexity Hierarchy.263Single Machine Models(Deterministic).353.1The Total Weighted Comple

48、tion Time.363.2The Maximum Lateness.423.3The Number of Tardy Jobs.473.4The Total Tardiness-Dynamic Programming.503.5The Total Tardiness-An Approximation Scheme.543.6The Total Weighted Tardiness.573.7Discussion.614Advanced Single Machine Models(Deterministic).694.1The Total Earliness and Tardiness.70

49、4.2Primary and Secondary Objectives.774.3Multiple Objectives:A Parametric Analysis.79xiiixivContents4.4The Makespan with Sequence Dependent Setup Times.824.5Job Families with Setup Times.914.6Batch Processing.984.7Discussion.1045Parallel Machine Models(Deterministic).1115.1The Makespan without Preem

50、ptions.1125.2The Makespan with Preemptions.1225.3The Total Completion Time without Preemptions.1295.4The Total Completion Time with Preemptions.1335.5Due Date Related Objectives.1365.6Online Scheduling.1375.7Discussion.1426Flow Shops and Flexible Flow Shops(Deterministic).1516.1Flow Shops with Unlim