Table of Contents

Preface

Chapter 1: Introduction to Flexibility and Robustness in Scheduling

1.1. Scheduling problems

1.2. Background to the study

1.3. Uncertainty management

1.4. flexibility

1.5. Robustness

1.6. Bibliography

Chapter 2: Robustness in Operations Research and Decision Aiding

2.1. Overview

2.2. Where do “vague approximations” and “zones of ignorance” come from? - the concept of version

2.3. Defining some currently used terms

2.4. How to take the robustness concern into consideration

2.5. Conclusion

2.6. Bibliography

Chapter 3: The Robustness of Multi-Purpose Machines Workshop Configuration

3.1. Introduction

3.2. Problem presentation

3.3. Performance measurement

3.4. Robustness evaluation

3.5. Extension: reconfiguration problem

3.6. Conclusion and perspectives

3.7. Bibliography

Chapter 4: Sensitivity Analysis for One and m Machines

4.1. Sensitivity analysis

4.2. Single machine problems

4.3. m-machine problems without communication delays

4.4. The m-machine problems with communication delays

4.5. Conclusion

4.6. Bibliography

Chapter 5: Service Level in Scheduling

5.1. Introduction

5.2. Motivations

5.3. Optimization of the service level: application to the ßow-shop problem

5.4. Computation of a schedule service level

5.5. Conclusions

5.6. Bibliography

Chapter 6: Metaheuristics for Robust Planning and Scheduling

6.1. Introduction

6.2. A general framework for metaheuristic robust optimization

6.3. Single-machine scheduling application

6.4. Application to the planning of maintenance tasks

6.5. Conclusions and perspectives

6.6. Bibliography

Chapter 7: Metaheuristics and Performance Evaluation Models for the Stochastic Permutation Flow-Shop Scheduling Problem

7.1. Problem presentation

7.2. Performance evaluation problem

7.3. Scheduling problem

7.4. Computational experiment

7.5. Conclusion

7.6. Bibliography

Chapter 8: Resource Allocation for the Construction of Robust Project Schedules

8.1. Introduction

8.2. Resource allocation and resource flows

8.3. A branch-and-bound procedure for resource allocation

8.4. A polynomial algorithm for activity insertion

8.5. Conclusion

8.6. Bibliography

Chapter 9: Constraint-based Approaches for Robust Scheduling

9.1. Introduction

9.2. Necessary/sufficient/dominant conditions and partial orders

9.3. Interval structures, tops, bases and pyramids

9.4. Necessary conditions for a generic approach to robust scheduling

9.5. Using dominance conditions or sufficient conditions

9.6. Conclusion

9.7. Bibliography

Chapter 10: Scheduling Operation Groups: A Multicriteria Approach to Provide Sequential Flexibility

10.1. Introduction

10.2. Groups of permutable operations

10.3. The ORABAID approach

10.4. AMORFE, a multicriteria approach

10.5. Application to several scheduling problems

10.6. Conclusion

10.7. Bibliography

Chapter 11: A Flexible Proactive-Reactive Approach: The Case of an Assembly Workshop

11.1. Context

11.2. Definition of the control model

11.3. Proactive algorithm

11.4. Reactive algorithm

11.5. Experiments and validation

11.6. Extensions and conclusions

11.7. Bibliography

Chapter 12: Stabilization for Parallel Applications

12.1. Introduction

12.2. Parallel systems and scheduling

12.3. Overview of different existing approaches

12.4. The stabilization approach

12.5. Two directions for stabilization

12.6. An intrinsically stable algorithm

12.7. Experiments

12.8. Conclusion

12.9. Bibliography

Chapter 13: Contribution to a Proactive/Reactive Control of Time Critical Systems

13.1. Introduction

13.2. Static problem definition

13.3. Step 1: computing a feasible sequencing family

13.4. Step 2: dynamic phase

13.5. Restrictions due to p-time PNs

13.6. Bibliography

Chapter 14: Small Perturbations on Some NP-Complete Scheduling Problems

14.1. Introduction

14.2. Problem definitions

14.3. NP-completeness results

14.4. Conclusion

14.5. Bibliography

List of Authors

Index

First published in France in 2005 by Hermes Science/Lavoisier entitled: “Flexibilité et robustesse en ordonnancement”

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
27-37 St George’s Road
London SW19 4EU
UK
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA

www.iste.co.uk
www.wiley.com

© ISTE Ltd, 2008

The rights of Jean-Charles Billaut, Aziz Moukrim and Eric Sanlaville 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

[Flexibilité et robustesse en ordonnancement English] Flexibility and robustness in scheduling / Edited by Jean-Charles Billaut, Aziz Moukrim, Eric Sanlaville.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-054-7

1. Production scheduling. I. Billaut, Jean-Charles 1973- II. Moukrim, Aziz. III. Sanlaville, Eric.

TS157.5.F55 2008

658.5'3--dc22

2008030722

British Library Cataloguing-in-Publication Data

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

ISBN: 978-1-84821-054-7

Preface

This book is about scheduling under uncertainties. However, the problems concern the whole domain of decision aid. Of course, the question of decision aid under unexpected events or uncertainties is not new, but a recent awareness has come on the necessity to define specific models. This awareness has lead to research activities in various domains like location, communication or transportation network design, supply chain management, industrial planing and – of course – scheduling problems.

