Table of Contents

Preface

Chapter 1. Statement of Production Scheduling

Chapter 2. Basic Concepts and Methods in Production Scheduling

2.1. Introduction

2.2. Basic scheduling concepts

2.3. Project scheduling

2.4. Shop scheduling

2.5. Conclusion

2.6. Bibliography

Chapter 3. Metaheuristics and Scheduling

3.1. Introduction

3.2. What is a combinatorial optimization problem?

3.3. Solution methods for combinatorial optimization problems

3.4. The different metaheuristic types

3.5. An application example: job shop scheduling with tooling constraints

3.6. Conclusion

3.7. Bibliography

Chapter 4. Genetic Algorithms and Scheduling

4.1. Introduction

4.2. One-machine problems

4.3. Job shop problems

4.4. Hybrid flow shop

4.5. Hybrid genetic algorithms

4.6. Conclusion

4.7. Bibliography

Chapter 5. Constraint Propagation and Scheduling

5.1. Introduction

5.2. Time constraint propagation

5.3. Resource constraint propagation

5.4. Integration of propagation techniques in search methods

5.5. Extensions

5.6. Conclusion

5.7. Bibliography

Chapter 6. Simulation Approach

6.1. Introduction

6.2. Heuristic resolution (greedy) procedures

6.3. Simulation approach

6.4. Using the simulation approach for the resolution of a scheduling problem

6.5. Priority rules

6.6. Information technology tools

6.7. Conclusion

6.8. Bibliography

Chapter 7. Cyclic Production Scheduling

7.1. Introduction

7.2. Cyclic scheduling problem classifications

7.3. Problem positioning

7.4. Presentation of tools used

7.5. Algorithm principle

7.6. Extension of cyclic strategies

7.7. Conclusion and prospects

7.8. Bibliography

Chapter 8. Hoist Scheduling Problem

8.1. Introduction

8.2. Physical system and production constraints

8.3. Hoist scheduling problems

8.4. Modeling and resolution

8.5. Resolution of other problems presented

8.6. Conclusion

8.7. Bibliography

8.8. Appendix: Notation

Chapter 9. Shop Scheduling with Multiple Resources

9.1. Introduction

9.2. Hybrid flow shop scheduling problem

9.3. RCPSP: presentation and state of the art

9.4. Conclusion

9.5. Bibliography

Chapter 10. Open Shop Scheduling

10.1. General overview

10.2. The open shop problem

10.3. Complexity of open shop problems

10.4. The preemptive case (operations executable multiple times)

10.5. Simple heuristics (excluding metaheuristics)

10.6. The disjunctive model and shop problems

10.7. Metaheuristics for the open shop

10.8. Exact methods for open shop

10.9. Algorithm comparison

10.10. Open shop problems in satellite telecommunications

10.11. Conclusion

10.12. Bibliography

Chapter 11. Scheduling Under Flexible Constraints and Uncertain Data:The Fuzzy Approach

11.1. Introduction

11.2. Basic notions on the fuzzy approach to uncertainty and constraints

11.3. Scheduling under flexible constraints

11.4. Scheduling with ill-known execution times

11.5. Flexible constraint scheduling and ill-known task execution times

11.6. Conclusion: the potential contribution of possibility theory in scheduling

11.7. Bibliography

Chapter 12. Real-Time Workshop Scheduling

12.1. Introduction

12.2. Interest and problem positioning

12.3. Modeling and dynamic of scheduling problem considered

12.4. Decisions, events and constraints

12.5. Models for off-line and on-line scheduling

12.6. Off-line scheduling method

12.7. Real-time scheduling method, interactive decision support system

12.8. Conclusion

12.9. Bibliography

List of Authors

Index

First published in France in 2001 by Hermes Science entitled “Ordonnancement de la production” First published in Great Britain and the United States in 2008 by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd | John Wiley & Sons, Inc.
6 Fitzroy Square | 111 River Street
London W1T 5DX | Hoboken, NJ 07030
UK | USA
www.iste.co.uk | www.wiley.com

© ISTE Ltd, 2008

© Hermes Science Ltd, 2001

The rights of Pierre Lopez and François Roubellat to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

 [Ordonnancement de la production. English]

Production scheduling / edited by Pierre Lopez, Francois Roubellat.

  p. cm.

 Includes bibliographical references and index.

 ISBN 978–1-84821–017–2

 1. Production scheduling. 2. Inventory control. I. Lopez, Pierre. II.

Roubellat, Francois. III. Title.

 TS157.5.07313 2008

 658.5'3--dc22

2007043950

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978–1-84821–017–2

Preface

This book is mainly a translation of an earlier text published in French in 2001. For this edition, all the authors have been requested to update their chapter by considering the latest advances and references in the field.

Research studies on job scheduling are mobilizing a large number of researchers attempting to bring solutions to theoretical as well as practical problems. New resolution methods are being developed in relation to classical scheduling problems or practical situations encountered in the context of goods or service production. Exchanges between researchers in this community are extensive and contribute to a real dynamic in this field. Numerous research studies are developed in cooperation with companies to identify real problems including problem statements not considered in much basic research for scheduling problem solving.

