Flexibility and Robustness in Scheduling E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 550

Veröffentlichungsjahr: 2013

Beschreibung

Scheduling is a broad research area and scheduling problems arise from several application domains (production systems, logistic, computer science, etc.). Solving scheduling problems requires tools of combinatorial optimization, exact or approximated algorithms. Flexibility is at the frontier between predictive deterministic approaches and reactive or "on-line" approaches. The purpose of flexibility is to provide one or more solutions adapted to the context of the application in order to provide the ideal solution. This book focuses on the integration of flexibility and robustness considerations in the study of scheduling problems. After considering both flexibility and robustness, it then covers various scheduling problems, treated with an emphasis on flexibility or robustness, or both.

Leseprobe

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 Ltd27-37 St George’s RoadLondon SW19 4EUUKJohn Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.iste.co.ukwww.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 2

Robustness in Operations Research and Decision Aiding1

It is always advisable to perceive clearly our ignorance.(Charles Darwin)

2.1. Overview

The search for robustness is an ever present concern is Operations Research and Decision Aiding (OR-DA) where increasingly rich and diversified methodologies and concepts are emerging. The term “robust” applies to a large variety of objects such as solution, method and conclusion. In OR-DA, the notion of robustness is often used in the same way as (sometimes even instead of) flexibility, stability, sensitivity and even equity in certain cases.

Faced with this diversity, I think it is necessary to highlight what seems to be the generally used meaning for the term “robust” in OR-DA (section 2.1.1) before specifying the reasons leading to the concern for robustness in this discipline (section 2.1.2) and presenting the structure of this chapter (section 2.1.3).

2.1.1. Robust in OR-DA with meaning?

As I see it, robust is a term that is generally used in the sense of a capacity for withstanding “vague approximations” and/or “zones of ignorance” in order to prevent undesirable impacts, notably the degradation of the properties to be maintained.

“Vague approximations” can refer to a way of modeling, the restrictive character of certain hypotheses, mode of value allocation to data and/or parameters, etc.

“Zones of ignorance” may deal with the complexity of certain phenomena and of value systems but mostly the future: trends, contingencies, behavior of others, etc.

Here are a few examples to illustrate this meaning of the term “robust” in scheduling. In Chapter 1, a solution is said to be robust if its “performance is rather insensitive to data uncertainties and disturbances”. In this context, insensitivity to data uncertainty means resisting to this uncertainty1. The uncertainty in question can for example refer to the way of modeling which processes certain data as insignificant or not influenced by contingencies, a Gaussian hypothesis simplifying the mode of consideration of a random phenomenon or the approximate character of values attributed to data (processing time, due date, etc.).

In some maintenance studies, scheduling must be conceived to guarantee deadlines are respected even though the jobs to be done are not well known (resistance to a certain form of ignorance). Job-shop scheduling may have to be chosen for its capacity to face an order book that is only partially known or with unknown reactions to delays that the end customer may encounter because of contingencies. Climate conditions, as well as work-related accidents or social upheavals, are sources of ignorance that project management may have to consider.

Two comments seem necessary to specify the meaning of what was just discussed:

1) Even though the borderline between vague approximations and zones of ignorance is far from being well defined, all vague approximations do not come from a zone of ignorance and all zones of ignorance do not lead to vague approximations.

2) Resistance can have the following meanings: protecting from, adapting to, being rather insensitive to, remaining stable, settling a certain form of equity, etc.

We will now examine the reasons resulting in the need to resist these vague approximations and zones of ignorance in OR-DA.

2.1.2. Why the concern for robustness?

In OR-DA, the capacity for resistance qualified by robustness is required in order to be protected from undesirable impacts, impacts that should be apprehended taking into account these vague approximations and/or zones of ignorance that need to be resisted. The nature of these impacts, along with the (very often subjective) way of assessing their undesirable character, are contingent to the context involved. The concerns motivating the search for robustness are extremely diversified for these reasons. I will settle for illustrating them through a series of examples in this chapter:

