英文（调度理论，算法和系统）Scheduling Theory, Algorithms, and Systems (5th ed....pdf

发布时间：2022-06-02 发布人：admin 分类：说明书资料大小：9.02M 资料格式：pdf 举报版权申诉

u010827633-11239710-16359647281109828015.pdf-第1页.png

第1页 / 共674页

u010827633-11239710-16359647281109828015.pdf-第2页.png

第2页 / 共674页

u010827633-11239710-16359647281109828015.pdf-第3页.png

第3页 / 共674页

u010827633-11239710-16359647281109828015.pdf-第4页.png

第4页 / 共674页

u010827633-11239710-16359647281109828015.pdf-第5页.png

第5页 / 共674页

u010827633-11239710-16359647281109828015.pdf-第6页.png

第6页 / 共674页

u010827633-11239710-16359647281109828015.pdf-第7页.png

第7页 / 共674页

u010827633-11239710-16359647281109828015.pdf-第8页.png

第8页 / 共674页

Preface

Preface to the First Edition

Preface to the Second Edition

Preface to the Third Edition

Preface to the Fourth Edition

Preface to the Fifth Edition

Contents

Supplementary Electronic Material

1 Introduction

1.1 The Role of Scheduling

1.2 The Scheduling Function in an Enterprise

1.3 Outline of the Book

Part I Deterministic Models

2 Deterministic Models: Preliminaries

2.1 Framework and Notation

2.2 Examples

2.3 Classes of Schedules

2.4 Complexity Hierarchy

3 Single Machine Models (Deterministic)

3.1 The Total Weighted Completion Time

3.2 The Maximum Lateness

3.3 The Number of Tardy Jobs

3.4 The Total Tardiness - Dynamic Programming

3.5 The Total Tardiness - An Approximation Scheme

3.6 The Total Weighted Tardiness

3.7 Online Scheduling

3.8 Discussion

4 Advanced Single Machine Models (Deterministic)

4.1 The Total Earliness and Tardiness

4.2 Primary and Secondary Objectives

4.3 Multiple Objectives: A Parametric Analysis

4.4 The Makespan with Sequence Dependent SetupTimes

4.5 Job Families with Setup Times

4.6 Batch Processing

4.7 Discussion

5 Parallel Machine Models (Deterministic)

5.1 The Makespan without Preemptions

5.2 The Makespan with Preemptions

5.3 The Total Completion Time without Preemptions

5.4 The Total Completion Time with Preemptions

5.5 Due Date Related Objectives

5.6 Online Scheduling

5.7 Discussion

6 Flow Shops and Flexible Flow Shops (Deterministic)

6.1 Flow Shops with Unlimited Intermediate Storage

6.2 Flow Shops with Limited Intermediate Storage

6.3 Proportionate Flow Shops with Unlimited and Limited Intermediate Storage

6.4 Flexible Flow Shops with Unlimited Intermediate Storage

6.5 Discussion

7 Job Shops (Deterministic)

7.1 Disjunctive Programming and Branch-and-Bound

7.2 The Shifting Bottleneck Heuristic and the Makespan

7.3 The Shifting Bottleneck Heuristic and the Total Weighted Tardiness

7.4 Constraint Programming and the Makespan

7.5 Discussion

8 Open Shops (Deterministic)

8.1 The Makespan without Preemptions

8.2 The Makespan with Preemptions

8.3 The Maximum Lateness without Preemptions

8.4 The Maximum Lateness with Preemptions

8.5 The Number of Tardy Jobs

8.6 Discussion

Part II Stochastic Models

9 Stochastic Models: Preliminaries

9.1 Framework and Notation

9.2 Distributions and Classes of Distributions

9.3 Stochastic Dominance

9.4 Impact of Randomness on Fixed Schedules

9.5 Classes of Policies

10 Single Machine Models (Stochastic)

10.1 Arbitrary Distributions without Preemptions

10.2 Arbitrary Distributions with Preemptions: the Gittins Index

10.3 Likelihood Ratio Ordered Distributions

10.4 Exponential Distributions

10.5 Discussion

11 Single Machine Models with Release Dates (Stochastic)

11.1 Arbitrary Release Dates and Arbitrary Processing Times without Preemptions

11.2 Priority Queues, Work Conservation, and Poisson Releases

11.3 Arbitrary Releases and Exponential Processing Times with Preemptions

11.4 Poisson Releases and Arbitrary Processing Times without Preemptions

11.5 Discussion

12 Parallel Machine Models (Stochastic)

12.1 The Makespan and Total Completion Time withoutPreemptions

12.2 The Makespan and Total Completion Time with Preemptions

12.3 Due Date Related Objectives

12.4 Bounds Obtained through Online Scheduling

12.5 Discussion

13 Flow Shops, Job Shops and Open Shops (Stochastic)

13.1 Stochastic Flow Shops with Unlimited Intermediate Storage

13.2 Stochastic Flow Shops with Blocking

13.3 Stochastic Job Shops

13.4 Stochastic Open Shops

13.5 Discussion

Part III Scheduling in Practice

14 General Purpose Procedures for Deterministic Scheduling

14.1 Dispatching Rules

14.2 Composite Dispatching Rules

14.3 Local Search: Simulated Annealing and Tabu-Search

14.4 Local Search: Genetic Algorithms

14.5 Ant Colony Optimization

14.6 Discussion

15 More Advanced General Purpose Procedures

15.1 Beam Search

15.2 Decomposition Methods and Rolling Horizon Procedures

15.3 Constraint Programming

15.4 Market-Based and Agent-Based Procedures

15.5 Procedures for Scheduling Problems with Multiple Objectives

15.6 Discussion

16 Modeling and Solving Scheduling Problems in Practice

16.1 Scheduling Problems in Practice

16.2 Cyclic Scheduling of a Flow Line

16.3 Scheduling of a Flexible Flow Line with Limited Buffers and Bypass

16.4 Scheduling of a Flexible Flow Line with Unlimited Buffers and Setups

16.5 Scheduling a Bank of Parallel Machines with Jobs having Release Dates and Due Dates

16.6 Discussion

17 Design and Implementation of Scheduling Systems: Basic Concepts

17.1 Systems Architecture

17.2 Databases, Object Bases, and Knowledge-Bases

17.3 Modules for Generating Schedules

17.4 User Interfaces and Interactive Optimization

17.5 Generic Systems vs. Application-Specific Systems

17.6 Implementation and Maintenance Issues

18 Design and Implementation of Scheduling Systems: More Advanced Concepts

18.1 Robustness and Reactive Decision-Making

18.2 Machine Learning Mechanisms

18.3 Design of Scheduling Engines and AlgorithmLibraries

18.4 Reconfigurable Systems

18.5 Web-Based Scheduling Systems

18.6 Discussion

19 Examples of System Designs and Implementations

19.1 SAP's Production Planning and Detailed Scheduling System

19.2 IBM's Independent Agents Architecture

19.3 Real Time Dispatching and Agent Scheduling at AMD

19.4 ASPROVA Advanced Planning and Scheduling

19.5 Preactor Planning and Scheduling Systems

19.6 ORTEMS' Agile Manufacturing Suite

19.7 LEKIN - A System Developed in Academia

19.8 Discussion

20 What Lies Ahead?

20.1 Theoretical Research

20.2 Applied Research

20.3 Systems Development

Appendices

Mathematical Programming: Formulations and Applications

A.1 Linear Programming Formulations

A.2 Integer Programming Formulations

A.3 Bounds, Approximations, and Heuristics Based on Linear Programming

A.4 Disjunctive Programming Formulations

Deterministic and Stochastic Dynamic Programming

B.1 Deterministic Dynamic Programming

B.2 Stochastic Dynamic Programming

Constraint Programming

C.1 Constraint Satisfaction

C.2 Constraint Programming

C.3 An Example of a Constraint Programming Language

C.4 Constraint Programming vs. Mathematical Programming

Complexity Theory

D.1 Preliminaries

D.2 Polynomial Time Solutions versus NP-Hardness

D.3 Examples

D.4 Approximation Algorithms and Schemes

Complexity Classification of Deterministic SchedulingProblems

Overview of Stochastic Scheduling Problems

Selected Scheduling Systems

The Lekin System

H.1 Formatting of Input and Output Files

H.2 Linking Scheduling Programs

References

Author Index

Subject Index

Michael L. Pinedo Scheduling Theory, Algorithms, and Systems Fifth Edition

Scheduling

Michael L. Pinedo Scheduling Theory, Algorithms, and Systems Fifth Edition 123

Michael L. Pinedo IOMS Dept Rm 8-59 KMC NYU Stern School of Business New York, NY, USA Additional material to this book can be downloaded from http://extras.springer.com ISBN 978-3-319-26578-0 DOI 10.1007/978-3-319-26580-3 ISBN 978-3-319-26580-3 (eBook) Library of Congress Control Number: 2015955728 Springer Cham Heidelberg New York 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, speciﬁcally the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microﬁlms 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 speciﬁc 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, Jeﬀrey, Ralph, Franciniti, Morris, Izzy Michael E., Charles, Michael J., and Evelyn

Henry Laurence Gantt (1861–1919) Henry Laurence Gantt was born in Calvert County, 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 Frederick W. 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 “Eﬃciency and Democracy,” which he presented at the annual meeting of the American Society of Mechanical Engineers in New York in 1918. The Gantt charts currently in use in decision support systems are often quite diﬀerent from the originals, in their purpose as well as in their design.

Preface 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, eﬀective 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 signiﬁcant loss of goodwill. They also have to schedule activities in such a way as to use the resources available in an eﬃcient 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 ﬁrst scheduling publications to appear in the industrial engineering and operations research literature. Some of the ﬁrst publications appeared in the Naval Research Logistics Quarterly in the early ﬁfties and contained results by W.E. Smith, S.M. Johnson, and J.R. Jackson. During the 1960s a signiﬁcant 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 diﬀerent 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 ﬁrst part covers deterministic models and the second vii

分享到：

赞收藏

资料库

英文（调度理论，算法和系统）Scheduling Theory, Algorithms, and Systems (5th ed....pdf

相关推荐

行业

热门标签

最新资料