In this book, we have attempted to bring together a number of contributions liable to help in resolving or considering a solution to problems actually encountered in the real world.

We wish to thank all the authors who have graciously accepted to participate and who have presented a summary of available results or current studies in different fields related to production scheduling.

Pierre LOPEZ
François ROUBELLAT

Chapter 1

Statement of Production Scheduling ¹

The current environment in companies is characterized by markets facing fierce competition and from which customer requirements and expectations are becoming increasingly high in terms of quality, cost and delivery times. This evolution is made even stronger by rapid development of new information and communication technologies which provide a direct connection between companies (business to business) and between companies and their clients (business to customer). In this type of context, company performance is built on two dimensions:

– a technological dimension, whose goal is to develop intrinsic performance of marketed products in order to satisfy requirements of quality and lower cost of ownership for these products. Technological innovation plays an important role and can be a differentiating element for market development and penetration. In this regard, we must note that rapid product technological growth and the personalization requirements for these products expected by markets often lead companies to forsake mass production and instead focus on small or medium-sized production runs, even on-demand manufacturing. This requires them to have flexible and progressive production systems, able to adapt to market demands and needs quickly and efficiently;

– an organizational dimension intended for performance development in terms of production cycle times, respect of expected delivery dates, inventory and work in process management, adaptation and reactivity to variations in commercial orders, etc. This dimension plays an increasingly important role as markets are increasingly volatile and progressive, and require shorter response times from companies. Therefore, companies must have powerful methods and tools at their disposal for production organization and control [BAI 99].

This production organization must be considered not only at company level, but also from its position in the supply chain where it is one of the links, resulting in a global “virtual” company which must be focused on satisfying customer needs under the best possible conditions [BAI 99, WU 98].

To achieve these goals, a company organization normally relies on the implementation of a number of functions including scheduling which plays a vital role. Indeed, the scheduling function is intended for the organization of human and technological resource use in company workshops to directly satisfy client requirements or demands issued from a production plan prepared by the company planning function. Considering market trends and requirements, this function must organize the simultaneous execution of several jobs using flexible resources available in limited amounts, which becomes a complex problem to solve. In addition, it is this function which ultimately is responsible for product manufacturing. Its efficiency and failures will therefore highly condition the company's relationship with its customers. Within companies, this function has obviously always been present, but today it must face increasingly complex problems because of the large number of jobs that must be executed simultaneously with shorter manufacturing times. This situation is obviously the result of the current environment as it was described earlier.

Offering efficient and powerful solutions to scheduling problems thus defined constitutes an important economic challenge. Despite the simplicity of formulating this type of problem, it must be noted that to date there is no “one” method able to solve all possible scenarios. In fact there are a number of generic problems differentiated by the characteristics of jobs to be performed or resources available to perform them. Specific methods can then be associated with the resolution of each of these generic problems, these specific methods being either a specific interpretation of the problem in a general way, or a specific method dedicated to the problem involved. Resolution of a concrete problem starts by identifying the generic problem to which we can associate it, followed by the selection of the method(s) adapted to the resolution of this problem. We must also note that the decision problem associated with the scheduling problem belongs to the category of combinatorial NP-complete problems. Consequently, resolution by exact methods is not realistic for large problems, justifying the use of powerful heuristic methods. This explains why research on scheduling problems is always popular and demands numerous studies [WIE 97].

The goal of this book is to present a number of methods for the resolution of scheduling problems. There are a number of studies, past or present, on scheduling issues [HER 06, LEU 04, PIN 05, SUL 07]. In this book, we have chosen to emphasize approaches to strictly solve or to improve the solution for problems actually encountered in the real world. This leads us to the organization of this book as follows.

A global presentation of concepts in relation to the scheduling domain and basic methods for solving classical scheduling problems is proposed in Chapter 2. The following two chapters present heuristic type resolution methods to solve large problems: metaheuristics (Chapter 3) and genetic algorithms (Chapter 4). Chapter 5 discusses an approach based on constraint propagation aiming at characterizing all solutions to a problem, which can be useful to help in searching for optimal solutions or in decision support. Chapter 6 recalls resolution principles based on the use of priority rules to generate a schedule by simulation or to identify priority rules to be used to organize scheduling in real time. The two following chapters discuss three scheduling problems for specific production lines: cyclic scheduling to satisfy mass production of a limited number of products (Chapter 7) and hoist scheduling (Chapter 8). Chapter 9 addresses an important practical extension of the scheduling problem: choosing which resource to use for each job operation, coupled with the operation scheduling for resources used. Chapter 10 considers a specific problem for which operations to be performed are not linked to sequencing constraints. Finally, the last two chapters focus on scheduling problems in uncertain environments or in environments which are not completely specified, a situation often encountered in practice. The fuzzy approach makes it possible to consider these two characteristics (Chapter 11), whereas the decision support approach makes it possible to organize job processing in real time according to the real state of the workshop and thus to consider unforeseen situations, using deterministic models (Chapter 12).