i) Exceptional character decisions

– Layout of a large linear infrastructure (very high speed train line, highway, high-tension line, etc.): throughout the execution (five years or more), what reactions will it generate? Once this is finished, what standards will it be judged by? Will the size be adapted to traffic?

– Construction of a sanitation or waterworks system: knowing that implementing such activities, as with the evolution of consumption patterns, can only be defined in large variation ranges, will the designed system be able to fulfill population requirements in the planned horizon without needing adjustments leading to prohibitive costs?

– Updating of equipment: considering the evolution of technology and environmental standards, when should the decision be made to update?

ii) Sequential character decisions

– Plan designed to be implemented in stages: how will the contexts in future stages be affected by the decisions taken at this present stage? Do they allow for possible evolutions of these contexts by keeping the range of adaptations and reactions open?

– Scheduling flight personnel in an airline company: how can we handle unexpected unavailability of teams (unforeseen absences, immobilization during a mission, etc.) in acceptable economic conditions and with no planning disruptions for agents?

iii) Choice of a method for repetitive applications

– Management support method for restocking a store: does the method protect against out of stock risks that could result from a failure to respect of delivery lead times by suppliers? Is it adapted for possible evolutions of purchase agreements?

– Method controlling budget distribution between members in a group: knowing that the size and composition of beneficiary groups can greatly change over time and space, will the method retained be considered fair in all cases where it will be applied?

– Adjustment method for a model dedicated to emphasizing the way in which different factors contribute to global client satisfaction during consecutive surveys: how can we avoid the results depending on final retained values (chosen in a relatively arbitrary manner in certain intervals) for different technical parameters involved in the model?

2.1.3. Plan of the chapter

In the next section, I will examine where, for a decision aiding problem (DAP), “vague approximations” and “zones of ignorance” come from, for which the need for protection leads to the search for robustness. These vague approximations and zones of ignorance are closely linked to the way that the decision aiding problem is formulated (DAPF). They can also depend (although generally less so) on the processing procedure applied to this formulation in the decision aiding process. This leads me to introduce the general concept of version. In section 2.3, I will specify the meaning I give to several currently used terms (procedure and method notably) in order to clarify their links with the concern for robustness. In section 2.4, I will focus on the way to take robustness into consideration: what must be robust? How can we formalize robustness? In what form can vague approximations and zones of ignorance be taken into account? Unfortunately, many questions raised here will remain unanswered. A brief conclusion will complete this chapter.

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

2.2.1. Sources of inaccurate determination, uncertainty and imprecision

Once the DAP is formulated, we should identify, in this formulation, the “places” (concepts, numerical data, presence or absence of links between phenomena, neglected aspects and factors, way to formulate constraints and criteria, the arbitrariness of certain operating instructions in a process mode, etc.) which could be affected by vague approximations and/or zones of ignorance. The specific form in which these relevant places are presented is obviously very specific to the problem studied, the way it is formulated and the process mode applied. Nevertheless, I think it is possible to see them whatever they are as frailty points connected to sources of inaccurate determination, uncertainty or arbitrariness (see [ROY 89]). The vague approximations and zones of ignorance that must be resisted actually come from such sources. They can, it seems, be classified into three categories (even though the line separating these categories is not perfectly well defined, they affect sides of the DAPF which I think it is important to distinguish):

– Source S · α: vague, uncertain, unknown, and even undetermined character of factual data, objective descriptions of phenomena and purely technical procedural aspects in relation to the form in which they must occur during the aiding process in the present situation.

This source may, for example, affect frailty points such as: processing times, due dates, process cost, failure probabilities, probability distributions chosen for modeling a random factor, discrimination thresholds, values given to the parameters playing a mostly technical role in a model or procedure, techniques used to adjust a model intended to represent complex phenomena, etc.