Scheduling: Theory, Algorithms, and Systems (2nd Edition) - Softcover

Pinedo, Michael

Softcover

ISBN 10: 0130281387 ISBN 13: 9780130281388

Publisher: Prentice Hall, 2001

Synopsis

Aimed at graduate students and practitioners, this text covers both theoretical and applied aspects of the scheduling of resources in the manufacturing and service industries. Drawing upon his experience in developing courses at Columbia U., Pinedo discusses deterministic and stochastic models for parallel machine models, flexible flow shops, and open shops. The second edition also features five new chapters on such topics as single machine scheduling with release dates and rolling horizon procedures. Annotation c. Book News, Inc., Portland, OR (booknews.com)

About this title

About the Author

Michael Pinedo is a research professor with the Stern School of Business, New York University. His research interests lie in the theoretical and applied aspects of scheduling. He has written numerous papers on the theory of deterministic and stochastic scheduling. He has also consulted extensively in industry and has been actively involved in the development of several large industrial scheduling systems.

From the Back Cover

Efficient scheduling of resources is critical to the proper functioning of businesses in today's competitive environment. Scheduling focuses on theoretical as well as applied aspects of the scheduling of resources. It is unique in the range of problems and issues that it covers.

The book consists of three parts. The first part focuses on deterministic scheduling and deals with the combinational problems that arise in deterministic scheduling. The second part covers probabilistic scheduling models. In this part it is assumed that processing times and other problem data are not known in advance with certainty. The third part deals with scheduling in practice. It covers heuristics that are popular with practitioners and also delves into system design and developmental issues.

INCLUDES:

• Discussion of the basic properties of scheduling models.
• Computational as well as theoretical exercises at the end of each chapter.
• Thorough examination of numerous applications.
• Investigation of the latest developments in the field.
• Discussion of future research developments.

A software package especially designed for the readers of this text is available free of charge on the web. Known as LEKIN, this system covers most of the machine environments discussed in this book and enables the user to test many of the algorithms and heuristics described.

This book is of interest to theoreticians and practitioners alike. Graduate students in operations research, industrial engineering, and computer science will find the book to be an accessible and invaluable resource. Scheduling will serve as an essential reference for professionals working on scheduling problems in manufacturing and computing environments.

Excerpt. © Reprinted by permission. All rights reserved.

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 environment effective sequencing and scheduling has 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 Henry Gantt 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 Naval Research Logistics Quarterly in the early 1950s 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 part stochastic models. The third and final part deals with applications. In this list 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. Reha Uzsoy and Alan Scheller Wolf went through the manuscript with a fine-tooth comb. Len Adler, Sid Browne, Xiuli Chao, Paul Glasserman, Chung-Yee Lee, YoungHoon Lee, Joseph Leung, Elizabeth Leventhal, Rajesh Sah, Paul Shapiro, Jim Thompson, Barry Wolf, and the hundreds of students who had to take the (required) scheduling courses at Columbia provided many helpful comments that 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. MICHAEL PINEDO
New York, 1994 Preface to the Second Edition

The book has been extended in a meaningful way. Five chapters have been added. In the deterministic section it is the treatment of the single machine, the job shop, and the open shop that have been expanded considerably. In the stochastic section 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. Part III, the applications section, 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.

There is a companion website for this book:
stern.nyu/~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.

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.

Reha Uzsoy, as usual, went through the manuscript with a fine-tooth comb. Salah Elmaghraby, John Fowler, Celia Glass, Chung-Yee Lee, Sigrid Knust, Joseph Leung, Chris Potts, Steve Smith, Levent Tuncel, Amy Ward, Guochuan, Zhang, Subhash Sarin, and Wilbert E. Wilhelm all made comments that led to substantial improvements.

A number of students, including Gabriel Adei, Yo Huh, Maher Lahmar, Sonia Leach, Michele Pfund, Edgar Possani, and Aysegul Toptal, 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 Heinrich Braun and Stephan Kreipl of SAP, Rama Akkiraju of IBM, Margie Bell of i2, Emanuela Rusconi and Fabio Tiozzo of Cybertec, and Paul Bender of SynQuest. MICHAEL PINEDO
New York, 2001

Edition details

• Publisher: Prentice Hall
• Publication date: 2001
• ISBN 10: 0130281387
• ISBN 13: 9780130281388
• Binding: Paperback
• Language: English
• Number of pages: 586