In Spring 2000, some members of the “GOThA” group (a French working group on “Theoretical scheduling and applications”) decided to create a sub-group working in the field of “flexibility”. It seemed convenient to gather the persons interested by the question: “how do we schedule under uncertainties?”. The success of this initiative was a surprise for their promoters themselves. In France only, among ten research teams were working on this problem. These teams wanted to communicate ideas, to unify the terminology, to exchange references. After multiple meetings during 2003, this group became a project “Scheduling with flexibility and robustness” among an official structure, the GDR-CNRS on Operations Research. The book Flexibilité et Robustesse en Ordonnancement published by Hermes in 2005 was the first conclusion of this project. This book is a revised version of this title.

The outline of the book is the following. The two first chapters are introductory. The first one introduces the problem, the main concepts and basic definitions. The second chapter is written by Bernard Roy, who examines the concept of robustness in the more general framework of decision aid. Subsequent chapters correspond to the specialties of several research teams. They can be organized according to the resolution approach or the application field. Each chapter presents a state-of-the-art survey related to its field.

Chapters 3 to 8 (5 to 8 with probabilistic hypotheses) consider that all the decisions have been taken before starting the schedule. In the approach of Chapters 9 to 13 most of the decisions are taken during the execution of the schedule. The last chapter considers on-line re-optimization.

Scheduling theory concerns several fields. Chapters 3, 5, 7, 10, 11 and 13 consider shop scheduling problems, whereas Chapters 6 and 8 consider project scheduling problems and Chapters 4 and 12 consider parallel computing. Chapters 9 and 14 do not consider a particular application field. But frontiers are sometimes thin.

We are very happy with this English version and hope that it will interest numerous researchers and scheduling practitioners.

Jean-Charles BILLAUT

Aziz MOUKRIM

Eric SANLAVILLE

Chapter 1

Introduction to Flexibility and Robustness in Scheduling¹

1.1. Scheduling problems

A large variety of scheduling problems are to be found in many domains. Almost every sector is concerned by scheduling problems in the broad sense:

– Industrial production systems: problems may need to be solved simultaneously in machine scheduling and vehicle dispatching (automated guided systems, robotic cells, hoist scheduling problems), in workshop layout problems or supply chain management problems.

– Computer systems: for example, to make full use of the processing power provided by parallel machines or when scheduling tasks with resource constraints in real-time environments.

– Administrative systems: appointment scheduling in health care sector, general resource assignment, timetabling, etc.

– Transportation systems: vehicle routing problems, traveling salesman problems, etc.

In all cases, for a realization being described as a series of interdependent tasks, it is necessary to coordinate the implementation of these tasks, i.e. to allocate resources to tasks and set their execution dates. Sometimes a schedule simply consists of a sequence of tasks by machine, coupled with a simple rule for calculating task start times (for example earliest schedules). However, in the more general case it is necessary to allocate a start time to each task in the schedule definition.

The basic data of a scheduling problem (see for instance [BRU 07]) are: the tasks to schedule with their precedence constraints, their duration, resources that are necessary for their execution and a function to optimize.

Methods for solving scheduling problems draw from all the techniques of combinatorial optimization, whether approximate methods (greedy algorithms, local search, genetic algorithms, etc.) or exact methods (mathematical programming, branch-and-bound methods, dynamic programming, decomposition methods, constraint programming, etc.). Solving a particular problem may require the use of modeling tools for complex systems (simulation, Petri nets, etc.), thus leading to the definition of matchings between these methods.

The scheduling problems addressed in this book are described according to the classification schemes proposed in [GRA 79]. The scheduling problems are specified using a classification in terms of three fields, α|β|γ where α specifies the machine environment, β the operation characteristics, and γ the criterion to optimize.

1.1.1. Machine environments

The majority of scheduling problems correspond to a number of fundamental theoretical models. We have to schedule a set of n tasks or n jobs. The machine environments are specified in the field α separated into two subfields α₁α₂. Depending on the values of α₁, we may distinguish the following models:

– Single machine problems. Each task Tj of duration pj runs on a dedicated machine that cannot handle more than one task at a time. In that case the field α₁ is absent and α₂ = 1.

– Parallel machine problems. The tasks are to be executed on machines in parallel, and pij denotes the execution time of Tj on machine Mi:

- If α₁ = P, the machines are identical: pij = pj for any machine Mi.

- If α₁ = Q, the machines are uniform: pij = pj/si where si is the processing speed of machine Mi.

- If α₁ = R, machines are unrelated: pij = pj/sij where sij is the processing speed of task Tj on machine Mi.

– Shop problems. In this model, a shop consists of m different machines. We consider a set of jobs that need to be performed. Each job Jj is described by nj tasks (which are called operations). Operation Jj running on machine Mi is denoted Oij, and its duration is pij. Operations belonging to the same job cannot be carried out simultaneously. There are three main types of shop:

- Flow-shop. Each job consists of m operations and the order of execution on different machines is the same for each job. In this case α₁ = F.

- Job-shop. The number of operations is not necessarily the same for each job, and every job has its own order of execution on the machines. In this case α₁ = J.

- Open shop. This is the least constrained shop scheduling problem. The number of operations is not necessarily the same for each job, and the order of execution on the machines is completely free. In this case = .

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!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!