It is important to note that although this book often uses vocabulary and examples inherent to the manufacturing field, methods presented can be used to organize processing of any type of activity requiring available resources in a limited amount, in particular service activities, provided of course that the processing constraints are similar to those of one of the models considered in this book.

Bibliography

[BAI 99] BAI S., NSF workshop on supply chain management in electronic commerce, Final Report, http://www.ise.ufl.edu/supplychain, 1998.

[HER 06] HERRMANN J. (Ed.), Handbook of Production Scheduling, International Series in Operations Research & Management Science , vol. 89, 2006.

[LEU 04] LEUNG J.Y-T., Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & Hall/CRC Computer & Information Science Series, 2004.

[PIN 05] PINEDO M., Planning and Scheduling in Manufacturing and Services, Springer, 2005.

[SUL 07] SULE D., Final Production Planning and Industrial Scheduling: Examples, Case Studies and Applications, Second Edition, Taylor & Francis/CRC Press, 2007.

[WIE 97] WIERS V.C.S., “A review of the applicability of OR and AI scheduling techniques in practice”, Omega, International Journal of Management Science, vol. 25, no. 2, p. 145–153, 1997.

[WU 98] WU S.D., STORER R.H. and MARTIN-VEGA L.A., “Manufacturing logistics research: taxonomy and directions”, NSF Design and Manufacturing Grantees Conference, Monterrey, Mexico, 1995.

1 Chapter written by François ROUBELLAT and Pierre LOPEZ.

Chapter 2

Basic Concepts and Methods in Production Scheduling ¹

2.1. Introduction

The scheduling problem is the organization over time of the execution of a set of tasks, taking into account time constraints (i.e. deadlines, precedence constraints, etc.) and capability and capacity constraints on resources required for these tasks.

A schedule constitutes a solution to the scheduling problem. It describes the execution of tasks and the allocation of resources over time with the aim of meeting one or more objectives. More precisely scheduling problems can be decomposed in two types. In a pure scheduling problem a start date and an end date have to be decided for each task, whereas in a sequencing problem tasks that compete for the use of the same resource only have to be ordered. Scheduling necessarily induces a unique set of sequencing relations. On the other hand, a solution to the sequencing problem, described in terms of precedence relations (those that solve the potential resources conflicts) is not associated with a single schedule but covers a family of schedules (possibly an infinity of schedules if dates are real numbers or if the variation domain is not bounded).

This chapter aims to present the main results from basic literature on scheduling problems, results which may be referred to in the following chapters. First, we present the basic concepts by integrating general method principles for the resolution of optimization problems. Then we address the project scheduling problem where most questions involve the determination of total project time and the emphasis of usable degrees of freedom (time floats) to minimize the cost of resource utilization or to smooth out the workload. Although this type of problem does not take resource constraints into account, its formulation is essential in scheduling because it enables the presentation of fundamental concepts and basic algorithms for handling time constraints. Finally, we present a second important family of problems, the shop scheduling problems. While in project scheduling, we can adapt the level of resources necessary for the execution of complex but well structured work, in shop scheduling on the other hand, we must use a known set of limited resources (machines) as well as possible to produce a diverse set of products. The complexity then lies in the combinatorics resulting from the consideration of existing resources limitation and not in the manufacturing processes which are here predetermined (in shop scheduling, manufacturing processes are often restricted to be linear sequences of operations on distinct machines, called routings). A series of traditional results are presented concerning initially one machine problems, then parallel machine problems and finally problems where products circulate in the shop according to a single routing or multiple routings.

2.2. Basic scheduling concepts

2.2.1. Tasks

A task is a basic work entity located in time with a start time ti and/or an end time ci, where execution is characterized by a duration pi (we have ci = ti + pi ) and by the intensity with which it consumes certain resources k. In more simple terms, we presume that for each resource required, this intensity is constant during task execution.

With certain problems, the tasks can be executed in parts, and interlacing of the different parts ensures that resources are as active as possible. With others, on the other hand, we cannot stop a task that is started. We speak of preemptive and non-preemptive problems respectively.

In project scheduling (see section 2.3), we will keep the term “task” to describe the activities of a project. For shop scheduling (see section 2.4), we will opt for the term “operation” (in this case, we will also prefer processing time rather than duration). In manufacturing, we often observe several phases in the execution of an operation: preparation; main phase; finishing; and transport. Depending on manufacturing conditions, each of these phases can greatly condition the time in which a product remains in the shop.

2.2.2. Resources

A resource k is a technical or human means needed for the execution of a task and available in a limited quantity, its (presumed constant) . Several types of resources can be observed. A resource is said to be if it becomes available again with the same quantity (man, machine, space, equipment in general, etc.) once used by one or more tasks; usable resource quantity is limited at each moment. Otherwise, it is or (raw material, budget, etc.); global consumption (or accumulation) during time is limited. A resource is said to be when its instant use and global consumption are both limited (source of energy, financing, etc.). resources cannot be shared, they are able to execute only one task at a time (machine tool, manipulating robot), while resources can be shared by several tasks simultaneously (team of workers, workstation) assuming that their capacity is sufficient.

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!