139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
This book describes the main classical combinatorial problems that can be encountered when designing a logistics network or driving a supply chain. It shows how these problems can be tackled by metaheuristics, both separately and using an integrated approach. A huge number of techniques, from the simplest to the most advanced ones, are given for helping the reader to implement efficient solutions that meet its needs.
A lot of books have been written about metaheuristics (methods for solving hard optimization problems) and supply chain management (the field in which we find a huge number of combinatorial optimization problems) in the last decades. So, the main reason of this book is to describe how these methods can be implemented for this class of problems.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 249
Veröffentlichungsjahr: 2016
Ähnliche
Table of Contents
Cover
Title
Copyright
Introduction
PART 1: Basic Notions
1 Introductory Problems
1.1. The “swing states” problem
1.2. Adel and his camels
1.3. Sauron’s forges
2 A Review of Logistic Problems
2.1. Some history
2.2. Some polynomial problems
2.3. Packing problems
2.4. Routing problems
2.5. Production scheduling problems
2.6. Lot-sizing problems
2.7. Facility location problems
2.8. Conclusion
3 An Introduction to Metaheuristics
3.1. Optimization problems
3.2. Metaheuristics: basic notions
3.3. Individual-based metaheuristics
3.4. Population-based metaheuristics
3.5. Conclusion
4 A First Implementation of Metaheuristics
4.1. Representing a list of objects
4.2. The implementation of a local search
4.3. The implementation of individual-based metaheuristics
4.14. Conclusion
PART 2: Advanced Notions
5 The Traveling Salesman Problem
5.1. Representing a solution: the two-level tree structure
5.2. Constructing initial solutions
5.3. Neighborhood systems
5.4. Some results
5.5. Conclusion
6 The Flow-Shop Problem
6.1. Representation and assessment of a solution
6.2. Construction of the initial solution
6.3. Neighborhood systems
6.4. Results
6.5. Conclusion
7 Some Elements for Other Logistic Problems
7.1. Direct representation versus indirect representation
7.2. Conditioning problems
7.3. Lot-sizing problems
7.4. Localization problems
7.5. Conclusion
PART 3: Evolutions and Current Trends
8 Supply Chain Management
8.1. Introduction to supply chain management
8.2. Horizontal synchronization of the supply chain
8.3. Vertical synchronization of a supply chain
8.4. An integral approach of the supply chain
8.5. Conclusion
9 Hybridization and Coupling Using Metaheuristics
9.1. Metaheuristics for the optimization of the supply chain
9.2. Hybridization of optimization methods
9.3. Coupling of optimization methods and performance evaluations
9.4. Conclusion
10 Flexible Manufacturing Systems
10.1. Introduction to the FMS challenges
10.2. The job-shop problem with transport
10.3. Proposal for a metaheuristic/simulation coupling
10.4. Workshop layout problem
10.5. Conclusion
11 Synchronization Problems Based on Vehicle Routings
11.1. Inventory routing problem
11.2. The location-routing problem
11.3. Conclusion
12 Solution to Problems
12.1. The swing state problem
12.2. Adel and his camels
12.3. The forges of Sauron
Conclusion
Bibliography
Index
End User License Agreement
Guide
Cover
Table of Contents
Introduction
List of Tables
1 Introductory Problems
Table 1.1. List of “swing states” and estimate of the investment necessary to obtain a majority
Table 1.2. Time necessary to gear up the camels (in minutes)
Table 1.3. Time of the tourists’ arrival
Table 1.4. Distance between the mine and the forges
Table 1.5. Volume (in m
3
) to be transported to each forge
Table 1.6. Production cost units for the parts of the siege machine
Table 1.7. Production capacity of the forges per hour
5 The Traveling Salesman Problem
Table 5.1. Some results for the TSP
6 The Flow-Shop Problem
Table 6.1. Example of a two-machine flow shop
Table 6.2. Results for the problem of the permutation flow shop
10 Flexible Manufacturing Systems
Table 10.1. Comparative results with the instances of the literature [DER 08]
Table 10.2. Comparative results in the literature instances [DER 13]
Table 10.3. Comparison of assignments – makespan criterion
12 Solution to Problems
Table 12.1. Results of the greedy heuristic in accordance with the criteria
Table 12.2. Evaluation of delays (case of isolated departures)
Table 12.3. Evaluation of delays (case of grouped departures)
Table 12.4. Evaluation of the greedy heuristic solution
Table 12.5. Transit times (in hours) between two sites
List of Illustrations
1 Introductory Problems
Figure 1.1. Will Mr L. satisfy Adel’s customers?
Figure 1.2. Map of Mordor
Figure 1.3. Nazgûl riding a winged creature
2 A Review of Logistic Problems
Figure 2.1. The Fermat-Torricelli point. Point P minimizes the expression MA + MB + MC
Figure 2.2. The Monge problem
Figure 2.3. The first puzzles solved by graphs
Figure 2.4. Example of a transportation problem
Figure 2.5. Illustration of the Minimum-Cost Spanning Tree
Figure 2.6. Flow-shop scheduling problem: illustrated by an example
Figure 2.7. Constraints of the flow conservation
3 An Introduction to Metaheuristics
Figure 3.1. Different optimization problems and their solving techniques
4 A First Implementation of Metaheuristics
Figure 4.1. Illustration of a permutation and of some representations
Figure 4.2. Illustration of the exchange, insertion, and inversion moves
5 The Traveling Salesman Problem
Figure 5.1. Units of the two-level tree structures
Figure 5.2. Coding for a permutation with a two-level tree structure
Figure 5.3. The four stages of the construction of the Christofides algorithm
Figure 5.4. An example of a 3-opt sequential move
Figure 5.5. A non-sequential move: the double bridge
Figure 5.6. “Stem-and-Cycle” structure and corresponding solutions
Figure 5.7. Changes to “Stem-and-Cycle” structures
6 The Flow-Shop Problem
Figure 6.1. Illustration of how the CDS heuristic works
Figure 6.2. Illustration of how the NEH heuristic works
Figure 6.3. Setbacks of the inversion movement
Figure 6.4. Taillard algorithm: insertion principle
Figure 6.5. Taillard algorithm adapted: principle for suppression
7 Some Elements for Other Logistic Problems
Figure 7.1. Indirect representation: case of an unattainable global optimum
Figure 7.2. Bin packing problem – example of objective function
8 Supply Chain Management
Figure 8.1. General sketch of a supply chain
Figure 8.2. Supply chain: a vision by activities
Figure 8.3. Gameboard of the milk carton game
Figure 8.4. The bullwhip effect in a supply chain
Figure 8.5. The three decision-making levels
Figure 8.6. Optimization problems of a supply chain
9 Hybridization and Coupling Using Metaheuristics
Figure 9.1. Taxonomy of hybrid metaheuristics (according to [TAL 02])
Figure 9.2. Principle of the hybridization “metaheuristic/local search”
Figure 9.3. Double complexity and method coupling [NOR 05]
Figure 9.4. Optimization-simulation coupling (1st approach)
Figure 9.5. Optimization-simulation coupling (2nd approach)
10 Flexible Manufacturing Systems
Figure 10.1. Four classic layouts of the FMS [BIL 95]
Figure 10.2. The 10 data sets [BIL 95]
Figure 10.3. Problem of policy
Figure 10.4. Partitioning of operations and representation of one solution
Figure 10.5. Reorganization of the workshop
Figure 10.6. Solution approach for the workshop configuration problem
Figure 10.7. Gantt Chart [DER 13]
11 Synchronization Problems Based on Vehicle Routings
Figure 11.1. Positioning of inventory and of location routing problems in supply chain management
Figure 11.2. A historical example of the IRP [BEL 83]
Figure 11.3. The three phases of the “Location Routing Problem”
12 Solution to Problems
Figure 12.1. Gantt chart of a scheduling obtained with the Johnson rule
Figure 12.2. Gantt chart of the greedy heuristic solution
Figure 12.3. Evaluation of routings
Figure 12.4. Construction schedule of the weapon
Pages
C1
iii
iv
v
xi
xii
xiii
xiv
xv
1
3
4
5
6
7
8
9
10
11
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
57
58
59
60
61
62
63
64
65
66
67
69
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
119
121
122
123
124
125
126
127
128
129
131
132
133
134
135
136
137
138
139
140
141
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
197
198
Metaheuristics for Logistics
Volume 4
Laurent Deroussi
Metaheuristics Set
coordinated by Nicolas Monmarché and Patrick Siarry
First published 2016 in Great Britain and the United States 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 4EUUK
www.iste.co.uk
John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA
www.wiley.com
© ISTE Ltd 2016The rights of Laurent Deroussi to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2015959671
British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-84821-808-6
Introduction
General Eisenhower stated that: “You will not find it difficult to prove that battles, campaigns, and even wars have been won or lost primarily because of logistics”. The military genius introduced the term “logistics” as the activity that allows supplying troops, temporally and spatially in order to maintain all of their operational abilities.
Logistics has progressively imposed itself in the industrial world ever since its revolution during the 19th Century, and nowadays it constitutes a means of pressure essential for the competitiveness of companies.
How can we exploit the full potential of logistics?
By bringing its flow under control and by structuring its logistic activity, which are the concerns of Supply Chain Management (SCM), several tools have been developed in various fields (manufacturing, inventory, supply and information management, etc.).
These tools can be of different kinds. They may be organizational (Lean Manufacturing, Kanban, Just-in-Time, etc.) or related to data management and use (Enterprise Resource Planning, Advanced Planning and Scheduling, Electronic Data Interchange, etc.). The scope of this work is limited to the latter category and, more specifically, to the field of decision-making tools and to the specialty they belong to, i.e. Operations Research (OR).
Robert Faure, one of the pioneers of Operations Research in France, qualified his discipline as “the set of rational methods and techniques for the analysis and the synthesis of organizational phenomena that can be used to make better decisions”. The advent of informatics, which has revolutionized our way of thinking and allowed Operations Research to take shape, has enabled us to approach logistics from a quantitative point of view.
Logistics-related problems have been pointed out, modeled and studied. However, some of them originated in the earliest stages of logistics. They were already stimulating the minds of talented scientists in the form of numerous conundrums and other mathematical challenges that they proposed to the world.
It is all the more to these pioneers’ credit that some of these problems have not been solved yet. Could it be that they are resistant to mathematics itself? Contemporary mathematicians have grouped them into two broad categories that are summarized as follows: “easy” problems and “hard” problems.
I am used to telling my students that the last person they should trust is their Operations Research professor. The words “easy” and “hard”, when uttered by a professor, are quite far from their original meaning. Thus, a problem deemed easy may turn out to be tricky to solve for someone with no insider knowledge (the two-machine flow-shop scheduling problem). Likewise, a “hard” problem may seem simple at first sight (the knapsack problem). You will soon know the two problems I have given as examples inside out!
In simple terms, “easy” problems include the set of combinatorial optimization1 problems for which we know an effective solving algorithm. This clearly shows that the number of necessary calculations is a polynomial function of the size of the problem. These problems belong to the P class of problems, which are called polynomial. On the contrary, we say that a problem is “hard” when the only algorithms we know for its solution are verified in exponential time. These problems belong to the NP class and will be called non-polynomial.
The greater part of the scientific community thinks that if we have no effective method for the solution of an NP-class problem, it is simply because there is no solution! This question, stemming from the complexity theory, is known as the “P versus NP” problem. To date, it remains unsolved and is classified by the Clay Mathematics Institute as one of the seven Millennium Prize Problems. A US $1,000,000 prize will be awarded to whoever solves it.
As it happens in mathematics, whenever a problem is too complex to be solved, approximate methods are applied. Metaheuristics, which constitutes a family of generic procedures, belongs to this category. They have proved their ability to solve complex optimization problems for several years.
Throughout this book I will aim to show these procedures, to see definitively how they can be applied to logistic problems, and to understand the solutions they can provide for the quantitative optimization of the mechanism of a supply chain.
For that reason, this book is made up of 3 parts and 12 chapters.
The first part is called “Basic Notions”. It enables us to lay some foundations whether in relation to logistic problems or concerning optimization procedures. It includes Chapters 1 to 4.
– Chapter 1 presents us with a certain number of logistic problems in the form of exercises drawn from everyday life, which offer a first playful approach to the field. Some detailed answers, together with comments, are provided in the last chapter of this book.
– Chapter 2 draws up a methodical inventory of logistic problems, emphasizing their variety and the richness of the solutions they provide to a great number of logistic sectors. Each of these problems is presented formally in the form of a linear program. This kind of mathematical modeling, despite seeming possibly rigid, can nonetheless contain information useful for the concept of metaheuristics.
– Chapter 3 constitutes an introduction to metaheuristics. The scope of the application of these methods and the general concepts are presented. Some metaheuristic procedures are then explained in detail, while emphasis is put on their historical background, on the concepts that make them differ or bring them together, on their advantages and on their drawbacks.
– Chapter 4 constitutes a first concrete example of the application of metaheuristics. A detailed and progressive implementation, provided with comments, is proposed for an important category of optimization problems, i.e. permutation problems. This first piece of work on metaheuristics will allow us to develop a range of tools adaptable to many logistic problems and be able to give us acceptable results.
The second part is called “Advanced notions”, as surprising as this might seem. This part aims to propose a certain number of more sophisticated tools, which will enable us to better the performance of metaheuristics. It includes Chapters 5, 6 and 7.
– The whole of Chapter 5 is dedicated to the emblematic traveling salesman problem. As for this permutation problem, metaheuristics can increase their effectiveness if they incorporate more elaborate procedures. Some of these mechanisms, such as variable neighborhood search or ejection chains, will be split into their components through the prism of the important relevant literature.
– Chapter 6 will sum up some research we have carried out in order to adapt the mechanisms mentioned in the previous chapter to the permutation flow-shop scheduling problem. This problem is also, as its name points out, a permutation problem.
– Chapter 7 aims to extend our reflection to other logistic problems that do not deal with permutation. Two general kinds of approaches are compared: the indirect approach, which consists of adapting the problem to metaheuristics and the direct approach, which consists of adapting metaheuristics to the problem.
The last part is called “Evolutions and Current Trends'”. The significance of logistic problems progressively dwindles before the current needs of the supply chain. This section is designed to define these needs and to determine the solutions that metaheuristics can provide when confronted with these new challenges. It includes Chapters 8 to 12.
– Chapter 8 introduces the concept of supply chain management. Logistic problems on their own can no longer provide satisfactory solutions to the new issues concerning the supply chain. We define the notions of horizontal and vertical synchronization in order to define the interactions between all these problems with more precision.
– Chapter 9 is also dedicated to solution methods. Faced with the study of increasingly complex systems, solving techniques have to join forces. The notion of hybridization of the optimization methods and the concept of interaction between an optimization procedure and a performance evaluation technique are studied.
– Chapter10 describes an analysis we have carried out on flexible production systems. This study enables us to show the solutions that can be provided by an approach that combines several procedures in the study of a complex system.
– Chapter 11 describes two complex problems, set up by combining two logistic problems, which occur more and more often in the literature on the subject. These problems can clearly show the significant role they play in relation to decision-making in a supply chain. In addition to the problems, we will also describe some solving techniques present in the literature.
– Chapter 12 provides detailed solutions to the problems presented in Chapter 2.
1
A combinatorial optimization problem consists of looking for the best solution among a very large, if finite, set of solutions. A more formal definition is offered in
Chapter 4
. All the logical problems found in this book belong to this category of problems.
