> Root Entry Ff 1>iFWordDocumentqObjectPooldtgtgSummaryInformation(
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~\E/]CompObjj
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTz^_`abcdefghijklmnoprstuvwx{}~
$
!"#%&'()*+,.0123456789:;<=>?@BCDGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnostuvwxy{}~
FMicrosoft Word Document
MSWordDocWord.Document.69qley 1988
Laburthe, F. (1998), Contraintes et Algorithmes en optimisation combinatoire, PhD Thesis, Universit Denis Diderot.
Mattfeld, D.C. (1996), Evolutionary Search and the JobShop, SpringerVerlag.
Minoux, M. (1983), Programmation Mathmatique, thorie et algorithmes, Dunod, Paris.
Nowicki, E. and Smutnicki, C. (1996), A Fast Taboo Search Algorithm for the JobShop Problem, Management Science, vol. 6, pp. 797813.
Nilsson, N. (1980), Principles of Artificial Intelligence Palo Alto California: Tioga.
Ould and Unwin (1986), Testing in software development, British Computer society Monographs in Informatics.
Partouche, A. (1997), Hybrid method for the general rostering problem with a mixed and homogeneous workforce, Cahier du Lamsade 151, Universit de Paris Dauphine
Perry W. (1995), Effective Methods for Software Testing, Wiley Inc.
Puget, J.F. (1993), On the Satisfiability of Symmetrical Constrained Satisfaction Problems, in Proceedings of ISMIS93.
Rodoek, R., Wallace, M. G., and Hajian, M. T. (1998), A New Approach to Integrating Mixed Integer Programming and Constraint Logic Programming, Annals of Operations Research, to appear.
Smith, B.M., Brailsford, S.C., Hubbard, P.M., H. Williams, H.P. (1996), The Progressive Party Problem: Integer Linear Programming and Constraint Programming Compared, Constraints: An international journal, vol. 1, pp. 119138.
Williams H.P. Model building in mathematical programming (Third edition) Ed. Wiley, 1994.
Structured Bibliography
Introduction to combinatorial optimisation
T.H. Cormen, C.E. Leiserson, and R.L. Rivest (1990)
Introduction to algorithms.
MIT Press, London.
Comprehensive introduction to the modern study of computer algorithms. Although it is not essential to combinatorial optimisation, the book presents many algorithms and covers them in considerable depth. Each chapter presents an algorithm, a design technique, an application area or a related topic. Very good overview of data structures and their implementations.
C.H. Papadimitriou and K. Steiglitz (1982)
COMBINATORIAL OPTIMIZATION: Algorithms and Complexity.
PrenticeHall.
Reference book on the theory of computational complexity. Complexity is seen as the interplay between computation (i.e. complexity classes) and applications (i.e. problems). Completeness results are central to this approach, as well as logic to express and capture computation. Thus computation, problems, and logic are the three main currents that run through the book.
M.R. Garey and D. S. Johnson (1979)
Computers and intractability, A guide to the theory of NPcompleteness
Victor Klee.
Defines NPcompleteness and NPcomplete (NPhard) problems. It constitutes a standard reference on the subject comprising the theory of NPcompleteness, how to prove NPcomplete results, NPhardness, coping with NPcomplete problems, and a list of NPcomplete problems.
Constraint programming
The following references concern general constraint handling methods in the CSP framework and search methods.
Cohen (1992)
Constraint Logic Programming Languages
Communications of the ACM 33(7)
Good introduction to Constraint Logic Programming. Also includes a historical view
Jaffar, Maher (1994)
Constraint Logic programming: A Survey
Journal of Logic Programming, 19/20:503582 1994
This article provides a good survey of the foundations of constraint logic programming, including formal semantics.
V. Kumar (1992)
Algorithms for ConstraintSatisfaction Problems: A Survey
AI Magazine, 13(1), 1992
Clear survey on consistency techniques and basic search techniques.
Marriott, Stuckey (1998)
Programming with Constraints: An Introduction
MIT Press, ISBN0262133415, 1998
This book is the basis for a fourth year university course on constraints programming. It is selfcontained and includes many practical examples and exercises...
Pearl (1984)
Heuristics: Intelligent Search Strategies for Computer Problem Solving
AddisonWesley, ISBN 0201055945
E.Tsang (1993)
Foundations of Constraint Satisfaction
Academic Press Limited, ISBN 0127016104
Reference book on CSPs, consistency techniques, basic search strategies, variable and value ordering heuristics, and optimization in CSPs. Very didactic book.
Van Hentenryck, Simonis and Dincbas (1994)
Constraint Satisfaction using Constraint Logic Programming
in ConstraintBased Reasoning, MIT/Elsevier. ISBN 0262560755
This article offers a brief but comprehensive description of constraint programming over finite domains, including formalisation, examples and benchmark results. The book includes several other important articles on constraints, in particular "Partial Constraint Satisfaction", "Constraint Reasoning based on Interval Arithmetic", and "Minimising Conflicts".
P.VanHentenryck (1989)
Constraint Satisfaction in Logic Programming
MIT Press, Cambridge, MA, USA 1989
M.G. Wallace (1998)
Constraint programming
Chap 17 in the Handbook of Applied Expert Systems, CRC Press, ISBN 0849331064
This article offers a brief but comprehensive description of constraint programming over finite domains, including formalisation, examples and benchmark results. The book includes several other important articles on constraints, in particular "Partial Constraint Satisfaction", "Constraint Reasoning based on Interval Arithmetic", and "Minimising Conflicts".
Operations research and graphs
R.K. Ahuja, T.L. Magnanti and J.B. Orlin (1993)
Network Flows : Theory, Algorithms, and Applications
Prentice Hall, USA
General Operations Research book on graphs and networks algorithms : for paths, flows and multicommodity flows. Many of exercises.
M.Gondran and M.Minoux (1984)
Graphs and algorithms
Series in Discrete Mathematics. Wileyinterscience, Great Britain
General Operations Research book on graphs and algorithms. On how the efficiency of the algorithms depends on the representation of the graph in the computer and the choice of the nodes (decision variables) and arcs (constraints).
H.A. Taha (1995)
Operations Research An introduction, fifth Edition
Prentice Hall International.
Good didactic presentation of the Simplex algorithm. Description of ILP models and decision making problems under risk and uncertainty.
Linear and Integer programming
R.S. Garfinkel and G.L. Nemhauser (1972)
Integer Programming.
Wileyinterscience.
Chvtal (1983)
Linear Programming
Freeman & Company
A very didactic book on the mathematics of the Simplex algorithm. Application to resource problems and network flow problems.
A.Schrijver (1986)
Theory of Linear and Integer Programming.
Discrete Mathematics. Wileyinterscience.
A reference book on the mathematics of linear and integer programming. Difficult, but a good scientific reference.
F.S. Hillier and G.J. Lieberman (1990)
Introduction to Mathematical Programming
McGrawHill
G.L. Nemhauser and L.A. Wolsey (1988)
Integer and Combinatorial Optimization.
Wiley.
A great book that unifies theory and practice. It is about the mathematics of discrete optimisation which includes mathematical modelling, solutions of models, and understanding the mathematics of the algorithms (polyhedral theory, valid inequalities and cuts, general algorithms and special purpose algorithms).
H.P. Williams (1990)
Model Building in Mathematical Programming.
Wiley.
Shows the importance of problem formulation when dealing with discrete optimisation problem. Aspects addressed are for example: problem decomposition, choice of integral decision variables, methods to solve
integer programming problems.
H.P. Williams (1992)
Model Solving in Mathematical Programming.
Wiley.
Offers an understanding of the methods of mathematical programming through numerical examples. The book is centred on the main methods of solving linear and integer programming models. Stimulating text for both students, and software engineers and consultants who wish to understand the subject.
Stochastic search
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.(1983)
Optimisation by simulated annealing
Science, 220: 671680.
The original paper presenting the simulated annealing applied to optimisation. It describes the foundation of the method, the algorithm based on the one introduced by Metropolis, and some convergence results.
F.Glover (1989)
Tabu Search.
In Orsa Journal of Computing, number 1, pages 190206
Describes the TABU local search method, which maintains a TABU list of forbidden moves during the search, preventing both to cycle and to get stuck in a local minima.
D. E. Goldberg.(1989)
Genetic Algorithms in Search, Optimization, and Machine Learning
AddisonWesley, Reading, MA.
This book presents the concept of Genetic Algorithm that comes from an analogy with biological selection. The formalism for data representation as chromosome and useful operators for evolution (crossover, mutation) is described and examples of applications to search, optimisation and machine learning are given.
L. Davis (1989)
Genetic Algorithms and Simulated Annealing
Morgan Kaufmann,.
This book gives the formulation of GA and SA programming, describes specific uses for optimisation, presents comparative results and further advice for practical implementation.
Problem classes and surveys
E. Balas and M.W. Padberg.(1976)
Set partitioning: A survey.
In SIAM REVIEW, volume 18/4.
Good overview of set partitioning problems, and methods based on simplex coupled with branch and cut search.
M.W. Padberg.(1979)
Covering, Packing and Knapsack Problems.
In Annals of Discrete Mathematics, chapter volume 4, pages 265287. NorthHolland Publishing company.
A.I. Hinxman (1980)
The trimloss problem and assortment problems: a survey
European Journal of Operations research
North Holland publishing company, number 5
K.L. Hoffman and M.Padberg (1992)
Solving Airline CrewScheduling Problems by BranchandCut.
Technical Report 376, George Mason and New York University.
Mattfeld, D.C. (1996),
Evolutionary Search and the JobShop,
SpringerVerlag.
Methodology references
EUROMETHOD Project (1996)
Euromethod Version 1 Reference Manual
Rational Software (1997)
Unified Modelling Language, version 1.1
Ould and Unwin (1986),
Testing in software development,
British Computer Society Monographs in Informatics.
F. P. Brooks(1995)
The mythical manmonth: Essays on software engineering
AddisonWesley
Book on software project management. With a blend of software engineering facts and thought provoking opinions, this book offers insight for anyone managing complex projects. The first edition was published in 1975. The new edition is a revision with added chapters.
Perry W. (1995),
Effective Methods for Software Testing
Wiley Inc.
Chamard, A. Fischer, B. Guinaudeau and A. Guillaud (1995)
CHIC lessons on CLP Methodology
Report, Dassault Aviation
Annex B: existing Classes of methods
7.1 Properties of standard solvers A. GOTOBUTTON _Toc449250119 PAGEREF _Toc449250119 10
7.2 Properties of decision strategy methods A. GOTOBUTTON _Toc449250120 PAGEREF _Toc449250120 13
Properties of standard solvers
The following solvers are simple to use and are applied to welldefined algebraic models. The tricky part might be to find out whether your problem can be formulated in terms of a welldefined model. There are three main classes of standard solvers: Linear Programming, Constraint Programming and stochastic search methods.
Linear Programmingand Algorithms.LP algorithms are optimisation algorithms that produce global optimum solutions to a set of constraints in linear form. They can tackle problems with many thousands of variables and constraints. LP solvers require a standard form of model that consists of an objective function and linear constraints applied to the variables of the problem.
EMBED Unknown
Additionally, LP methods are a first candidate if the problem can be formulated as a matching or a flow problem. However, it is quite difficult to identify a matching or flow problem given an LSCO since many problems can actually be seen as min/max weight flows with various capacity constraints. Descriptions of such models can be found in Williams (1994).
Experience has shown, though, that when a problem or subproblem has a simple algebraic model, one should try to consider a more streamlined version of the simplex method which exploits their special structure. A number of additional algorithms, based on the simplex method and thus retaining the computational efficiency, can be found and used from common software packages: dual / revised simplex, upper bound techniques, parametric LP etc.
Constraint Propagation algorithms. Constraint propagation is a technique, used in conjunction with search algorithms, to reduce the search space by removing parts where there is guaranteed to be no solution. Typically it is applied to problems, or subproblems, each of whose variables has a "domain" of possible values. The effect of propagation is to reduce the domains of the variables by removing values which could not take part in any solution.
Propagation can be applied both to symbolic domains (for example colours, in a map colouring problem) and to numeric domains. For continuous numeric domains a specific technique known as interval propagation can be applied, which simply narrows the bounds of the domain. For discrete domains, propagation can in principle remove arbitrary values from a domain.
There are a great variety of propagation algorithms, both generic and constraintspecific. For example AC5 is a generic algorithm which can be tailored to achieve very high efficiency for specific classes of constraints. AC5 reduces the domains of the problem variables until it reaches an "ArcConsistent" state (hence AC). Under certain assumptions, arcconsistency is the best reduction possible. An example of constraintspecific propagation is an algorithm designed for the "alldifferent" constraint, which constrains any set of variables to take different values. Specific propagation algorithms have been designed for a many constraints, such as resource constraints, sequencing constraints, sorting constraints and set constraints, and further propagation algorithms are continuously under development.
In solving a problem, different propagation algorithms will be applied to different sets of constraints: thus constraint propagation can be tuned very finely to the application requirements.
Stochastic algorithms. These methods are essentially optimisation methods that do not require a specific algebraic modelling except that the model must have an optimisation function. They are commonly used when the search space is too large to explore and thus when a global iterative optimisation algorithm is not acceptable. Such methods do not yield to optimal solutions in general but try to improve the value of the cost function by making local searches to find improvements.
Properties of decision strategy methods
Decision strategy methods comprise heuristics, local optimisation, lower bounds and search methods. They do not require the problem formulation to be in a specific form. However, being decision strategies their modelling might be more or less embedded in the algebraic model.
The properties of these methods are presented here in increasing degree of modelling difficulty.
Heuristics. A heuristic means a deterministic way to build a good solution. It is very often a greedy heuristic that takes a set of decisions in a given order with the idea of not coming back to a previous decision. It may also be obtained by using a smarter algorithm such as a flow algorithm. Finding a good heuristic can be very important since it will be used as an upper bound in the search and as a seed in a local optimisation strategy. The heuristic should ideally model the current best practice of the customer, which is most of the time a greedy decision process. This will also be very convenient when trying to demonstrate any improvement to the customer. Heuristics should be designed and embedded in the current algebraic model, by considering their semantics and iterative decision making.
Local Optimisation. Local optimisation is about how to improve a current solution by making a small change. The first and hard step is to define the neighbourhood, that is the set of small changes that might bring an improvement. Standard stochastic methods propose some types of local moves. But in general, this part requires a lot of intuition and knowledge (bibliographic work is usually needed). Once the neighbourhood is defined, the techniques for exploiting them are fairly standard and a local optimisation framework can be used. Just like heuristics, local optimisation does not require a specific algebraic model, but should however, be specified and embedded in the algebraic model.
Lower Bounds: before starting the development of a search, it is a good idea to try to evaluate how far the best solution found so far is from optimal. The development of a lower bound algorithm is difficult and does not always succeed. There are a few general techniques, very often based on a relaxation of the problem. The two most classical are the linear relaxation, where the values are assumed to be real numbers and only the linear constraints are kept. This allows us to use a simplex algorithm to compute a lower bound. The other classical technique is Lagrangean relaxation, where the most difficult constraints are pushed into the optimisation function. If a search algorithm is planned to be used, it is important to focus on incremental techniques, which may be more difficult to find. In that case, the most common technique is pure relaxation, obtained by dropping enough constraints such that the optimal solution is easy to compute (incrementally). This method might require a revision of the algebraic model in the sense that a hierarchy in the satisfiability of the constraint set might be necessary.
Search Techniques: in constraint programming and integer linear programming problems, once all the previous components have been considered, a search technique is defined by the branching strategy and the control strategy. As for the local optimisation process, the most difficult and problemdependent part is the branching strategy. A good generic approach is to use the decision tree deduced from the greedy heuristic. However, this requires good intuition and a fair amount of experimentation. Once a branching strategy is found, there are a lot of search techniques available depending on the size of the problem. Limited discrepancy search is a very useful framework (as a global philosophy) that can be reused from one problem to the other. The idea is simply to control and limit the number of actual branching nodes by selecting only those for which there is no good way to choose one alternative rather than the other. This approach might not require any revision or enhancement in the algebraic model.
Annex C: Examples Of programs
8.1 The transportation problem with LPTOOLKIT in Visual Basic A. GOTOBUTTON _Toc449250122 PAGEREF _Toc449250122 15
8.2 Example of CLAIRE code A. GOTOBUTTON _Toc449250123 PAGEREF _Toc449250123 17
8.3 Example of ECLiPSe code A. GOTOBUTTON _Toc449250124 PAGEREF _Toc449250124 19
The transportation problem with LPTOOLKIT in Visual Basic
In this example, the data are in an Excel Worksheet TransSheet. We give hereafter the Visual Basic code which is in a Visual Basic Module within the same worksheet.
'**********************************************************************
' TRANSPORTATION MODEL : LPTOOLKIT + XPRESS (or CPLEX)+ EXCEL
' EURODECISION (C) , march 1998
'**********************************************************************
' Public declaration of data structures
Public ni, nj As Integer
Public cost As Variant ' transportation costs
Public demand As Variant ' clients demands
Public capacity As Variant ' capacities of the depots
Public xValue() As Double ' results of the transportation model
' declare the transportation model, variables and constraints
Public transProb As Long
Public x() As Long ' variables x(i,j)
Public Cst As Long ' constraints (do not store dual values)
Public Function TransModel()
Dim i, j As Integer
Dim costVar, xinf, xsup, binf, bsup As Double
Dim test As Long
MsgBox "Transolve()"
' Problem instantiation with LPTOOLKIT
' Replace XPRESS by CPLEX for a solution with CPLEX solver.
transProb = newProb("XPRESS", 100000)
' build transportation model
' initialise to 0 data structures for variables
For i = 1 To ni
For j = 1 To nj
xValue(i, j) = 0
x(i, j) = 0
Next j, i
' variables creation
For i = 1 To ni
For j = 1 To nj
x(i, j) = newVar1(cost(i, j), zero, infin, xValue(i, j))
Next j, i
' demand constraints
For j = 1 To nj
Cst = newConst(demand(j), demand(j)) ' by reference
For i = 1 To ni
test = newElt(Cst, x(i, j), 1#)
Next i
Next j
' depot capacity constraints
For i = 1 To ni
bsup = capacity(i)
Cst = newConst_(zero, bsup) ' by balue
For j = 1 To nj
test = newElt(Cst, x(i, j), 1#)
Next j
Next i
' solve model
test = optimise()
End Function
' Function Trans() recovers data, build model and save results
Public Function Trans()
Dim i, j As Integer
Dim costVar, xinf, xsup As Double
Dim returnCode As Long
' transfer data from the worksheet to tables cost, demand and capacity
cost = Worksheets("TransSheet").Range("COST").value
ni = UBound(cost, 1) ' ni = number of depots
nj = UBound(cost, 2) ' nj = number of clients
demand = Worksheets("TransSheet").Range("DEMAND").value
capacity = Worksheets("TransSheet").Range("CAPACITY").value
ReDim xValue(1 To ni, 1 To nj), x(1 To ni, 1 To nj)
MsgBox "Depots : & ni & Clients : " & nj
' build and solve model
returnCode = TransModel()
' transfer results in Worksheet, at range X.
Worksheets("TransSheet").Range("X").value = xValue
' delete problem
deleteProb (transProb)
End Function
Example of CLAIRE code
Here is an example of the use of the CLAIRE platform for solving optimisation problems. The problem is a high school time tabling problem for one class: a set of lessons need to be scheduled during the week in order to satisfy as much as possible the teachers preferences. This problem is solved by a hybrid combination of finite domain constraint propagation and relaxation (using the ECLAIR constraint propagation library). The problem can be modelled with the following data structures:
// a week contains m (40) 1hour time slots in which one
// needs to place a total amount of k (<= 40) lesson hours
Problem <: object(m:integer = 40,
k:integer,
Cost:Var,
Happy:Var)
PROBLEM :: Problem()
TimeSlot :: (1 .. PROBLEM.m)
Solver <: object(redundant1:boolean = true,
redundant2:boolean = false)
// a 1hour chunk from a lesson
TimeUnit <: object(v:Var)
Lesson <: thing(units:list[TimeUnit],
start:Var,
halfDay:Var,
prefs:list[TimeSlot],
duration:integer)
Note here that the instance of the problem is stored in an object, that the algorithm and its resolution parameters (a Boolean flag indicating whether a redundant constraint will be used) is also stored in an object. All objects from the class lesson feature a list of TimeUnits (1 hour chunks of lessons) and have a set of preferred starting times (the teachers preferences). Each time unit is associated a variable indicating the time slot (1  40) of the week to which it will be scheduled. Finally, the half day (1  10) in which the lesson will be scheduled is also represented.
The following procedure reads the data file (creation of instances of Lesson) and creates all finite domain variables (the parameter to the call to makeVar indicates the initial domain of the variable). It also states the constraints that the list of variables L.units must take consecutive values (all 3 units of a 3hour lesson must be performed in sequence).
createVars(n:integer)
(readData(),
for L in Lesson
(L.start := makeVar(TimeSlot),
L.units := list{(L.start + i)  i in (1 .. L.duration)},
for k in {k in TimeSlot  (k  1) mod 4 + duration(L) > 4)}
L.start isnot k,
if SOLVER.redundant L.halfDay := L.start div 4),
for i in (1 .. PROBLEM.n  PROBLEM.m)
TimeUnit.v = makeVar(TimeSlot),
PROBLEM.Cost := makeVar(),
PROBLEM.Happy := makeVar(0,size(instances(Lesson))) )
Note here that we forbid starting time that would make a course overlap over two different half days. We can now describe the preemptive relaxation: we will find an (preferencewise optimal) assignment of TimeUnits (chunks of lessons) to TimeSlots in the week. There are PROBLEM.m time slots, PROBLEM.k chunks of lessons and we define a cost matrix mcost such that the total cost of a feasible solution with respect to this relaxation is
(PROBLEM.m  PROBLEM.k) * CMAX // units not corresponding to lesson chunks
+ PROBLEM.k * FEASIBLE // units corresponding to lesson chunks
PREFERRED * size({l in Lessons  l.start belongs to l.prefs})
// units corresponding to lessons placed at a preferred time slot
CMAX :: 10000
FEASIBLE :: 1000
PREFERRED :: 12
mcost[i:TimeUnit, j:TimeSlot] : integer := CMAX
setCosts()
(for c in Lesson
for k in (1 .. length(units(c)))
for j in domain(c.start)
mcost[units(c)[k],j + k  1] :=
(if j(prefs(c) FEASIBLE
else FEASIBLE  PREFERRED / duration(c)) ))
We can now set all constraints and in particular the weightedBijection constraint defining the relaxation: this constraint will compute the minimal weight assignment between TimeUnits and TimeSlots, with respect to the cost matrix mcost and update the lower bound of the variable PROBLEM.Cost with the optimal value of the relaxed problem.
Note that depending on the values of the flag redundant of the solver, we decide whether to state or not a redundant constraint which ensures that all lessons lasting more than 3 hours occur during different half days.
setConstraints()
(weightedBijection(list{tu.v  tu in TimeUnits},
TimeSlot,
PROBLEM.Cost,
mcost),
PROBLEM.Cost == 1000 * PROBLEM.m  12 * PROBLEM.Happy,
if SOLVER.redundant
AllDifferent({l.halfDay  l in {l in Lesson  l.duration >= 3}}) )
We can now describe the recursive procedure that searches for one solution
search(n:integer) : boolean
let bestv := 1000000, c := unknown in
(for c2 in Lesson
(if unknown?(value,c2.start)
let v := card(c2.start) in
(if (v < bestv) (bestv := v, c := c2))),
if (bestv = 1000000) true
else if exists(x in {x in c.start.domain  x(c.prefs} 
branch( (c.start == x, search(n + 1))))
true
else if exists(x in {x in c.start.domain  x(c.prefs}
branch( (c.start == x, search(n + 1))))
true
else false)
Example of ECLiPSe code
This example of ECLiPSe code represents the ship loading problem and its resolution. The problem was introduced in [JFPL92]. It involves 34 tasks, each of which has a specific manhours requirement, which can be achieved by more people in less time, if the resources are available.
The example illustrates four features of ECLiPSe:
The facility to combine multiple solvers (here two libraries)
The facility to structure the data (static object orientation)
The facility to separate constraint handling from search
The facility to control search at a high level (the level of the conceptual model)
% This particular problem uses the following two solver libraries. Most
% practical applications of ECLiPSe also involve a linear solver, such as
% XPRESS or CPLEX
: lib(fd).
: lib(edge_finder).
% For this problem a specific data structure is introduced to model
% tasks. In this application a task has a start time, a duration, required
% resources, and successors (tasks which cant start until this task has
% finished). Each task also has an area which is the number of manhours
% needed for its completion. Attributes of tasks can be accessed
% individually, and if extra attributes are added to support newly required
% facilities, there is no need to change anything in the program except the
% structure definition.
: define_struct(task(start,area,dur,req,succ)).
% The data model specifies the constraints on the tasks of the problem.
% This data model is
% logical: it does not address algorithmic search issues.
shiploading_model(ResourceLimit, Tasks, EndTime) :
Tasks = [
T01, T02, T03, T04, T05, T06, T07, T08, T09, T10, T11, T12,
T13, T14, T15, T16, T17, T18, T19, T20, T21, T22, T23, T24,
T25, T26, T27, T28, T29, T30, T31, T32, T33, T34, Tend ],
T01 = task with [area:12,succ:[T02,T04,Tend]],
T02 = task with [area:16,succ:[T03,Tend]],
T03 = task with [area:12,succ:[T05,T07,Tend]],
...
T31 = task with [area:6,succ:[T28,Tend]],
T32 = task with [area:3,succ:[T33,Tend]],
T33 = task with [area:6,succ:[T34,Tend]],
T34 = task with [area:6,succ:[Tend]],
Tend = task with [start:EndTime,area:0,dur:0,req:0,succ:[]],
% CONSTRAINTS
% precedence constraints
( foreach(task with [start:Si,dur:Di,succ:Succi], Tasks) do
Si #>= 1,
( foreach(task with [start:Sj], Succi) do
Sj #>= Si+Di
)
),
% surface constraints
( foreach(task with [area:A,dur:D,req:R],Tasks) do
D #>= 0,
R :: 0..ResourceLimit,
D*R #= A
),
% Note that foreach can be used to iterate over a known list (such as
% Tasks), or to create lists (such as Starts, Durations, Resources and
% Areas).
( foreach(T,Tasks), foreach(S,Starts), foreach(D,Durations),
foreach(R,Resources), foreach(A,Areas) do
T = task with [start:S,dur:D,req:R,area:A]
),
cumulative(Starts, Durations, Resources, Areas, ResourceLimit).
% solve is the main procedure that defines the model, calls the
% optimisation procedure and outputs the optimal solution. Only now is the
% search algorithm addressed in the program.
solve(ResourceLimit) :
shiploading_model(ResourceLimit, Tasks, EndTime),
min_max(labelling(Tasks), EndTime).
writeln("Optimum" = EndTime),
( foreach(task with [start:S], Tasks), fromupto(1,I,_) do
printf("Task %d starts at time %d\n", [I,S])
).
% This is the search procedure that assigns a start and duration for each
% task.
labelling(Tasks) :
( foreach(task with [start:S,dur:D], Tasks) do
indomain(S), indomain(D)
).
Annex D: Problem category definition
TOC \o "14"
9. ANNEX D: PROBLEM CATEGORY DEFINITION A. GOTOBUTTON _Toc449250125 PAGEREF _Toc449250125 21
The following list gives a broad description of LSCOs based on application type. The table is organised around two classes of applications, ones that involve some scheduling or time components, and ones that deal essentially with assignment or allocation of entities. A more complete list of pure problem instances can be obtained from [Garey & Johnson 79].
PLANNING/SCHEDULING
Car SequencingGiven: A set of cars to be produced in a given time, a large set of constraints to ensure a continuous flow of production, and the capacity limits of producing cars with given options
Find: A schedule of vehicles on the production line that satisfies the constraints and minimises the production costs.
Crew SchedulingGiven: A set of crews and vehicles (planes/buses/trains) with restrictions coming from crew preferences, personnel regulations and various costs
Find: An allocation of one crew per vehicle on each journey that minimises the costs.
Fleet SchedulingGiven: A set of scheduled flights with their respective forecast passenger demand, aircraft from a given set of fleets with their capacity, costs,
Find: An allocation of aircraft that minimises cost.
Jobshop SchedulingGiven: A set of jobs to perform (and tasks within each job) with due dates, a set of machines such that due dates constrain the jobs and the machines have limited capacity,
Find: An assignment of start times and machines to jobs (and tasks within each job) that maximises machine utilisation and minimises time to complete all the jobs
Production SequencingGiven: A set of products to be manufactured, an assembly line with various options requiring special processes such that some sequences of products can not take place.
Find: A sequence of products on the assembly line.
Staff SchedulingGiven: A set of employees, with different profiles, skills and preferences, to accomplish task in a given time span (daily, weekly,)
Find: A schedule of the employees that respect the constraints and satisfies the preferences as much as possible.
Shift PlanningGiven: A set of shifts and a workforce of employees with different skills
Find: A daily/weekly/monthly plan that has an appropriate range of skills at all times.
Vehicle Routing/SchedulingGiven: A set of customers to visit using a fleet of vehicles, respecting constraints on the vehicles, customers, drivers
Find: A low cost routing plan specifying for each vehicle the order of the customer visits they make.
Workforce SchedulingGiven: A set of jobs, at geographically dispersed locations, and a set of engineers, such that jobs require different skills, and their order and times of execution may be constrained. The duration of jobs may be fixed, or stochastic
Find: An allocation of jobs to engineers.
ALLOCATION/ASSIGNMENTS
Bin PackingGiven: A set of objects with their weight (or length, size) and a set of bins with their maximum capacity (weight or size)
Find: An assignment of each object to a bin such that the number of bins used is minimised
Cutting StockGiven : Raw materials (e.g. cloth/wood/metal etc.) and a set of orders in terms of pieces of material (dimensions) to obtain from the raw material
Find: A cutting up the raw material that satisfies all the orders with minimum wastage
Knapsack Given: A set of objects with their properties (its size and value) and a knapsack with its size
Find: A subset of objects that maximises the total value while fitting into the knapsack
Network FlowGiven: A set of sources of material with an upper capacity limit on the number of sinks it can supply, and a set of sinks with a demand profile of material, a set of arcs (flows) from the sources to the sinks with their capacity limit and a set of cost for each material shifted through an arc
Find: A supply of the sinks from the sources at minimal cost
Portfolio managementGiven: A set of financial instruments with their price, risk exposure and demand cover
Find: A portfolio that maximises profits and minimises risks
Production MixGiven: A set of products to manufacture and constraints on the availability of raw materials, production facilities and cost
Find: The quantities of different products to manufacture that maximises profit
TimetablingGiven: A set of people (e.g. instructors), locations (e.g. class rooms), and activities (e.g. courses), such that people perform a activity at a time in one location at a time
Find: A timetable of peoplelocationsactivities over a prefixed period that maximises the preferences of the people.
Annex E: Didactic example: The Inventory Management Application
10.1 Problem definition A. GOTOBUTTON _Toc449250127 PAGEREF _Toc449250127 24
10.1.1 Problem overview and structure A. GOTOBUTTON _Toc449250128 PAGEREF _Toc449250128 24
10.1.1.1 Objectives A. GOTOBUTTON _Toc449250129 PAGEREF _Toc449250129 24
10.1.1.2 Input data A. GOTOBUTTON _Toc449250130 PAGEREF _Toc449250130 24
10.1.1.3 Output data A. GOTOBUTTON _Toc449250131 PAGEREF _Toc449250131 24
10.1.2 Conceptual model A. GOTOBUTTON _Toc449250132 PAGEREF _Toc449250132 25
10.1.2.1 Input data A. GOTOBUTTON _Toc449250133 PAGEREF _Toc449250133 25
10.1.2.2 Ouput A. GOTOBUTTON _Toc449250134 PAGEREF _Toc449250134 25
10.1.2.3 Constraints A. GOTOBUTTON _Toc449250135 PAGEREF _Toc449250135 26
10.1.2.4 Decision criteria A. GOTOBUTTON _Toc449250136 PAGEREF _Toc449250136 26
10.1.3 Other requirements A. GOTOBUTTON _Toc449250137 PAGEREF _Toc449250137 27
10.2 Problem design A. GOTOBUTTON _Toc449250138 PAGEREF _Toc449250138 28
10.2.1 Problem Solution Deliverable 1 A. GOTOBUTTON _Toc449250139 PAGEREF _Toc449250139 28
10.2.1.1 Problem features and structure A. GOTOBUTTON _Toc449250140 PAGEREF _Toc449250140 28
10.2.1.2 Algorithm characterisation A. GOTOBUTTON _Toc449250141 PAGEREF _Toc449250141 28
10.2.1.3 Problem design A. GOTOBUTTON _Toc449250142 PAGEREF _Toc449250142 29
10.2.2 Problem Solution Deliverable 2 A. GOTOBUTTON _Toc449250143 PAGEREF _Toc449250143 31
10.2.2.1 Problem features and structure A. GOTOBUTTON _Toc449250144 PAGEREF _Toc449250144 32
10.2.2.2 Algorithm characterisation A. GOTOBUTTON _Toc449250145 PAGEREF _Toc449250145 32
10.2.2.3 Problem design A. GOTOBUTTON _Toc449250146 PAGEREF _Toc449250146 32
10.2.3 Problem Solution Deliverable 3 A. GOTOBUTTON _Toc449250147 PAGEREF _Toc449250147 34
10.2.3.1 Problem features and structure A. GOTOBUTTON _Toc449250148 PAGEREF _Toc449250148 34
10.2.3.2 Algorithm characterisation A. GOTOBUTTON _Toc449250149 PAGEREF _Toc449250149 34
10.2.3.3 Problem design A. GOTOBUTTON _Toc449250150 PAGEREF _Toc449250150 36
10.3 Concluding remarks A. GOTOBUTTON _Toc449250151 PAGEREF _Toc449250151 39
The purpose of this example is to take you through the different steps of the methodology using an application tackled in the CHIC2 project. The application is an inventory management problem from a construction company. We wish to illustrate that different designs and implementations can be applied to a single problem. The diversity comes from 1) the technology background of the LSCO team,
the amount of work that has been put into the problem,
3) the results of previous work that give hints for new ideas,
4) the implementation support available.
Together with the problem definition and different design models, we give the background of the LSCO team, together with some indicative information about the time spent in design and implementation work. This example takes you through three of the five approaches applied to the inventory management problem within the CHIC2 project.
Problem definition
The problem definition is presented using the structure of the Problem Definition Deliverable (PDD)
Estimated time:
The definition work carried out with the client (user requirement capture) has taken approximately 20 mandays.
The building of the PDD in its current form, comprising a validation of the user requirements against the LSCO team understanding (conceptual model) has taken approximately 40 mandays.
Problem overview and structure
No organisational decomposition is required and the unique module consists of the whole problem with the following objectives, input and output data:
Objectives
Inventory management consists of managing a given (though evolving) fleet of equipment in order to satisfy given and already scheduled requests to use it. When requests exceed the stock of available equipment, a decision has to be made either to subcontract some requests to another provider or to purchase new pieces of equipment. The main difficulty lies in the fact that a subcontracted request must be subcontracted for all the duration of the request. For example, if a subcontracted car is rented to a given customer, this customer will keep the subcontracted car for all the duration of the rental. The overall problem consists of determining
which orders have to be subcontracted
which resources are allocated to those orders that are not subcontracted
when to buy new items and how many have to be bought
at what time the resources are maintained
so that all the constraints are satisfied and the entire cost of the operations is minimal.
Input data
The input data are the set of orders and their attributes, the different resource types and the ways in which resources may be substituted for each other on it, the number of items of each resource type and all their attributes, the cost of maintenance per item, the maintenance capacity.
Output data
The output data describe the solution required by the client. It consists of the number of items of a given type subcontracted for the different orders, the set of items bought at a given time, the set of items of a given type allocated to an order, the maintenance schedule (starting time for each item of a given type).
Conceptual model
The conceptual model is structured in terms of four components: Input, output, constraints, decision criteria. It gives a full description of the problem. Due to the complexity of a natural language description, we provide as well a formal description based on the use of functions and sets. It remains independent of any solution method and implementation language.
Let R = {r1, r2, ..., rk} be a set of resource types. We say that the resource type ri subsumes the resource type rj (ri ( rj) if all units of type rj can be substituted by units of type ri. The Inventory Management Problem is defined as follows.
Input data
Set of resource types and the subsumption relation defined on it. (R, ()
For each resource type in R, we have:
set of items of type r available in stock at time t Stock(r,t)
maximal time of use of an item without maintenance Utime(r)
maintenance time of an item (unpreemptive task) Mtime(r)
number of capacity units required for the maintenance of a resource of type r. Mcap(r)
external renting price (in FF per time unit) Crent(r)
fixed cost of the allocation of an item to an order (FF) Cafix(r)
time dependent cost of the allocation of an item to an order (in FF per time unit) Catd(r)
period length dependent purchase cost of an item (F) Cbuy(r)
cost of a purchased item (used or not) in stock (F per time unit) Cstock(r)
cost of maintenance of an item (F per maintenance) Cmaint(r)
The capacity of the maintenance workshop MCAP
A discrete time period for the problem [Start, End]such that Start, End ( ( and Start ( End
Set of orders O
For each order o in O,
start time of o, such that st(o) ( ( and Start ( st(o) < End st(o)
end time of o, such that et(o) ( (, st(o) < et(o) ( End et(o)
required resource type rtype(o)
required number of rtype(o) for the order o rq(o)
Ouput
A solution is a valuation for the functions
number of items of type r from external rentals (subcontracts) for the order o rent(r,o)
set of items of type r bought at time t buy(r,t)with Stock(r,t) = Stock(r,t1) ( buy(r,t)
set of starting time of maintenance for the item u of type r maint(r,u)
set of items of type r allocated to the order o alloc(r,o)with alloc(r,o) ( Stock(r,st(o))
Constraints
The allocated and rent resources to an order correspond to the required resource type of the order:
EMBED Unknownand
EMBED Unknown
All orders are satisfied,EMBED Unknown
The same item is not allocated to two orders which intersect in time. For all o and o intersecting orders in O (that is st(o) ( st(o) < et(o)):
EMBED Unknown
for all items u of type r there is a maintenance after at most Utime(r) effective use.
at each moment the sum of maintenance capacities required by the items in maintenance should be inferior to the capacity of the maintenance workshop.
Decision criteria
An optimal solution is a solution where the cost function F is minimal. The function F composed of three parts.
First the cost of external rentals and resource allocations from existing stock:
EMBED Unknown,
then the cost of purchase: EMBED Unknown,
and the cost of the maintenance: EMBED Unknown
The cost function is defined as the sum of the three previous functions:
EMBED Unknown
Other requirements
The PDD contains other requirements in terms of GUI functionality, technical aspects (software and hardware requirements) and business aspects. We did not consider them at this stage of the project. Thus they are not yet part of the problem definition, but other extensions are illustrated below.
As a note for future stages in the development, we wish to add that the manager of the warehouse can make prior decisions, which restrict the problem data. For example, resource allocations can be constrained (e.g. such resource is allocated to such request), purchase can be limited, or the maintenance plan can be partially defined. All these are not considered by the current problem definition.
Moreover, in the realworld application, predefined data is in general uncertain, especially when the time period under consideration is long: requests can be cancelled or modified, resources can break down, and so on. In the current problem definition, we assume that the time period is not too long, so that the data can be considered certain.
Problem design
The design work consists of characterising the algorithm and formulating the problem in a form that suits the algorithm. Different designs have been derived and tested by implementation work. We present three of the five models that have been derived by different partners in the project. Although so many models might not always be developed, it demonstrates the importance of investigating different approaches to get more insight on the actual complexity of the problem and identify new algorithms which take into account the problem features, improve efficiency or get closer to optimality.
Problem Solution Deliverable 1
Estimated time:
The design work coupled with implementation was allocated approximately: 12 man days.
The writing up of the PSD has taken approximately: 6 man days.
The following PSD describes the problem model and algorithm implemented using ECLiPSe, a constraint logic programming platform. It makes use of linear programming. The linear solver used was CPLEX, callable as an ECLiPSe library. The LSCO expert has been using ECLiPSe for several years and had at his disposal modelling facilities in ECLiPSe, allowing him to model the problem in a Prolog environment that remains generally independent of the algorithm used.
Problem features and structure
This approach uses a technical decomposition where the core problem corresponds to the resource allocation part of the inventory management where maintenance and purchase are not considered. The core problem is a linear problem. The resource allocation problem deals with the allocations of the equipment to requests and determines which requests have to be subcontracted, which items are allocated to those requests which are not subcontracted. Thus the decomposition consists of core problem + maintenance + purchase.
Algorithm characterisation
The core idea is to use mathematical programming techniques to tackle the linear constraints. Then to extend the optimal solution returned by the linear solver using a finite domain solver that tackles the maintenance constraints. If such an extension does not exist, the CPLEX solver is called again on a modified problem containing orders with longer duration to leave room with anticipation for maintenance. The procedure is repeated until a solution of the whole problem is found.
This algorithm is a hybridisation of a finite domain solver and a mathematical programming solver. The implementation showed that the linear programming part of the solver was sufficient to obtain integral optimal solutions (without branch and bound search).
Problem design
The model considers the search for an optimal solution with respect to external rentals and item allocations from existing stocks. In this model an integer identifier of each order corresponds to each type of item. The identifier represents the number of items which are allocated to a given order.
Data model
The data model is based on a relational representation of the data (to be fed later on to the constraint logic programming model in ECLiPSe).
Algebraic model for the core problem
Sets and indices
Let O={o1, , on} be a set of orders.
Let R={r1, , rm} be a set of item types.
Input data
subs(ri,rj) item type ri subsumes the item type rj.
Stock(r) the number of items of type r.
Crent(r) external renting price for an item of type r.
Cafix(r) fixed cost of the allocation of an item of type r to an order.
Catd(r) time dependent cost of the allocation of an item of type r to an order.
st(o) start time of order o.
et(o) end time of order o.
rtype(o) required item type to order o.
rq(o) required number of items for order o.
Decision variables
a(r,o) integer indicating the number of allocated items of type r to order o.
Constraints
allocated items to an order correspond to the required item type of the order.
a(r,o) = 0 for r ( rtype(o) and not subs(r, rtype(o))
a(r1,o) + + a(rm,o) ( rq(o)
the same item is not allocated to two orders which intersect in time. For every set {oi1,...,oik} of orders which intersect in time:
a(r,oi1) + + a(r,oik) ( Stock(r)
Objective functions (criteria to minimise)
An optimal solution is a solution where the cost function C1 is minimal. The function is composed of external rentals and item allocations from existing stock:
C1 = (r (o ( Crent(r) ( (rq(o) a(r,o)) + a(r,o) ( (Cafix(r) + Catd(r) ( (et(o) st(o))))
Algebraic model for the core problem with maintenance
The problem without purchase represents an extension of the core problem by considering also the maintenance of items. The problem has been successfully solved by using a linear programming approach on the core problem and constraint reasoning on the maintenance part of the whole problem.
Sets and indices
Let O={o1, , on} be a set of orders.
Let R={r1, , rm} be a set of item types.
New input data
Utime(r) : maximal time of use of an item of type r without maintenance.
Mtime(r ) : maintenance time of an item of type r.
MCAP : the maximum number of workers.
Decision variables
a(r,o) : integer variable indicating the number of allocated items of type r to order o.
b(i,o) : Boolean variable indicating that item i is allocated to order o.
s(i,k) : integer variable indicating the start time of the kth maintenance of item i.
w(i,k) : integer variable indicating the worker who handles the kth maintenance of item i.
New constraints
the same item is not allocated to two orders which intersect in time. Let i1, , ij be the items of type r. For every set {o1, .., ok} of orders which intersect in time:
b(i1,o1) + + b(i1,ok) ( 1
b(ij,o1) + + b(ij,ok) ( 1
b(i1,o1) + + b(ij,o1) = a(r, o1)
b(i1,ok) + + b(ij,ok) = a(r, ok)
the maximal time of use of an item without maintenance should not be longer than Utime(r):
(cond1(i,k) (b(i,oj) ( (et(oj) st(oj)) ) ( Utime(r)
where
cond1(i,k) is true iff ( s(i,k) + Mtime(r) ( st(oj) ) and ( et(oj) ( s(i,k+1) )
at each time the sum of maintenance capacities required by the items in maintenance should be inferior to the capacity of the maintenance workshop:
w(i,k) ( MCAP
if s(i,k) ( s(i,k) ( s(i,k) + Mtime(r) then w(i,k) ( w(i,k)
Objective functions (criteria to minimise)
An optimal solution is a solution where the cost function C1+ C3 is minimal. The function is composed of external rentals, item allocations from existing stock and the cost of the maintenance.
C3 = (r,i,k ( Cmaint(r) ( s_flag(i,k) )
where
if w(i,k) > 0 then s_flag(i,k) = 1 else s_flag(i,k) = 0
Algebraic model for the whole problem (with maintenance and purchase)
The inventory management problem with purchase represents an extension of the core problem by considering purchase as well as the maintenance of items. The problem has been successfully solved using the solution strategy described previously.
The objective of the model is to search for an optimal solution with respect to external rentals, item allocations form existing stock, purchase and the cost of the maintenance. To consider purchase in the problem, the model in the previous section can be extended by additional new variables and constraints.
New input data
Cbuy(r) : cost of purchase of a resource of type r
Cstock(r) : cost of stocking a purchased resource of type r, per time unit
New decision variables
rq(r,t): integer variable indicating the number of items of type r at time t.
p(r,t): number of items of type r purchased at time t.
New constraints
for every set {o1, .., ok} of orders which intersect in time t:
a(r,o1) + + a(r,ok) ( rq(r,t)
for every time t:
p(r,t) = rq(r,t) rq(r,t1)
Objective functions (criteria to minimise)
An optimal solution is a solution where the cost function C1+ C2 + C3 is minimal where C2 becomes :
C2 = (r(t ( Cbuy(r) ( p(r,t) + Cstock(r) ( p(r,t) (Endtime t) )
The function is composed of external rentals, item allocations from existing stock, the cost of purchase and maintenance cost.
Problem Solution Deliverable 2
Estimated time:
The design work coupled with implementation has taken approximately 25 man days
The writing up of the PSD has taken approximately 5 man days
The second model has been designed and implemented using the CLAIRE language, an object oriented language enhanced with a scheduling library (CLAIRE Schedule). The LSCO team is expert in scheduling problems, algorithm and development.
Problem features and structure
In the previous design and implementation works (see PSD1), it was observed that the core resource allocation problem was solved without backtracking, using CPLEX. This encouraged us to perform an extended complexity analysis of the problem. First, it is shown that the core resource allocation problem is polynomial and that its intuitive integer linear programming formulation is solved by linear programming. More precisely, the matrix of the integer linear programming formulation is shown to be totally unimodular, which implies that the solution returned by the linear relaxation is guaranteed to be integral. Three extensions of the core problem have been studied: (1) the extension in which buying is allowed; (2) the extension in which resource substitutions are allowed; and (3) the extension in which maintenance constraints apply. The first extension has been shown to remain polynomial, while the two others are NPhard. In this illustrative example we present the model for the third extension only.
Algorithm characterisation
The algorithm considers a technical decomposition into successive allocation problems. The basic idea is that more or less strong relaxations of maintenance constraints are taken into account at each step of the algorithm. The resulting allocation of orders to items is used as a basis to solve the whole problem. More precisely, we first solve a meta resource allocation problem, derived from the LP formulation, which takes into account some of the maintenance constraints. We rely on the results of this meta resource allocation phase to heuristically allocate orders to items. Given this heuristic allocation, we use a second MIP formulation to find a good solution in which maintenance can be interrupted. Last, given this solution, we use a branch and bound algorithm with constraint propagation to compute a feasible solution where maintenance can not be interrupted.
Problem design
Data model
The data model used is an objectoriented model of the conceptual model presented in the PDD. Input data, orders, resource types and resources are represented as instances of the corresponding classes. Resource type, or order dependent variables are implemented as slots of the corresponding classes (i.e. Crent is a slot of the Resource_type class, st and en are slots of the Orders class, etc.).
The representation of the output data is the following:
rent is a slot of the Orders class containing the number of rent resources for a given order. Only the required type of resource is rent for an order.
buy is represented as a list of triplets (t, rt, n) where t is an integer representing a time point, rt is a resource type instance and n is the number of resources of type rt bought at time t. Bought resources are also represented as instances of the Resources class.
maint a maintenance is represented as a special order (instance of the Orders class)
alloc is a slot of the Orders class containing the set of resource instances allocated to the order.
In addition, a valued interval tree is built for representing the requirements to satisfy. The intervals are obtained by considering the beginning and end times of the orders. The value associated to an interval is the number of resources required during this time that can not be satisfied from existing stock. The algorithm will cover these intervals using external rentals in such a way that the cost is minimised.
Algebraic model for the problem without maintenance
In the interests of clarity, we introduce Possible(o) the set of resource types which can be allocated to the order o and Orders(r) the set of orders which can be allocated on an item of resource type r. Both sets can be deduced from the substituability relation. Note that this formulation relies on an obvious dominance property: The only interesting dates at which items can be bought correspond to the start times of orders.
Nonnegative integer variables
For each order o and for each resource type r in Possible(o), let ar,o be the number of items of type r allocated to the order o.
For each order o and for each resource type r in Possible(o), let br,o be the number of items of type r bought at time st(o) (to simplify the presentation, we assume that start times are distinct).
Constraints
For any resource type r, purchases are limited:
So ( Orders(r) br,o ( Maxbuy(r)
For any order o, no more than rq(o) items can be allocated:
Sr ( Possible(o) ar,o ( rq(o)
For any resource type r, and for any starting time t of an order in Orders(r), a capacity constraint applies. Let E be the set of orders in Orders(r) which execute at time t and let B be the set of orders in Orders(r) which start before t.
So ( E ar,o ( Stock(r)+ So ( B br,o
The sum over orders in B corresponds to the number of items bought before or at time t.
Decision criteria
The allocation cost: So Sr ( Possible(o) ar,o * (Cafix(r) + Catd(r) * (et(o) st(o)))
The renting cost: So Sr ( Possible(o) (rq(o) ar,o) * Crent(r) * (et(o) st(o))
The purchase cost: So Sr ( Possible(o) br,o * (Cstock(r) * (end st(o)) + Cbuy(r))
The objective is to minimise the sum of the three criteria.
This MIP problem is a straight extension of ICPARC's model (PSD1).
Algebraic model for the problem with maintenance
Let us now describe how this MIP can be extended to take into account some maintenance constraints.
Maintenance Capacity Constraints
Consider a time interval [t1 t2]. The basic idea consists of computing a pseudoload of the maintenance shop in the interval [t1 t2]. If the pseudo load exceeds the amount of work that can be done in the interval by the maintenance shop then, we can limit the overall number of allocated items at time t2. More precisely, for each order o and for each resource type r, we associate a pseudo maintenance which starts at time et(o) and whose duration pm(o, r) is either Mtime(r) if et(o) st(o) + dmin(o,r) > Utime(r) or 0 otherwise.
We define the pseudo load Lt1, t2 of the interval [t1 t2] as
Lt1, t2= So Sr ( Possible(o) ar,o * overlap(t1, t2, et(o), et(o) + pm(o, r))
Where overlap(a, b, c, d) is the number of time units during which two intervals [a b] and [cd] overlap. Lt1, t2 (t2 t1) * mcap is then a lower bound of the number of units of maintenance which cannot be done in [t1 t2]. Which means that (Lt1, t2 (t2 t1) * mcap) / maxMtime is a lower bound of the number of items which are not available at time t2, where maxMtime is the maximal value among {Mtime(r)}.
Let At2 be the sum over all orders o that execute at t2 and over all resource types r of ar,o. More precisely, At2 = So executing at t2 Sr ( Possible(o) ar,o
Let St2 be the total stock, over all resource types, at time t2.
St2=SrStock(r)+ Sr So  st(o) ( t2 br,o.
Thus the maintenance capacity linear constraint is
(Lt1, t2 (t2 t1) * mcap) / maxMtime + At2 ( St2
One could object that, we implicitly consider that when dmin(o,r) > 0 a maintenance executes immediately after the end of o. Of course, the maintenance could occur later and thus the value of overlap(t1, t2, et(o), et(o) + pm(o, r)) could be strictly less. But in such a case, the maintenance would not be finished at time t2 and thus the item would not be available at timet2.
The main drawback of the Maintenance Capacity Constraints is that one such constraint could be generated for any time interval. However, we think that it is sufficient to consider time intervals [t1 t2] such that t1 (respectively t2) either corresponds to a start time or an end time of an order or to the end time of pseudo maintenance. This means that there are O(n2) constraints to consider. This remains to be formally proven.
Problem Solution Deliverable 3
Estimated time:
The design work coupled with implementation has taken approximately 30 man days
The writing up of the PSD has taken approximately 5 man days
The third model we present has been derived by a partner using a column generation technique. The partner has considerable experience in Operations Research methods. The problem is modelled in C++ with the LPToolkit libraries and solved by a column generation technique.
Problem features and structure
The inventory management problem consists of two difficult loosely connected subproblems: a resource allocation problem and a scheduling problem. The scheduling problem deals with the work in the maintenance workshop and consists of determining at which time the workers maintain the items. The two problems do not use the same resources. The resource allocation problem deals with items while the scheduling problem considers workers in the workshop. The problems are connected by hard constraints stating that no item is used more than its maximum use time without maintenance.
Algorithm characterisation
The Column Generation technique is a pure hybrid algorithm with two cooperating subproblems using their respective model and algorithm (see Minoux 1983, chapter 10).
A master problem allows a selection of a good subset of columns (i.e. decision variables), and is solved by a MIP formulation of the problem or usually its relaxed continuous version. This problem has its own model, based often on an LP set covering model with additional constraints. It enables satisfaction of both basic covering constraints (i.e. each task must be covered by a column), and global constraints like the number of available resources (trucks, staff, ...). The generation of new interesting columns is then done dynamically taking into account the dual values of the current solution.
EMBED Unknown
A shortest path problem is defined on a value graph whose values are derived from the initial costs and the dual values given by the LP. A path in the graph with a negative length will be a column to introduce in the next LP.
The associated shortest path algorithm must sometimes take into account cumulative constraints in order to find feasible columns (i.e. feasible tours with a constraint on weight or maximal travel time, ..).
A major iteration consists in the resolution of a shortest path algorithm + the resolution of the modified LP. For sake of efficiency, restart techniques from the current basis are used in order to solve optimally each LP. This method is particularly powerful since it enables us to find the optimal solution when the decision variables are continuous and when no cumulative constraints are introduced.
In the inventory management problem, the core problem (without purchase) consists in assigning resources (equipment) to orders (different places where equipment is required for construction). The set covering problem allows the selection of columns which represent full feasible schedules of a single resource unit (an equipment item). The shortest path problem is built on a graph for which nodes (vertices) are the orders, and the potential days of maintenance starting activity. The links of the graph (edges) represent precedence constraints between the orders, and between maintenance activities and orders. A cumulative constraint in the shortest path algorithm allow to take into account the maintenance constraint.
The shortest paths problems have been solved using an adapted Dijkstra's algorithm. It has been adapted so that the cumulative maintenance constraint is satisfied for each path. Note that this additional constraint makes the problem NPhard. Consequently, the algorithm is not optimal in the sense that some path from source to an order can have a better reduced cost than the one proposed by the adapted algorithm. To have an optimal algorithm requires some additional research. The master problem is solved with CPLEX (or XPRESSMP).
The basic idea can be understood when looking at a Gantt chart of a solution. A row of the chart is the planning of one item o a resource (2 items for resource 1 and 2 items for resource 2).
Each feasible row will be a potential column to be selected in the master Linear Program.
EMBED Unknown
The generation of the columns will be performed using a set of graphs, one graph per resource, and for which nodes will be orders and maintenance tasks starting days, and links will be preceding constraints. A path will be feasible if the cumulative constraint of using an item will be less than the maximal time of use of an item.
Problem design
Algebraic model for the master problem
Indices
o : order
r : resource type
t : time
j : a column (which a path in the graph, or the planning of an item of resource type r)
Input data
subs(ri,rj) : item type ri subsumes the item type rj.
Stock(r) : the number of items of type r.
Crent(r) : external renting price for an item of type r.
Cafix(r) : fixed cost of the allocation of an item of type r to an order.
Catd(r) : time dependent cost of the allocation of an item of type r to an order.
st(o) : start time of order o.
et(o) : end time of order o.
rtype(o) : required item type to order o.
rq(o) : required number of items for order o.
Mcap (r) : required number of items for order o.
Utime(r) : maximal time of use of an item of type r without maintenance.
Mtime(r ) : maintenance time of an item of type r.
MCAP : the number of workers.
c(j) : the cost of a column : (sum of the costs of the orders plus sum of the cost of the maintenance tasks) :
c(j) =SYMBOL 83 \f "Symbol" \s 10Sj/o (Cafix(r) + Catd(r) ( (et(o) st(o))) +SYMBOL 83 \f "Symbol" \s 10Sj/r Cmaint(r)
Decision variables
x(j) : integer variable (0/1) indicating whether the column j is selected or not
rent(o) : number of units rented for order o
Constraints
We associate to each constraint its dual value which is necessary to compute the reduced cost of any new column
each required type or resources (rtype(o)) of an order is either allocated to an item of resource (a path ) or is rented
SYMBOL 83 \f "Symbol" \s 10Sj/o x(j) + rent(o) SYMBOL 179 \f "Symbol" \s 12 rq(o) dual value : l(o) for all o
the number of items is not greater than what is available in stock
SYMBOL 83 \f "Symbol" \s 10Sj/r x(j) SYMBOL 163 \f "Symbol" \s 12 Stock(r) dual value : m(r) for all r (type of resource)
for each time period, the number of items under maintenance is limited by the capacity of the maintenance workshop :
Let m(j,t) be a function which gives 1 if column j has a maintenance task which covers time period t ( a column j is defined for a type resource r)
SYMBOL 83 \f "Symbol" \s 10Sj/m(j,t) =1 Mcap (r) ( x(j) SYMBOL 163 \f "Symbol" \s 12 CapMax dual value : n(t) for all t
Objective function
The function is composed of external rentals and item allocations from existing stockand the cost of the maintenance.
F = SYMBOL 83 \f "Symbol" \s 10So Crent(rtype(o)) ( rent(o)+ SYMBOL 83 \f "Symbol" \s 10Sj c(j) ( x(j)
Associated graph
As explained before, we build one graph per resource type. When substitution is possible, a same order is present into more than one graph. If no substitution is possible, then clearly, the problem is completely decomposable per resource (we could solve each subproblem independently).
EMBED Unknown
Following the theory, the valuation of a path must represent the reduced cost of the corresponding column. Therefore, we have to give to each link (edge) a valuation such that the valuation of a path from a node to any order will represent the reduced cost of the corresponding column.
The reduced cost of a column (a path) is given by :
D(j) = C(j) SYMBOL 83 \f "Symbol" \s 10Sj/o l(o) + n(r ) + SYMBOL 83 \f "Symbol" \s 10St' /m(j,t) Mcap (r) m(t')
t'/m(j,t) =1 means that maintenance starts at t and has a duration of Utime (t), therefore we sum t' from t to t+Utime(t), ach time the column (path) j goes through a maintenance node which starts at t.
With purchase
The problem with purchase represents an extension of the core problem by considering purchase as well as the maintenance of items. The Column generation model can be in principle extended to this type of situation, but it would require a dynamic introduction of new constraints. Although the technology is available to implement such a model, its implementation would have been too complex to be done within the manpower allocated.
Concluding remarks
The three design and implementation activities were allocated different manpower and driven by different motivations.
The first one focused on getting good solutions by intuitively identifying the problem features and decomposing the problem into a resource allocation part (linear constraints) and a scheduling part. It benefited from a modelling platform (ECLiPSe) that allowed for uniform modelling and support for hybrid solvers. The strength of linear programming for the resource allocation part was shown. In three weeks one person got a good grasp of the problem, even though it did not consider the full problem.
The second design and implementation activity, further investigated the first results and studied the problem features deeper in terms of problem complexity and decomposition. It showed the reasons for the linear programming efficiency on the resource allocation subproblem (unimodular matrix) and extended the set of constraints tractable by the linear solver. It further improved the results by powerful heuristic and global scheduling constraints. The expertise of the team in scheduling problems allowed an improvement in the quality of results.
The third design concentrated on experimenting with a new approach based on a column generation technique. It proposed a new model and showed new optimality results for the problem. Even though the computation times were longer, in some cases it reached better solutions. This approach has benefited from an expertise in OR techniques and implementation support allowing for easy modelling of column generation models (LPToolkit and LPColGen).
So clearly, the expertise and implementation support of the LSCO team drives the earliest design and implementation work. However, The team which initially did not have an LP solver, acquired one (XpressMP) as well as knowledge about its benefits. As a conclusion, even though multiple design and implementation of a single problem can be costly, it allows much more insight into the problem features and improves efficiency as well as solution quality.
Writing up of the Problem Solution Document allowed application development to be documented. It also allowed all LSCO teams to share their knowledge towards better results. Even within a single LSCO team, different people will have different backgrounds and the role of the PSD is useful not only to document solutions but also to share expertise.
Annex F: Glossary
TOC \o "14" 11. ANNEX F: GLOSSARY A. GOTOBUTTON _Toc449250152 PAGEREF _Toc449250152 40
11.1 Definitions A. GOTOBUTTON _Toc449250153 PAGEREF _Toc449250153 41
11.2 Translations A. GOTOBUTTON _Toc449250154 PAGEREF _Toc449250154 49
Definitions
Acceptance Criteria
The criteria a software product must meet to successfully complete a test phase or meet delivery requirements.
[ANSI/IEEE 729]
Algebraic Model
Mathematical or 'readytocode' representation of a problem built based on the Problem Definition Deliverable during the design activity.
Algorithm Characterisation
Algorithm Design
(1) Action of selecting and describing the algorithm used to solve a problem.
(2) The result of the algorithm characterisation process.
BottomUp
Pertaining to a method or procedure that starts at the lowest level of abstraction and proceeds towards the highest level.
[ISO/IEC 238220]
Business Case
The justification for an activity expressed in terms of its business outcomes ( as distinct from, for example, as part of a scientific development )
Business Objective
The aim of an activity expressed in business terms
Combinatorial Optimisation
Selection of the best solution in a situation where there are potentially an extremely large number of potential solutions
Conceptual Model
CM (abbreviation)
A formalised representation of the definition of a problem or a subproblem that is part of the Problem Definition Deliverable. It lists input, constraints, criteria and output of the problem to be solved.
Constraint
The constraint may be a:
hard constraint: constraint that must be satisfied for a solution to be feasible.
soft constraint: relations whose satisfaction is aimed at while their violation does not invalidate a solution (see criterion).
Criterion (pl. Criteria)
A standard by which something can be decided, so used especially to describe a requirement which contributes to the objective of a problem.
Customer Organisation
Customer (abbreviation)
Problem Owner (synonym)
Organisation in charge of the project that decides to contract out some services to suppliers.
[adapted from EuroMethod]
Debugging
The process of locating, analysing, and correcting suspected faults.
[ANSI/IEEE 729]
Decision Support System
DSS (abbreviation)
A system ( usually a computer application ) whose purpose is to assist a user in making a decision
Decision Variable
A variable whose value is determined by the application and whose value forms part of the solution to the problem
Decomposition
A method of designing a solution to a problem by breaking the initial problem into subproblems. The decomposition may be organisational, i.e. due to the problem's structure or technical, i.e. artificially made in order to solve the problem.
Design
(1) The process of defining the software architecture, components, modules, interfaces, processing logic, data structures and data definitions for a software system to satisfy specified requirements.
(2) The result of the design process.
[adapted from ANSI/IEEE 729]
Design Model
DM (abbreviation)
A formalised representation of a problem or a subproblem that is expressed in a way required for a chosen solution method.
Development (abbreviation)
System Development
A process that usually includes requirement analysis, system design, implementation, documentation and quality assurance.
[ISO/IEC 238220]
Domain Expert
An individual who knows in detail the current practice of the process to be optimised as well as the customer requirements for the new project. He may or may not be part of the customer organisation.
Feasibility Study
A study to identify and analyse a problem and its potential solutions in order to determine their viability, costs, and benefits.
[ISO/IEC 238220]
Global Search
Global search is a divide and conquer optimisation technique, which searches for solution with the whole solution space. In order to find solution, the problem is recursively divided into subproblems which are examined one after the other. This branching process stops when the subproblem is precise enough to be solved to optimality by some algorithm (which may be a constraint propagation process or a relaxation, linear or not). Global search is the general scheme of exact optimisation techniques such as constraint logic programming (CLP) or mixed integer programming (MIP).
Hill Climbing, see Local Search
Hybrid Algorithm
Algorithm using two or more resolution techniques from different domains (e.g. operational research, constraint propagation, stochastic methods, ...) working in cooperation.
Implementation (abbreviation)
System Implementation
The system development phase at the end of which the hardware and software and procedures of the system considered become operational.
[ISO/IEC 238220]
Inference
Constraint Propagation (synonym)
A constraint programming system features variables and constraints. A set of possible values (a domain) is associated to each variables and constraints are used to remove values from the domains. Such value removals are based on constraint reasoning: the system infers that a variable will never take a given value in a solution and hence removes it from the domain: this deduction mechanism is the essence of constraint propagation.
Large Scale Combinatorial Optimisation
LSCO (abbreviation)
Combinatorial optimisation problem with a large number of constraints, variables or type of constraints or variables that can not therefore be satisfactorily solved using textbooktechniques. More generally, all complex combinatorial optimisation problem.
LSCO Provider
LSCO Technology Provider (synonym)
Supplier specialised in LSCO techniques that is in charge of the resolution of the LSCO problem. The team should be composed by one or several of the following: a analyst in charge of the capture of the requirements, a designer in charge of the solution design, a developer in charge with the development of the LSCO solution, and an expert, i.e. a senior engineer, for the overall technical management of the project. Note that a team member may be specialised into several activities.
Lifecycle (abbreviation)
System Lifecycle
The course of developmental changes through which a system passes from its conception to the termination of its uses.
[ISO/IEC 238220]
In the Chic2 Methodology, the lifecycle is decomposed into seven stages. Each stage is define by its objectives, input, output and process that link generic activities.
Local Search
Local search is an optimisation technique which starts with a solution an iteratively changes it to a similar one. Local search algorithms can be described by two components: a neighbourhood describing how to transform a solution into a set of similar ones and a control strategy, describing which move should be selected. The simplest strategy consists in looking for iterative improvements on the solution, which yields a hillclimbing process. However, more sophisticated strategies supporting moves which do not improve the objective function are available and yield excellent results (such as tabu search and simulated annealing).
Mapping
Process of insuring the consistency between the algorithm characterisation and the algebraic model.
Methodology (abbreviation)
Development Methodology
A systematic approach to the creation of software that defines phases, specifies the activities, products, verification procedures and completion criteria for each phase.
[ANSI/IEEE 729]
Objective
Objective Function
The measure of a subset of the performances of the system.
PDD
Problem Definition Deliverable
Product of the Problem Definition activity that list the requirement of the system and serves as reference for the design and the validation activities.
It is organised into three parts: 1) Problem overview and decomposition, 2) Conceptual model(s), 3) Other requirements.
PSD
Problem Solution Deliverable
Product of the Solution Design activity that specifies the design of the solution and is used by the developer to build a software solution. It is organised into three parts: 1) Problem solution overview and technical decomposition, 2) Algorithm design(s) and corresponding algebraic model(s), 3) Data flows model.
Project Management (abbreviation)
ISProject Management
In the software lifecycle process, it contains the activities of initiation & scope definition, planning, execution & control, review & evaluation and closure.
[ISO/IEC 12207]
Project Planning
The activities concerned with the specification of the components, timing, resources, and procedures of a project.
[ISOIEC 238220]
Problem Definition
The activities concerned with the analysis of user's requirements in order to build and validate a conceptual model of the problem.
Problem Solving
The tasks concerned with the design and programming of a solution to a problem.
Prototype
Operational trial model suitable for evaluating an information system specification or for better understanding or determination of requirements.
[Euromethod adapted from ISO/IEC 238220]
A preliminary type, form, or instance of a system that serves as a model for later stages or for the final, complete version of the system.
[ANSI/IEEE 729]
Prototyping
A hardware and software development technique in which a preliminary version of all or part of all the hardware or software is developed to permit user feedback, determine feasibility, or investigate timing or other issues in support of the process development process.
[ANSI/IEEE 729]
Requirement
An essential condition that a system has to satisfy.
[ISO/IEC 238220]
A condition or capability needed by an actor (user or system) to solve a problem, achieve an objective or satisfy a contract, standard, specification, or other formally imposed documents.
A documented representation of an above condition or capability.
[ANSI/IEEE 729]
Robustness
The property of being able to cope with small or moderate changes without significant problems
Risk
Possibility of exposure to the adverse consequences of future events.
[Euromethod]
Risk Management
Systematic approach to reduce the probability of the risk and/or limit the damage caused by the risk using appropriate counter or preventive actions..
It consists of the activities: risk analysis, risk management planning, and risk monitoring.
[EuroMethod]
Scope
the area covered by an activity
Search Space
the potential solutions which are evaluated by an algorithm in seeking a solution
Semantic
relating to the meaning of, for example, variables or expressions, as distinct from the way in which they are expressed.
SemiInnovative Problem
Nonbasic problem for which experts are confident that a resolution technique can be derived from existing work.
Specification
Definitive description of a system for the purpose of developing or validating of a system.
[ISO/IEC 238220]
A document that prescribes, in a complete, precise, verifiable manner, the requirements, design, behaviour, or other characteristics of a system or a system component.
[ANSI/IEEE 729]
Structure
( of a problem ) the arrangement and interrelationships of the parts of a problem
Supplier Organisation
Supplier (abbreviation)
Contractor (synonym)
An organisation that enters into a contract with the customer for the supply of a system, product or service under the terms of the contract.
[ISO/IEC 12207]
In the Chic2 Methodology, the LSCO Team.
Testing
The process of exercising or evaluating a system or system component by manual or automated means to verify that it satisfies specified requirements or to identify differences between expected and actual results.
[ANSI/IEEE 729]
TopDown
Pertaining to a method or procedure that starts at the highest level of abstraction and proceeds toward the lowest level.
[ISO/IEC 238220]
User
EndUser
An individual or organisation that uses the operational system to perform a specific function.
[ISO/IEC 12207]
Validation
The process of evaluating software at the end of the software development process to ensure compliance with software requirements.
[ANSI/IEEE 729]
Translations
EnglishFranaisGreekacceptance criteria critre d'acceptationKRITHRIO APODOCHSalgebraic modelmodle algbriqueALGEBRIKO MONTELOalgorithm characterisation/ designcaractrisation / conception des algorithmesCARAKTHRISMOS / SCEDIASH ALGORIQMWNbusiness caseplan commercialEPICEIRHSIAKO PLANO business objectiveobjectif commercialEPICEIRHSIAKOS STOCOS combinatorial optimisationoptimisation combinatoireSUNDUASTIKH BELTISTOPOIISHconceptual modelmodle conceptuelIDEATO MONTELOhard constraintcontrainte dureISCUROS PERIORISMOSsoft constraintcontrainte flexibleASQENHS PERIORISMOScriterioncritreKRITHRIOcustomerclientPELATHSdebuggingdebogageEKSFALMATWSHdecision support systemsystme d'aide la dcisionSUSTHMA UPOSTHRIXHS APOFASEWNdecision variablevariable de dcisionMETABLHTH APOFASHSdecompositiondcompositionAPOSUNQESHdesignconceptionSCEDIASHdesign modelmodle de conceptionMONTELO SCEDIASHSdevelopmentdveloppementANAPTUXHdomain expertexpert domaineEIDIKOS PEDIOU (EMPEIROGNWMONAS)feasibility studytude de faisabilitMELETH EFIKTOTHTAShybrid algorithmalgorithme hybrideUBRIDIKOS ALGORIQMOSimplementationralisationULOPOIHSHlarge scale combinatorial optimisation systemsystme d'optimisation complexeSUSTHMA SUNDUASTIKHS BELTISTOPOIHSHS MEGALHS KLIMAKAS (SBMK)LSCO teamquipe doptimisationOMADA SBMKlife cyclecycle de vieKUKLOS ZWHSmappingmise en relationANTISTOICISHmethodologymthodologieMEQODOLOGIAobjective functionfonction objectifANTIKEIMENIKH SUNARTHSHProblem Definition Deliverabledocument de dfinition du problmePARADOTEO PERIGRAFHS PROBLHMATOSProblem Solution Deliverabledocument de rsolution du problme PARADOTEO EPILUSHS PROBLHMATOSproject managementgestion de projetDIACEIRISH ERGOUproject planningplanification de projetSCEDIASMOS ERGOUproblem definitiondfinition du problmeKAQORISMOS PROBLHMATOSproblem solvingrsolution du problmeEPILUSH PROBLHMATOSprototypeprototypePRWTOTUPOprototypingprototypagePRWTOTUPOPOIHSHrequirementbesoinAPAITHSHrobustnessrobustesseSTIBAROTHTA / SQENAROTHTAriskrisqueKINDUNOS (RISKO)risk managementgestion des risquesDIACEIRISH KINDUNOUscopeenveloppe / primtreEKTASHsearch spaceespace de rechercheCWROS ANAZHTHSHSsemanticsmantiqueENNOIOLOGIKO PERIECOMENOsemiinnovative problemproblme semiinnovatif HMIKAINOTOMIKO PROBLHMAspecificationspcificationPRODIAGRAFHstructurestructureDOMHsupplierfournisseurPROMHQEUTHS / TROFODOTHStestingtestDOKIMHuserutilisateurCRHSTHSvalidationvalidationEPIBEBAIWSH / KURWSH
Annexes A. PAGE 25
.A 6: w .1&@&MathTypeTimes New Roman
2
@Min Uk` 2
c2
such that`kk 2
@a 2
@P b 2
@x 2
, `
2
, N``Times New Roman! 2
i,2
N (((
2
@Gij,,
2
@
j ,( 2
i, Times New Roman 2
i>PSymbol 2
< 2
@5" 2
@ 2
PSymbol 2
6 2
Times New Roman! 2
bx
2
@ x` 2
@= 2
@ ``Times New Roman 2
"i,
2
@i ,(Times New Roman! 2
@Gjk Times New Roman 2
ui>
&
"Systemnngf:(4@ .1$&$&MathTypePSymbol 2
`5" 2
`Z 2
`" 2
`# 2
`3 2
`d< 2
`z 2
`= 2
`/Times New Roman 2
`Go 2
`O 2
`(r 2
``R2
` allockk 2
``
r 2
`o 2
`r2
`rtypek 2
`o 2
``r2
`rtypek 2
`B#oTimes New Romanol 2
`,` 2
`V ,` 2
`( 2
`,` 2
`P) 2
`( 2
`b) 2
`"( 2
`$)MT Extra 2
`bp
&
"System >
@d :4@ .1@&&MathTypePSymbol 2
`5" 2
`Z 2
`" 2
`# 2
` 2
`Kz 2
`=Times New Roman 2
`Go 2
`O 2
`(r 2
``R2
` rtypek 2
`t
o 2
`Pr
2
`rentk 2
`0r 2
`ZoTimes New Romanol 2
`,` 2
`V ,` 2
`( 2
`:) 2
`( 2
`,` 2
` ) 2
`:0
&
"Systemppp2
$io: 3 .1``& &MathType`BB`xxSymbol 2
5" 2
Z 2
= 2
+ Symbol 2
Y
Symbol 2
Times New RomanSy 2
Go 2
O
2
rq 2
o
2
4rentk 2
Gr 2
qo2
\allockk 2
r 2
o Times New RomanP 2
rW 2
RTimes New RomanSy 2
,` 2
( 2
) 2
( 2
( 2
,` 2
7) 2
`( 2
,` 2
) 2
)
&
"Systema R:$4@ .1!&@!&MathTypePSymbol 2
`5" 2
`B 2
`" 2
` 2
`y
2
` 2
`2 2
`z 2
`=Times New Roman 2
`Gr 2
`R 2
`u 2
`<r 2
`f u2
`allockk 2
`,r 2
`Vo 2
`u2
`Wallockk 2
`r 2
`o 2
`o 2
`4 oTimes New Romanol 2
`u,` 2
`,` 2
`( 2
`,` 2
`) 2
`[( 2
`,` 2
`' 2
`9) 2
` '
&
"System2
`( 2
,` 2
()*+8DL a:98fp K .1`3&2&MathType "P(P(Pp(pP(Times New Roman 2
4C2
Crentk 2
r
2
:rentk 2
Mr 2
o 2
+d 2
o2
allockk 2
r 2
Ro2
!Cafixkk 2
a%r 2
(d 2
*o
2
z,Catdk 2
0r Times New Roman8 2
=op 2
6O 2
vrW 2
oRTimes New Roman 2
*1Symbol 2
.= 2
:+ 2
&+ Symbol 2
2
Symbol 2
> 2
lTimes New Roman 2
( 2
( 2
T) 2
* 2
( 2
,` 2
E) 2
;* 2
( 2
e) 2
( 2
,` 2
) 2
* 2
( 2
$( 2
&) 2
(( 2
z)( 2
*) 2
+* 2
/(
2
0))))
&
"SystemnFe :%hDHR .1@"&"Z&MathTypeTimes New Romany 2
4C
2
KCbuy 2
r2
Cstockk 2
xr2
xEnd 2
w tk Times New Roman 2
up2
buyppc 2
v
rW 2
+t> 2
at>2
Startp>pW>2
Endpp 2
rW 2
RTimes New Romany 2
B2Symbol 2
b= 2
+ 2
V Symbol 2
= 2
2
Symbol 2
2
* 2
Times New Romany 2
( 2
( 2
) 2
( 2
&) 2
* 2
(
2
!)) Times New Roman 2
(J 2
,8 2
)J 2
9[J 2
o,8 2
M
]J
&
"Systemication de tailleModification d
ss:0HR P .1&@:&MathType`vv`22Times New Romanc 2
4C 2
r 2
u Times New RomanD 2
Iup2
YStockp>pcc 2
rW2
~ Endpp 2
rW 2
RTimes New Romanc 2
B3Symbol 2
J= Symbol 2
2
Symbol 2
2
Times New Romanc2
H Cmaint(r)+kk2
maint+kk 2
r* 2
( 2
R,` 2
) Times New RomanD 2
a(J 2
0 ,8 2
)J
&
"Systemaint(r)*m( an:g .1@&`&MathType Times New RomanD 2
@LF 2
@C 2
@C 2
@< CSymbol 2
@= 2
@+ 2
@+Times New RomanD 2
@1 2
@ 2 2
@J
3
&
"Systemn3 T :2@_e$** G
;&WordMicrosoft Word
*System
@Times New Roman*wgw`
 &4
+;,;@ Helvetica
!w*wgw
J.%2
J*
Column GenerationTG!GhG![AGA.A'!GG.'$4%4 '&*
 .2434@Times New Roman*wgw
 8. 2
8*
Initialisation'8!2'2!28.*'\\ .72
*
1. Set covering Pb. Structure*.%%*)%))/*.)%)%.*'kXkX \.&2
\*
2. Build the graph*8)*)%)%*).*'~~ .52
*
3. initial cost on the graph*)%%* *))%)%*).*'
c& TU 1.)2
1*
Set covering problem8,!,22,,828,28,R.*'  .2
*
solving'2282.*'!v"v z.2
z*
1.*.*'Yv8Zv8 z8.)2
z8*
Introduce new colums)**)%%)%:%*)? .*'2818 8.72
8*
generated (i.e shortest path)%)%%%*% )*% *%).*'4.84.8 28. 2
28*
in the graph),))%)%*).*'!" .2
*
2.*.*'.8/8 8.52
8*
Get the new optimal solution<%)%)%:**?% *)*).*'D 8C 8 8.12
8*
(restart from the currenti% %*?)%%)%).*' @@ 8 A@ 8 D 8.2
D 8*
basis)*% .*' !  "  .2
*
3.*.*' 8 8 8.&2
8*
Get dual values of<%*)%)%)% *.*'V
8V
8 8.2
8*
constraints%*) %) .*'
&  1..2
1*
Shortest path algorithmn882,!,'!82!8222,!8R.*'h4 h5 
.2
*
1.*.*'h
K h
K 
K .82
K *
Update the cost of edges using<**%%)%%* *%*)% ) )).*'dK  dK  hK .2
hK *
dual values*)%)%)% .*'4 5  .2
*
2.*.*'
K 
K  K .;2
K *
Find optimal shortest path using.)***?% )*% *%)) )).*'zK zK  K .#2
K *
Dijkstra or Ford<) %*.**.*'4 v5 v z.2
z*
3.*.*'
vK 
vK  zK .:2
zK *
Optimal path are new columns tog<*?%*%)%%)%:%*)?) *.*'1
K 0
K  K .2
K *
introducee)**)%%.*'     1 *' 4  5  .2
*
4.*.*'
K 
K  K .;2
K *
Stop if all reduced cost of path.**%%*)%%*%* **%).*'C
K B
K  K .2
K *
are positive%%** )%.*'& % &&\z $~``~ &&\  $ ` & :@&V$
DD W
V&WordMicrosoft Word/ $
Times New Roman4 &# J
Times New Roman4 /2
$/ Gnration de colonnes :gugNgAAuu:ug:guAuuug[:A '
#]jTimes New Roman V2
)]2$/ exemple affectation de moyens (grues) des tchesCKCtK*C&C22CC*C**KK&KC&tKMCK:&2K2KC:2&C&KC:&*CCKC: ' "/ "D)2
) $/ ResourcesdC:KK2CC:' "
 "$'
M
IKm
2
Qm
$/ time**tC'̙ "X5(̙ "X̙ "X̙ "̙ " ̙ "93 "X3 " "ZN3 " "  jTimes New Romanb
2
$/ oK' "* Times New Roman%
2
&* $/ 22' " T  "
T   " T^  " 4 3 "
T'  "uu1
s5&2
;&$/ r=12UK's&2
&$/ r=22UK' " $  Root Entryf`iFWordDocumentqObjectPooltgtgSummaryInformation(
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~\E/]Root EntryfQgFWordDocumentObjectPooltgtgSummaryInformation(\/]DocumentSummaryInformation8_986200205_Ftg&g_986200209YF&g<.g_986200210SF<.g<.g
!#$%&'()*,/0146789:;<=>?@ABCDEFGHJMNORTUVWXYZ[\]^_`abcdefghiknopqtvwxyz{}~՜.+,0HP`hpxNTUAUIq0Oh+'0
4@L
Xdlt0CEICParc=AENormalICParc2FMicrosoft Word for Windows 95@F#@/;@b@b3w3_%
FImage Microsoft Word
MSWordDocWord.Picture.89qL@%V$l_986200211MF<.gd7g_986200212GFd7gd7g_986200213 AFd7g?g_986200214;F?g?g_986200215
5F?gHg_986200216/FHgHg_986200218
' FHgOg_986200219 FOg`g_986200221 F`g@igOle
PIC
LMETA
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[^_`abcdefghijklmnoprstuvwx{}~ " $  " $  " $  " $((  " $   " $   " $
  " $ 4 4 I I  " $ ^ ^ t t  " $   " $   " $   " $   " $ 2 2 G G 3 "
 
{Times New Roman2
$/ maintenancee;%C%;C;C;;' 
2
$/ oK' 9> 
2
=> $/ 22'
2
$/ oK'5f
2
9f$/ 12'(
#2
.
$/ rq(o2) = 2 items,C,CC,!K!C!%%;e4'Qh
+2
$/ substitution possible4CC4%%%C%%CC!CC44%C%;'
&
~':@%T$jv0 @&WordMicrosoft Word#System
@Times New Roman*wgw
 &
#F
#F
@Times New Roman*wgw

. 2
#Graphe associSo}}o?oaa}oEo.* '""b@Times New Roman*wgw
s
 ).
2
)#SX.*'&n%i&&G$wcGw&&]#%a&&EZ$fRYE&&I%M&&$&&33@%=5[">Yr#/<HVcq&&s33$s&&XDx33@%\HJNhUZ`f l/sS{vF^s(6ETcr&&v33$0/u0&&%&&m$mwmm&JJb@Times New Roman*wgw
 J.
2
J#oO.* '$D$D@Times New Roman*wgw
>
 I.
2
I#16.* 'XX _.
2
_#oO.* ')) .
2
#46.* 'JJ .
2
#oO.* 'e/e/ /.
2
/#26.* 'XX .
2
#oO.* 's`r` `.
2
`#36.* '&6AF3
%:EA
&&#~3
$67#}6
&&6A7l3
%:E2g
&&FM3
$],[?FL]
&&6A3
%:E
&&i3
$i
&&`3
%[
&&3
$
&&H3
%L
&&a3
$a
&&3
%
&&3
$
&hg .
2
#t5.* '3

3
3
@Times New Roman*wgw
h

?.2
?#O [.*E.2
E# t : c(t)(((,((,(F5,5.'p) q) r@Times New Roman*wgw
`
 / .2
/ #+Mcap(r)P~??G///.*'w)w)r@Times New Roman*wgw
 /* 'b@Symbol
!w*wgw

2
#S^'
pY
pY uY.2
uY#t$.*'f)g)r@Symbol
!w*wgw

2
)#mS7
.2
7
#(t)////. '&s3%w{w&&ne3$nuwnewn&&6334
.(2
#o o : c(o) O5((((((O((,(F5O5(5.*'
y
y y*b@Symbols
!w*wgws
'


2
#lO'.2
'#(o)/G/. '& k t33% o o&& ] 33$ o ] o &&ru
gexuDqCr .&2
#s o : c(o) =((((((O((,(F5O5(5.*'== *'====
2
=#l O.2
#(o)+ /G/Q$.
2
#noM
.2
#(r)/?/. '& t % o &&b $b i b b &< < {@Times New Roman*wgwA
 B .,2
B #Valuation of the links`;%C;%%CC!C!%C;!%%CC4.*'˟ٟ؟؟@ D :7 D :Nl D :_ D : D : D :i ͟͟@˟ݟԟ͟@
ϟӟ@џߟ@ݟڟ֟ݟ@ݟܟԟޟȟޟşݟ@ݟџҟܟݟ@ޟޟܟßß@Jџӟޟɟӟޟޟş՟֟ϟ֟ǟ؟՟@ #$67RSjkln./1QRmn.EFGIde56MNOQRS^st?VUVuDaaU
uDU]c0]c8Zh & ? @
.
D
h
i
9LM*Ahi
/
0
e
z
I\op,NOu U} E6jUVaaUaV`EPcdW5frt9S7'tUeCD_ """"""#'#$$%1%f%%&#&&&2&\'m''E(F(g((((((n)))I*p******9,N,z,VbcabVabVU_z,o.(/L/50E0R031I112234"4>4445n555606l66667+7S7l777788R8o99999:*:+:,:4:Q:w:x:::::::::::;;;;;<<==> >
>>1ARAOHfHKK MuDgeuD8:vKuDuDaa]c0]c8U][]cVUS M
MNOQQV*VZZZZ0Z1Z2ZtZuZZZZZZZZZZZZ[[[#[$[?[@[W[X[Z[\[^[[[B\C\D\;]<]d]]]]]^^<^b^d^^^^^^__"`N``a+aaakbbIcXccc5ddf/fNf}fffffgbUV]auDaU]c0U]c8U][]cVWg
ghpiwjjmm7n>nnnr
rr#rRrWrrsttBuSuuuuuuu%v1vvvyyzzzz{{o}~8~U"&6@)!"#12]^yzaU
uDUU]c0U]c8U[c]JJVUVuDaS.4]^_ovYjp7KR\c)/PkrLagKRz%}$w:;<IPovř̙"XY[jq:GMoqsU][]cUU]_szќҜ
34OPghjlӝԝ
$%@AXY[]xyȞɞ/0GHJLdeן؟.EFHJaauDaU]c0U]c8^ab}~àĠߠ'(CD[\^`ۡܡ=>YZqrtvբ֢آڢ568:UVqrӣԣ78OPRT{ϤФauDab#$?@WXZ\] !"^_`}~ųƳǳTU;<ҵӵxy@AluķŷƷǷҷӷ'()*J]JNJUJpVhVauDaY*56CEIQhijk{ܸ/06UfsŹιϹҹ789BX]hmstuz
9:GHuD8:vKuDpeuD8:vKuD?ABDEQ[\_(*+./U]UhUJhh JVh]VJ]VhUVhUVV=>?`a}~?@FWYZ\]^bciklmnoqr~
%&*+3$@JQRTprUVhUV JVhh]VhV]*+/12456@BCEOPSTUXYZd=> :;< %&'J]U
J]h]h JVhV]VhVUVhUVV'E F S T U V u2<lu(/FOpw#KQin+,GHIJYmqsUVJVV]
uDVuDuD8:vKbuDuD8:vKuDUVhVP:;<=RSTWc
.:;VWXYqrswxyzMRSnopquD8:vKJVV]c$Vc$
uDVc$U]UJ]uDUV]V]
uDVUVVMT U d e !,,,34OPghjl..... ..,...H/u//000;1N111U]cuDaaU
uDU]c0]c8U]c8UVUV]V]V
uDV]uDuDpL122<2334444m5w555]6o6667788999P:^:';9;;;#>2>5>U>?9??@AAB"C
EE5EEEhFuFHH_IINJlJJJKKbKb^bpbbbbb
c.cNcacscccccccdd)d>dHdRd]didudddddddddddee+e1eGeOe\epeeeeeeeee ff$f.f8f>fGfSfmfufzfffffffffffffffffu PacPcuDPc[]
]abcU]cW%o2JR^_& D
9A
z
\, } jPfp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#( +f9Uh9H(5CD[\ stUeDp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#&I'I (I)I &I'I (I)I x(Dg
_ +!""""""#'#x#$$%%1%f%y%%%&2&t&['\'p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#&I'I((I)I &I'I (I)I &I'I (I)I &\'m'''E(F(f(g((((((((m)n))))H*I*p**********8,9,N,z,,Pnop#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#&I'I (I)I &I'I (I)I &I'I (I)I 'o....(/L/c/4050E0R002131I111222223133344"4>4[44445m5n55p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#&p#p#&I'I (I)I &I'I (I)I )555
6606l666666677+7Q7R7S7l777777778888R8a8m9n9o9999999:):*:p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#&I'I (I)I ,*:,:Q:R::;8;9;~<<==>
>u?v?1AB_DGOH6J7J`JaJvKKNQVZZ0Z2Zp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#
p#p#p#p#p#p#p#p#p#B p#\p#p#p#p#
$
4h
;( !2Z3ZZ[][^[[[B\D\\\\;]<]d]}]]]^c^d^^^^_ _!_>_@_X______"`#`M`N`m```p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#
n# e#
*````
aa+aAaYaaaaaab#bLb[bhbkbbbbbc+c:cGcIcXcncpc~cccccccccd4d5dddp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#dd(edeeeeff/fMfNf}ffffffffgghh4ipiqiiiiiiijjIjvjwjjjjjjk6kp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#,6kXkYkm
oo$o1oFolooopEppppppprr8sp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#
4
4$
h4h.h8svsssssstt$t5t]ttttup#p#p#p#p#p#zp#p#p#Up#p#p#p#p#p#$
h4h.h
4
4
4$
h4h.hu
uavG~'Y
&jӄ>Svޅ)6{?@χp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#NO{()tǉ!"3.]^p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#lp#II ;( %^_oWXYj567K])NOPkJKLlp#II
lp#I
$LaLvwxyz{}uvw:;<Ipp#p#lp#II
lp#I
lp#II lp#III
přYZ[j89:Gmnopqsmp#p#p#p#p#p#p#p#p#( ^lp#III
lp#I
lp#II
^MKawۢ;U ]^_$cp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#"& ' ( ) 48) &
& ' ( ) 48) & ' ( ) ܨUVgשGHSTޭM67CD
p#p#p#p#p#p#p#p#p#p#p#p#p#Jp#p#p#p#p#p#p#p#Jp#p#p#p#Jp#p#p#p#p#p#p#p#p#p#Jp#$
4h
& ' ( ) $W}>յ{DxطIzع"p#p#p#p#p#p#p#p#p#p#p#p#p#p#:p#p#p#p#p#p#p#p#Jp#p#p#p#p#p#p#p#J
$
u 4hu $
4h
KIJef̽ͽ1p#p#p#p#"p#"p#p#p#p#"p#p#p#p#p#p#Jp#p#p#p#p#p#p#p#p#p#
4"
4
$
4h
12}ѿab#$CDU'2p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#Jp#p#p#p#p#p#p#p#Jp#p#p#& ' ( ) *2JU0"p$%p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#
"
4
4$
4h
/QbAgzv"#~+p#p#^p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#Tp#p#p#p#p#p#p#p#p
$
4h
$[\]^iXZ}Gp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#^p#p#p#
4$
4h
& ' ( ) 23Dkl{MHR3Rp#p#p#p#p#p#p#p#p#p#p#p#Jp#p#p#p#Jp#p#p#p#Jp#p#p#p#&p#p#&p#&p#p#p#p#p#p#p#p#$
4h
& ' ( ) #6TEi,~U%bM.Z[>?p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#
$
4h
# p%&ABD E W X :
tuM?GReo 3p#p#p#p#p#p#p#Jp#p#p#p#Jp#p#p#p#p#:p#p#p#p#p# p#p#p#p#p#p#p#p#p#p#p#Jp#p#p#p#p#p#p#p#p#h& ' ( ) )3l(FpLjZmkbc.:L p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#"p#p#p#Dp#p#p#p#,p#p#p#p#p#p#p#p#
$
4h
# T !!!`#s#t##%()+,,,, 
m.
...,.....G/H/c/u////0p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p
( )00000:1;1N111122*2<23331334444444444R5l5m5w555555\6]6o66667p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p77788889999999=:O:P:^:&;';9;;;;;">#>C>D>U>??#?9??????@AAAABBp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#p#pBB"C
EE$E5EEEgFhFuFHHH^I_IzII=JMJNJYJlJJJJJdKKKKKK:M;MbJbKb
G(Bp#
(Kb^bpbbbbbbb
c.cMcNcacscccccccccddd)d=d>dHdRd\d]diduddddddd
G(Bp#
(dddddddddee*e+e1eGeNeOe\epeeeeeeeeeee ff#f$f.f8f=f>fGfSflfmf
G(Bp#
(mfufzffffffffffffffffff
p#p#p#p#
& 9r p#G(Bp#I J I J I J
G(Bp#I I I I I I
G(Bp#
K@Normala t@t Heading 1Q
<34.8"
U[]
c`n@n Heading 2M
<4U]c l@l Heading 3K
<4.U]cj@j Heading 4K
<4.]cf@f Heading 5I
<34.]`@` Heading 6D
<34.UVd@d Heading 7K
<34.f@f Heading 8K
<34.Vf @f Heading 9H
x34.ac"A@"Default Paragraph Font"@"TOC 2n#
Z"@"TOC 3n#
V"B@" Body Text
<O"Code] O2 Figurex3)@APage Number( @R(Footerx39r @b Header9r (@(TOC 1xxn#
U[$@$TOC 4Xn#
c$@$TOC 5 n#
c$@$TOC 6n#
c$@$TOC 7n#
c$@$TOC 8xn#
c$@$TOC 9@n#
ccf3!!!!!! !
!!!
!! ! ! ! !!! !!! ! " # $ % & '!(!)!* + ,  . / 0!1!2 3RU!'/4+78D7GW^Xh_cmwwjPrܥضQ^a,
` )
+1P7?HPVQYRY>cclJ&
)
;JF !"Z#a$3%&'()*+,.*/0
1 2%o2JR^_&D9A
z
\,
}
jPf9Uh9H(5CD[\ stUeDg
_+ ' x !!""1"f"y"""#2#t#[$\$m$$$E%F%f%g%%%%%%%%m&n&&&&H'I'p''''''''''8)9)N)z))P*n*o****++++(,L,c,45ER2.3.I.../////0100011"1>1[11112m2n2222
3303l333333344+4Q4R4S4l444444445555R5a5m6n6o66666667)7*7,7Q7R7788898~99::;
;u<v<1>?_ADOE6G7G`GaGvHHKNSWW0W2W3WWX]X^XXXBYDYYYY;Z\@\X\\\\\\"]#]M]N]m]]]]]]
^^+^A^Y^^^^^^_#_L_[_h_k_____`+`:`G`I`X`n`p`~`````````a4a5aaaa(bdbbbbcc/cMcNc}ccccccccddee4fpfqfffffffggIgvgwggggggh6hXhYhj
ll$l1lFlllllmEmpmmmmmoo8pvppppppqq$q5q]qqqqr
rasG~'Y
&jӁ>Svނ)6{?@τNO{()tǆ!"3_Y7PLxyz}w<[:opqsm
^MKaw۟;U ]^_$cܥUVgצGHSTުM67CD
W}>ղ{DxشIzض"
KIJef̺ͺ12}ѼabͿο#$CDU'2JU0"p$%/QbAgzv"#~+[\]^iXZ}G23Dkl{MHR3R6TEi,~U%bM.Z[>? p%&ABDEWX: tuM?GReo 3l(FpLjZmkbc.:L T` s t "%&())))** *
**m**+
+++,+++++G,H,c,u,,,,:.;.N....//*/>>>???"@
BB$B5BBBgChCuCEEE^F_FzFF=GMGNGYGlGGGGGdHHHHHH:J;Ja]aaaaa+bObbbb$c>cmccccccccc$$$$$$$" $  " $  " $))  " $??TT  " $ii~~ 1Table+CompObjfObjInfoObjectPool@ig@igWordDocumentSummaryInformation(zDocumentSummaryInformation8qOle
PIC
LMETA1Table +CompObjfObjInfo"WordDocumentSummaryInformation(!#DocumentSummaryInformation8Ole
PIC
$&LMETAH1Table%)G"CompObjfObjInfo(+ObjectPoolOgOgWordDocument*,SummaryInformation(DocumentSummaryInformation8Ole
PIC
.1+LMETA"0CompObj02 qObjInfo3Equation Native DOle
KPIC
47ILMETA5CompObj683qObjInfo92Equation Native .Ole
lPIC
:=jLMETASCompObj<>QqObjInfo?PEquation Native LOle
PIC
@CLMETAuCompObjBDsqObjInfoErEquation Native m4Ole
PIC
FILMETACompObjHJqObjInfoKEquation Native Ole
PIC
LOLMETACompObjNPqObjInfoQEquation Native Ole
PIC
RULMETAhCompObjTVZObjInfoWEquation Native Ole
PIC
X[LMETA(CompObjZ\qObjInfo]Equation Native Ole
PIC
^aLMETACompObj`bfObjInfocEquation Native ՜.+,D՜.+,X
px
EuroDecisionD<jTitre 6>
_PID_GUIDAN{878FD642EDB111D19FBF444553540000}Oh+'0
8DP
\hpxssjacquetlagrezeacqacqNormal.dotr BROTTEMBtr2OTMicrosoft Word 8.0@F#@@43@zJ3YpbjbjWW==]DDDDDPD(pppppc%c%c%%%%%P%P!'Pq($`)T+X(c%A%"c%c%c%(%pp p%%%c%pp%(6c%%%%%%pd =3DD%%
Graphe associ
S
o
1
o
4
o
2
o
3
t
O t : c(t)
+Mcap(r)
S
t
m(t )
o o : c(o) 
l(o)
s o : c(o) 
l(o)+ n(r)
Valuation of the links
$*06<BHNTZ`d$&02<jlpºȪꞺꞺB*CJ mH5B*CJ&OJQJmH5B*CJ"OJQJmHB*CJmHB*CJ&OJQJmH5B*CJ"mHB*CJ"mHB*CJ&mH5B*CJmH5B*CJ&mHB*CJmHB*CJ&mH5B*CJ&mHB*CJ<mH
jUmH%"$(*.046:<@BFHLNRTXZ^`"`n"$:<jlnpN N!5"6#$%
[$@$NormalmH2A@2Police par dfaut"%(+.?ILOT[psy%'()*+,12389:="%(+.?ILOT[psy
ppn8=>@ ==(
@ NN
~
6?75
~
6?!$7W*
HB
#"?z(
B NC NEF?;Mk#$;8M;M@`NHB
#"?z(
B NC NEF?M)MM@`JHB
#"?6"(
B NC NEF?5M$M5M@`5!#T2
C33"?!
B NC NEF3333?'hBMM@` 1!T2
C33"?#&
B NC NEF3333?'hBMM@`R"##&HB
#"?q(!(
B NC NEF?M &M&M@`(!1'")~
6?]s
~
6?
~
6?0#%E'*,
~
6?$)'
~
6?}
~
6?>
~
6 ?'%
~
6
?"}&
NB
33"?xDn?
B NC NEF33?;(HEMM@`g>ANB
33"?x@
B NC NEF33?$=MM@`?HBNB
33"?xA
B NC NEF33? 5MM@`@yCNB
33"?)"X@
B NC NEF33?/M7q1M/M@`v!("+NB
!
33"?Ff0(B
"
B NC NEF33?TM5R1{"MTM@`2(/)1NB
#
33"?w1b(C
$
B NC NEF33?'MmI5E+M'M@`'/0F)2~
%
6?HCI
T
&
C3"?:"FMN~
'
6?#F4L
~
(
6
?2cG@L
~
)
6?=cG@L
~
*
6?D>F{BL
~
+
6?@ICM
~
,
6?AcGJL
NB

33"?$
J&J
.
B NC NEF33??M}&\M&?M@`j&lIG'JhL NN
/`,3I<T
0
C33"?NN~
1
6?YR;C
~
2
6?'6>@
~
3
6?K82
I@
NB
4
333"?f)
)
5
B NC NEF3333?=M}&\M&=M@`!
{#p/\L NM
6+
'N!/N
7
3"?NM~
8
6?2CLy"
B
S ?/
`M92j56@\\BYDIRO01\HP LaserJet 4000 Series PSNe01:winspoolHP LaserJet 4000 Series PS\\BYDIRO01\HP LaserJet 4000 SerW 4dXA4PRIV''''\\BYDIRO01\HP LaserJet 4000 SerW 4dXA4PRIV''''5`GTimes New Roman5Symbol3&Arial",f,f!0>jacquetlagrezeBROTTEMB@% A
,&WordMicrosoft Word$
Times New Roman4 &#E
Times New Romantr 2
$Graphe associSo}}o?oaa}oEo '"bTimes New Romanȑ
2
)$SX' "i " "$wcG "a "$fRYE "M "$ 33"
33 "$s 33"H]sH33 "$0/u " "$mwmJbTimes New Roman
2
J$oO '#DTimes New Roman4
2
I$16 'X
2
_$oO ')
2
$46 'J
2
$oO 'e/
2
/$26 'X
2
$oO 'r`
2
`$36 ' 3"E:@3 " $67#}  3"E:g13 " $],Z?FL  3"E:3 " $i  3"[3 " $  3"L3 " $a  3"3 " $ g
2
$t5 ' 3"  2
#2
$o t : c(t)O((((((,((,(F5,5'p) rTimes New Roman4 2
/ $+Mcap(r)P~??G///'v)rTimes New Roman
2
/$ 'bSymbolbSymbol
2
$S^'
pY2
uY$t$'f)rSymbol
rSymbol
2
)$mR
2
7
$(t)//// ' 3"ww{3 "$ouwoew& 33"4(2
$o o : c(o) O5((((((O((,(F5O5(5'
ybSymbol2
y$bSymbol'

2
$lN
2
'$(o)/G/ ' 33"o o 33 "$ o ] o
&
&vx "exvCq&2
$s o : c(o) =((((((O((,(F5O5(5'=2
$'==
2
=$lN
2
$(o)+ /G/Q$
2
$nL
2
$(r)/?/ ' " o  "$c i c 
&
< {Times New Roman8{Times New Roman4,2
B $Valuation of the links`;%C;%%CC!C!%C;!%%CC4'
&

FImage Microsoft Word
MSWordDocWord.Picture.89qL@&V$
՜.+,D՜.+,X
px
EuroDecisionD,
Titre 6>
_PID_GUIDAN{878FD641EDB111D19FBF444553540000}Oh+'0
<HT
`ltssjacquetlagrezeacqacqNormal.dotrJacquetLagrze3cqMicrosoft Word 8.0@@@"`@XagIbjbj]w(,,,,,$$$$$$$/%&>($)!+fb($$"$$$b($,,!,$$$$,,$$$$$$,$, !$$
Gnration de colonnes :
exemple affectation de moyens (grues) des tches
Resources
time
o
2
r=1
r=2
maintenance
o
2
o
1
rq(o2) = 2 items
substitution possible
Padgq~B*CJ mH5B*CJmH5B*CJ$mHB*CJ$mHB*CJ$mHB*CJ8mH
jUmHOPZ[`acdfgklpq}~N N!5"6#[$\%
[$@$NormalmH2A@2Police par dfautNY_bejo 456789:NY_bejo
8;:;@>!:: ( E)$
@ NN
~
6?
$>
~
6?7L F
HB
#? ?kN~
6?*R
HB
#? ?LDBL
B NC NEF?M l&Ml&M@`A"LZCM~
6?CxFML
Z
S̙̙? ?& Z
S̙̙? ?E Z
S̙̙? ?#N( Z
S̙̙? ?"&Z
S̙̙? ?P+"0&Z
S̙̙? ?" &Z
S33? ? Z
S33? ?#"'&Z
S? ?37Z
S33? ?3%7Z
S? ?P+307~
6?,2048
~
6?*.407
Z
S? ?^
4>OBZ
S? ?014>d6OBZ
S? ?4>&OBZ
S? ?3#7Z
S33? ?(4>OBHB
#? ?7.B:.~
6?
~
6?:q@
B NC NEF?HLHLH@`6+&T+w'
B NC NEF?HLHLH@`6+)(T+(
!
B NC NEF?HLHLH@`6+)T+N*
"
B NC NEF?HLHLH@`6+*T++
#
B NC NEF?HLHLH@`6+h,T+!
$
B NC NEF?HLHLH@`6+T+.
%
B NC NEF?HLHLH@`6+;/T+/
&
B NC NEF?HLHLH@`6+0T+_1
'
B NC NEF?HLHLH@`6+2T+2
(
B NC NEF?HLHLH@`6+y3T+24
)
B NC NEF?HLHLH@`0'0(
*
B NC NEF?HLHLH@`08)0)
+
B NC NEF?HLHLH@`0*0\+
,
B NC NEF?HLHLH@`0,0,

B NC NEF?HLHLH@`0v0/.
.
B NC NEF?HLHLH@`0.0/
/
B NC NEF?HLHLH@`0I001
0
B NC NEF?HLHLH@`010n2
1
B NC NEF?HLHLH@`0 303
2
B NC NEF?HLHLH@`040A5Z
3
S33? ?y6;~
4
6 ?{<^K
~
5
6
?j"0'
~
6
6?.#1'
~
7
6?$`38
~
8
6
?4$8
~
9
6?6>J^
~
:
6?6Nr$
B
S ?{.:g2j@HP DeskJet 660CLPT1:HPFDJC02HP DeskJet 660CHP DeskJet 660C4 d,,HP DeskJet 660CLPT1
,,HP DeskJet 660C4 d,,HP DeskJet 660CLPT1
,,/P@GTimes New Roman5Symbol3&Arial"9%%!0HjacquetlagrezeJacquetLagrze@& W
V&WordMicrosoft Word/ $
Times New Roman4 &# J
Times New Roman4 /2
$/ Gnration de colonnes :gugNgAAuu:ug:guAuuug[:A '
#]jTimes New Roman V2
)]2$/ exemple affectation de moyens (grues) des tchesCKCtK*C&C22CC*C**KK&KC&tKMCK:&2K2KC:2&C&KC:&*CCKC: ' "/ "D)2
) $/ ResourcesdC:KK2CC:' "
 "$'
M
IKm
2
Qm
$/ time**tC'̙ "X5(̙ "X̙ "X̙ "̙ " ̙ "93 "X3 " "ZN3 " "  jTimes New Romanb
2
$/ oK' "* Times New Roman%
2
&* $/ 22' " T  "
T   " T^  " 4 3 "
T'  "uu1
s5&2
;&$/ r=12UK's&2
&$/ r=22UK' " $  " $  " $  " $))  " $??TT  " $ii~~  " $  " $  " $  " $((  " $   " $   " $
  " $ 4 4 I I  " $ ^ ^ t t  " $   " $   " $   " $   " $ 2 2 G G 3 "
 
{Times New Roman2
$/ maintenancee;%C%;C;C;;' 
2
$/ oK' 9> 
2
=> $/ 22'
2
$/ oK'5f
2
9f$/ 12'(
#2
.
$/ rq(o2) = 2 items,C,CC,!K!C!%%;e4'Qh
+2
$/ substitution possible4CC4%%%C%%CC!CC44%C%;'
&
՜.+,D՜.+,X
px
EuroDecisionDBjTitre 6>
_PID_GUIDAN{44BDCB41EDA911D19FBF444553540000}Oh+'0
8DP
\hpxssjacquetlagrezeacqacqNormal.dotrArnaud LINZ2naMicrosoft Word 8.0@F#@@B7@7$
!"#%&'()*+,.0A123456789:;<=>?@BCDY<bjbjWW==9]XXXE*PzP$!^X""xXlzXX0E7
Column Generation
Initialisation
1. Set covering Pb. Structure
2. Build the graph
3. initial cost on the graph
Set covering problem
solving
1.
Introduce new colums
generated (i.e shortest path
in the graph),
2.
Get the new optimal solution
(restart from the current
basis)
3.
Get dual values of
constraints
Shortest path algorithm
1.
Update the cost of edges using
dual values
2.
Find optimal shortest path using
Dijkstra or Ford
3.
Optimal path are new columns to
introduce
4.
Stop if all reduced cost of path
are positive
'xMf:<B*mH5B*CJmH5B*CJ&OJQJmH5B*CJ&OJQJmH5B*CJOJQJmH
jUmH
&'EFYZwx&'EFYZwx&'+,?@LMefjk
+,9;C&'+,?@LMefjk
+,9:;<N N!.".#$%
FImage Microsoft Word
MSWordDocWord.Picture.89qL6@dg$(qJlJrJ
F=C1+C2+C3
[$@$NormalmH2A@2Police par dfaut%DXv%*>Kdi*8<
!"#$%&'%DXv%*>Kdi*8;
< <<< ;8*+@**8(
@ NN
~
6?&2:"
~
6?"
L NN
fNNN
3'?3~
6?:n#
~
6?
~
6?
$]
~
6?J+
N
3'?,%QN~
6?j%)
~
6?m) 
~
6 ?w1{4
~
6
?w14
~
6?4G8
~
6?,8;
~
6
?;{>
~
6?;>
~
6?>NB
~
6?1B
E
~
6?E{H
~
6?EeH
~
6?HTL
N
3'?,,%NN~
6?,j%F)
~
6?,v00
~
6?0vL0
~
6?00;=4
~
6?,"407
~
6?0"4L7
~
6?07?:
~
!
6?,:0D>
~
"
6?0:MD>
~
#
6?0)>:A
~
$
6?,A.D
~
%
6?,D0JH
~
&
6 ?0DSKJH
~
'
6!?0/H;K
!HB
(
#'??&q4$
)
B NC NE F'?::9:9:MN&:@`G1,3
*
B NC NE F'?}}=N=NM:}M:}M{&}@`G\>,e@B
S ?<`63j:=@HP LaserJet 4000 Series PSLPT1:winspoolHP LaserJet 4000 Series PSHP LaserJet 4000 Series PSW 4dXA4PRIV''''HP LaserJet 4000 Series PSW 4dXA4PRIV''''L<@GTimes New Roman5Symbol3&Arial;"Helvetica"1#1&!0jjacquetlagrezeArnaud LINZ6@d
;&WordMicrosoft Word
+
Times New Roman &t+;b"Helvetica%2
>+
Column Generationra,aa,{XaX=X5,aa'$4'& "  "24Times New Roman 2
8+
Initialisation'8!2'2!28'\72
+
1. Set covering Pb. Structure*.%%*)%))/*.)%)%'jX&2
\+
2. Build the graph*8)*)%)%*)'}52
+
3. initial cost on the graph*)%%* *))%)%*)' "
c&T)2
1+
Set covering problem8,!,22,,828,28,R'2
+
solving'2282'!v2
z+
1.*'Yv8)2
z8+
Introduce new colums)**)%%)%:%*)? '1872
8+
generated (i.e shortest path)%)%%%*% )*% *%)'3.8 2
28+
in the graph),))%)%*)'!2
+
2.*'.852
8+
Get the new optimal solution<%)%)%:**?% *)*)'C 812
8+
(restart from the current% %*?)%%)%)' @@ 82
D 8+
basis)*% ' ! 2
+
3.*' 8&2
8+
Get dual values of<%*)%)%)% *'V
82
8+
constraints%*) %) ' "
&.2
1+
Shortest path algorithm882,!,'!82!8222,!8R'h4 2
+
1.*'h
K 82
K +
Update the cost of edges using<**%%)%%* *%*)% ) ))'dK 2
hK +
dual values*)%)%)% '4 2
+
2.*'
K ;2
K +
Find optimal shortest path using.)***?% )*% *%)) ))'zK #2
K +
Dijkstra or Ford<) %*.**'4 v2
z+
3.*'
vK :2
zK +
Optimal path are new columns to<*?%*%)%%)%:%*)?) *'0
K 2
K +
introduce)**)%%'  2
1 +
' 4 2
+
4.*'
K ;2
K +
Stop if all reduced cost of path.**%%*)%%*%* **%)'B
K 2
K +
are positive%%** )%' "  "$~`` "$ `
&
&

F"Microsoft Editeur d'quations 2.0DS EquationEquation.29qg .1@&`&MathType Times New RomanD 2
@LF 2
@C 2
@C 2
@< CSymbol 2
@= 2
@+ 2
@+Times New RomanD 2
@1 2
@ 2 2
@J
3
&
"SystemnLg+67d 7
C3=Cmaint(r)*maint(r,u)abuStock(r,End)
rR
__
FMicrosoft Equation 2.0DS EquationEquation.2tion.29q63 P .1&@:&MathType`vv`22Times New Romanc 2
4C 2
r 2
u Times New RomanD 2
Iup2
YStockp>pcc 2
rW2
~ Endpp 2
rW 2
RTimes New Romanc 2
B3Symbol 2
J= Symbol 2
2
Symbol 2
2
Times New Romanc2
H Cmaint(r)+kk2
maint+kk 2
r* 2
( 2
R,` 2
) Times New RomanD 2
a(J 2
0 ,8 2
)J
&
"Systemaint(r)*mL0OS_6O74O7
C2=(Cbuy(r)+Cstock(r)*(Endt))ubuy(r,t)
t[Start,End]
rR
FMicrosoft Equation 2.0DS EquationEquation.2tion.29q%= .1@"&"Z&MathTypeTimes New Romany 2
4C
2
KCbuy 2
r2
Cstockk 2
xr2
xEnd 2
w tk Times New Roman 2
up2
buyppc 2
v
rW 2
+t> 2
at>2
Startp>pW>2
Endpp 2
rW 2
RTimes New Romany 2
B2Symbol 2
b= 2
+ 2
V Symbol 2
= 2
2
Symbol 2
2
* 2
Times New Romany 2
( 2
( 2
) 2
( 2
&) 2
* 2
(
2
!)) Times New Roman 2
(J 2
,8 2
)J 2
9[J 2
o,8 2
M
]J
&
"Systemication de tailleModification dL%hDJVSlJqJlJ
C1=(Crent(r)*rent(r,o)ab*d(o)+alloc(r,o)ab*(Cafix(r)+(d(o)*Catd(r))))oO
rR
J
F"Microsoft Editeur d'quations 2.0DS EquationEquation.29q98 K .1`3&2&MathType "P(P(Pp(pP(Times New Roman 2
4C2
Crentk 2
r
2
:rentk 2
Mr 2
o 2
+d 2
o2
allockk 2
r 2
Ro2
!Cafixkk 2
a%r 2
(d 2
*o
2
z,Catdk 2
0r Times New Roman8 2
=op 2
6O 2
vrW 2
oRTimes New Roman 2
*1Symbol 2
.= 2
:+ 2
&+ Symbol 2
2
Symbol 2
> 2
lTimes New Roman 2
( 2
( 2
T) 2
* 2
( 2
,` 2
E) 2
;* 2
( 2
e) 2
( 2
,` 2
) 2
* 2
( 2
$( 2
&) 2
(( 2
z)( 2
*) 2
+* 2
/(
2
0))))
&
"SystemnL98jyˠ78@8
"rR,"ur,ualloc(r,o)ualloc(r,o)o=oR
FMicrosoft Equation 2.0DS EquationEquation.2tion.29q$4> .1!&@!&MathTypePSymbol 2
`5" 2
`B 2
`" 2
` 2
`y
2
` 2
`2 2
`z 2
`=Times New Roman 2
`Gr 2
`R 2
`u 2
`<r 2
`f u2
`allockk 2
`,r 2
`Vo 2
`u2
`Wallockk 2
`r 2
`o 2
`o 2
`4 oTimes New Romanol 2
`u,` 2
`,` 2
`( 2
`,` 2
`) 2
`[( 2
`,` 2
`' 2
`9) 2
` '
&
"System2
`( 2
,` 2
L$4@ˠ78(8
"oO,rq(o)=(rent(r,o)+alloc(r,o)ab)rR
FMicrosoft Equation 2.0DS EquationEquation.2tion.29q: 3 .1``& &MathType`BB`xxSymbol 2
5" 2
Z 2
= 2
+ Symbol 2
Y
Symbol 2
Times New RomanSy 2
Go 2
O
2
rq 2
o
2
4rentk 2
Gr 2
qo2
\allockk 2
r 2
o Times New RomanP 2
rW 2
RTimes New RomanSy 2
,` 2
( 2
) 2
( 2
( 2
,` 2
7) 2
`( 2
,` 2
) 2
)
&
"SystemLˀ7848
"oO,"rR,rtype(o)rrent(r,o)=0)rprtyp
FMicrosoft Equation 2.0DS EquationEquation.2
4> .1@&&MathTypePSymbol 2
`5" 2
`Z 2
`" 2
`# 2
` 2
`Kz 2
`=Times New Roman 2
`Go 2
`O 2
`(r 2
``R2
` rtypek 2
`t
o 2
`Pr
2
`rentk 2
`0r 2
`ZoTimes New Romanol 2
`,` 2
`V ,` 2
`( 2
`:) 2
`( 2
`,` 2
` ) 2
`:0
&
"SystempppL
4@ˠ78d 8
"oO,"rR,alloc(r,o)r=rtype(o)rprtype(o)&"
FMicrosoft Equation 2.0DS EquationEquation.2tion.29q(4> .1$&$&MathTypePSymbol 2
`5" 2
`Z 2
`" 2
`# 2
`3 2
`d< 2
`z 2
`= 2
`/Times New Roman 2
`Go 2
`O 2
`(r 2
``R2
` allockk 2
``
r 2
`o 2
`r2
`rtypek 2
`o 2
``r2
`rtypek 2
`B#oTimes New Romanol 2
`,` 2
`V ,` 2
`( 2
`,` 2
`P) 2
`( 2
`b) 2
`"( 2
`$)MT Extra 2
`bp
&
"System >
@L(4@lJ8qJ mJ
Min ci
Times New Romanxi
such thati
"jaij
i
xi
= bj
xi
N
FMicrosoft Equation 2.0DS Eq
uationEquation.29q w .1&@&MathTypeTimes New Roman
2
@Min Uk` 2
c2
such that`kk 2
@a 2
@P b 2
@x 2
, `
2
, N``Times New Roman! 2
i,2
N (((
2
@Gij,,
2
@
j ,( 2
i, Times New Roman 2
i>PSymbol 2
< 2
@5" 2
@ 2
PSymbol 2
6 2
Times New Roman! 2
bx
2
@ x` 2
@= 2
@ ``Times New Roman 2
"i,
2
@i ,(Times New Roman! 2
@Gjk Times New Roman 2
ui>
&
"SystemnL $
!"#%&'()*+,.0A123456789:;<=>?@BCDGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnostuvwxy{}~$444$4444$$444DDTTTTTDTTTTTDTTTT$444DDTTTD$444DTTTTTTDz, Mgsa*HbG'1Xa
fD\'o5*:2Z`d6k8suzV^Lp123 07BNVw\W^#`Kbdmff !"#$%&'()*+,./0123456789:;<=#6Rjlm/0QmEGHd5MOPRw7777777888:;
;tWWWWWWWWXX#X?XWXZX[X"1]yљ 3OgjkӚ
$@X[\xț/GJKdלEHIa}Ýߝ'C[^_۞=Yqtu՟؟ٟ589UqӠ7ORS{ϡ#?WZ[
9GIǺɺ/}ESU+GI:<:VXyRnpd**3*O*g*j*k********++++c
2%@2%@2%@2%@2%@2%@2%@2%@2%@2%2%:2%2%2%
2%@2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%2%::::::::::9999999999:99
2%@2%@2%@!0WBYdxcaqM
_Toc422166587
_Toc422202074
_Toc422202207
_Toc422203785
_Toc422849352
_Toc422850489
_Toc422912791
_Toc440880209
_Toc441463356
_Toc449250108
_Toc440880210
_Toc441463357
_Toc449250109
_Toc440880211
_Toc441463358
_Toc449250110
_Toc440880212
_Toc441463359
_Toc449250111
_Toc440880213
_Toc441463360
_Toc449250112
_Toc440880214
_Toc441463361
_Toc449250113
_Toc440880215
_Toc441463362
_Toc449250114
_Toc440880216
_Toc441463363
_Toc449250115
_Toc440880217
_Toc441463364
_Toc449250116
_Toc440880218
_Toc441463365
_Toc449250117
_Toc415240629
_Toc415286500
_Toc415306927
_Toc420305308
_Toc420314223
_Toc422139077
_Toc422141446
_Toc422145613
_Toc422159895
_Toc422166578
_Toc422202065
_Toc422202196
_Toc422203776
_Toc422849353
_Toc422850490
_Toc422912792
_Toc440880219
_Toc441463366
_Toc449250118
_Toc414855113
_Toc414961662
_Toc421677962
_Toc421678048
_Toc421971682
_Toc422040610
_Toc422040739
_Toc422138197
_Toc422139075
_Toc422141444
_Toc422159893
_Toc422202197
_Toc440880220
_Toc441463367
_Toc449250119
_Toc421677963
_Toc421678049
_Toc421971683
_Toc422040611
_Toc422040740
_Toc422138198
_Toc422139076
_Toc422141445
_Toc422159894
_Toc422202198
_Toc440880221
_Toc441463368
_Toc449250120
_Toc414855114
_Toc414961663
_Toc415240632
_Toc415286503
_Toc415306930
_Toc420305311
_Toc420314226
_Toc422139080
_Toc422141449
_Toc422145616
_Toc422159898
_Toc422166586
_Toc422202073
_Toc422202206
_Toc422203784
_Toc422849354
_Toc422850491
_Toc422912793
_Toc440880222
_Toc441463369
_Toc449250121
_Toc440880223
_Toc441463370
_Toc449250122
_Toc440880224
_Toc441463371
_Toc449250123
_Toc440880225
_Toc441463372
_Toc449250124
_Toc422166580
_Toc422202067
_Toc422202200
_Toc422203778
_Toc422849355
_Toc422850492
_Toc422912794
_Toc440880226
_Toc441463373
_Toc449250125
_Toc440880227
_Toc441463374
_Toc449250126
_Toc440880228
_Toc441463375
_Toc449250127
_Toc440880229
_Toc441463376
_Toc449250128
_Toc449250129
_Toc449250130
_Toc449250131
_Toc440880230
_Toc441463377
_Toc449250132
_Toc449250133
_Toc449250134
_Toc449250135
_Toc449250136
_Toc440880231
_Toc441463378
_Toc449250137
_Toc440880232
_Toc441463379
_Toc449250138
_Toc440880233
_Toc441463380
_Toc449250139
_Toc449250140
_Toc449250141
_Toc449250142
_Toc379636295
_Toc379636296
_Toc379636297
_Toc379636298
_Toc379636299
_Toc440880234
_Toc441463381
_Toc449250143
_Toc449250144
_Toc449250145
_Toc449250146
_Toc440880235
_Toc441463382
_Toc449250147
_Toc449250148
_Toc420080676
_Toc449250149
_Toc420080679
_Toc449250150
_Toc420080681
_958826729
_Toc440880236
_Toc441463383
_Toc449250151
_Toc422139081
_Toc422141450
_Toc422145617
_Toc422159899
_Toc422166588
_Toc422202075
_Toc422202208
_Toc422203786
_Toc422849356
_Toc422850493
_Toc422912795
_Toc440880237
_Toc441463384
_Toc449250152
_Toc415306924
_Hlt440169076
_Toc415306925
_Toc422139083
_Toc422141452
_Toc422145619
_Toc422159901
_Toc422166590
_Toc422202077
_Toc422202210
_Toc422203788
_Toc422849358
_Toc422850495
_Toc422912797
_Toc440880238
_Toc441463385
_Toc449250153
_Toc415306926
_Toc422139084
_Toc422141453
_Toc422145620
_Toc422159902
_Toc422166591
_Toc422202078
_Toc422202211
_Toc422203789
_Toc422849359
_Toc422850496
_Toc422912798
_Toc440880239
_Toc441463386
_Toc449250154SDDD!!!F%F%F%+++000333,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7Q7Q7Q7Q7Q7Q7Q7Q7Q7Q7Q7Q7Q7Q7Q77G7G7G7G7G7G7G7G7G7G7G7G7G7G7GWWWWWWWWWWWWWWWWWWW2W2W^XcccwwwsssܥܥܥH7$$$Jpl&& ` ` ` )))))))))))))))
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+RYRYRYRYRYRYRYRYRYRYRYRYRYRYRYc
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~]]]ZZZ!!!d%d%d%+++000444P7P7P7P7P7P7P7P7P7P7P7P7P7P7P7P7P7P7P7080878787878787878787878787878^G^G^G^G^G^G^G^G^G^G^G^G^G_G_G'W'W'W'W'W'W'W'W'W'W'W'W'W/W/W/W/W/W/WXXX
d
d
dxxx RB̿̿̿BBBT!{111z
@@r r r )))))))))))****
++++++++++++++++^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Ychj&4GN19@MPQZ^efjkr}, 2 A H J M R [
*.2=IKT\c#*,39B
)

8
I
U
c
m
t
{
}
'09]hjsky
+19A/3tzCYeim""
""""$")"f"n""""###R#d#a$e$$$g%k%l%u%z%~%%%%%%%n&y&&&N'U'_'h'''''''''+,,,, ,5=EIUYg.s.%001 11111n2r2s2z23(33333+45444444566666677RRXXkZmZoZqZ%[+[[[[[[[1\;\H\I\`\g\i\m\o\s\u\y\{\\\\\\\\']0]3]:]]]]]]]]]]]]]^^5^6^>^@^V^X^[^\^p^q^}^^^^^^^^^^^^^^__ _"_3_9_:_=_A_B_Y_Z__________________````` `!`E`F````aaa
aa!a+aaaaaaaaaaaaabbAbKbbbbbbbbbbbbbbbbbbbcc3c=c@cJcccccccccfffffffffggggggggggggghh h*h+h3hFhVhfipi7k>kkklll"l%llNlUlYl`laliltl{llllllllllllmmmm'm(m1m5mKQRU lpuwx{X\dgkqyIKHMtMOGKNPLPdh
#%SU[_chwy=E/3$AFIKTX38lq
FKpr "$NT>@]`hluz{ DKPS&&''`2j299CCEERM\M[QeQmRwRSShYpYYYYYYYYYZZ+Z.Z/Z:ZZZZ[5[;[<[F[g[q[r[v[[[[[\\3\:\;\A\G\O\\\\\\]/]<]\]c]]]]]]]]]
^^O^V^W^e^f^n^^^^^_
_1_=_^_f_g_o_____` `$`,`a`h`l`r`````````aa a(aiataaaaaaab b
b
bbb1b:b=bFb\bbbfbobbbbbbbbb ccGcRccccc DaBigBoss+C:\Gkost\CHIC2\DELIVERA\Method\ANNEX_W6.docICParc4\\TRIUMPH\MEMBERS\Chic2_Methodology\ANNEX_aja 10.docICParc1\\TRIUMPH\MEMBERS\Chic2_Methodology\ANNEX_aja.doc@Epson Compatible 9 PinFILE:EPSON9Epson Compatible 9 PinEpson Compatible 9 Pin@f x@MSUDEpson Compatible 9 PindEpson Compatible 9 Pin@f x@MSUDEpson Compatible 9 PindFFFFTimes New RomanSymbol&Arial
MgRevueTimesTimes New Roman5Courier NewMT ExtraVColonna MTWingdings 2FBrush Script MT""Futura LtCn BTArial Narrow&Arial Black"hd5fd5f#5Fw3_%3q3!#0ICParcICParc
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTz^_`abcdefghijklmnoprstuvwx{}~ܥh efc:::::::\)zзM);Y
Xb#:+@зm::
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~mmm ::`iN4::::mmAnnex A: References
TOC \o "14"
6.1 References A. GOTOBUTTON _Toc449250109 PAGEREF _Toc449250109 2
6.2 Structured Bibliography A. GOTOBUTTON _Toc449250110 PAGEREF _Toc449250110 4
6.2.1 Introduction to combinatorial optimisation A. GOTOBUTTON _Toc449250111 PAGEREF _Toc449250111 4
6.2.2 Constraint programming A. GOTOBUTTON _Toc449250112 PAGEREF _Toc449250112 4
6.2.3 Operations research and graphs A. GOTOBUTTON _Toc449250113 PAGEREF _Toc449250113 6
6.2.4 Linear and Integer programming A. GOTOBUTTON _Toc449250114 PAGEREF _Toc449250114 6
6.2.5 Stochastic search A. GOTOBUTTON _Toc449250115 PAGEREF _Toc449250115 7
6.2.6 Problem classes and surveys A. GOTOBUTTON _Toc449250116 PAGEREF _Toc449250116 8
6.2.7 Methodology references A. GOTOBUTTON _Toc449250117 PAGEREF _Toc449250117 8
References
ANSI/IEEE 729 (1983), Standard Glossary of Software Engineering Technology, Std 729, 1983.
Baptiste P., Caseau, Y., Kkny, T. and Lepape C (1998), Creating and Evaluating hybrid Algorithms for Inventory Management Problems, Working Paper, Bouygues, to be presented to ECCO IX, Copenhagen.
Charnes, A., Cooper, W.W. (1961), Management Models and Industrial Applications of Linear Programming, vol. 1, Wiley.
Chatzoglou et al (1997), The importance of human factors in planning the requirements capture stage of a project, International Journal of Project Management, Vol. 15, No 1, pp3953, 1997
Dechter, R., Pearl, J. (1989), Tree Clustering for Constraint Networks, Artificial Intelligence 38, pp. 353366.
Demeulemeester E. (1992), Optimal Algorithms for Various Classes of Multiple ResourceConstrained project Scheduling Problems. PhD Thesis, Katholieke Universiteit Leuven.
ElSakkout H., Richards T. and Wallace M. (1998), Minimal perturbance in dynamic scheduling, to appear in ECAI98.
ElSakkout H. and Wallace M. (1998), A Strategy for Minimal Temporal Perturbation in Dynamic Scheduling, submitted to the Constraints journal.
Euromethod, Information systems: improving the customersupplier relationship, Version 0, Juin, 1994.
Haouari, M. (1991), Les problmes de tourne avec fentre de temps, modlisation et algorithmes de rsolution exacte et heuristique, Thse, Ecole Centrale Paris
Hillier, F.S and Lieberman G.J. (19671986), Introduction to Operations Research, HoldenDay, Oakland.
Hillier, F.S and Lieberman G.J. (1990), Introduction to Mathematical Programming, Mc GrawHill.
C. A. R. Hoare, C.B. Jones (1989), Essays in Computing Science, Prentice Hall International series in computer science.
ISO/IEC 12207 (1995), Information Technology Software lifecycle processes, 1st Edition, 1995.
ISO/IEC 238220 (1990), Information Technology Vocabulary. Part 20: System Development Terms, 1st Edition, 1990.
JacquetLagrze, (1998), Programmation Linaire, modlisation et mise en oeuvre informatique, Economica, Paris
Jourdan, J. (1992), Concurrence et coopration de modles multiples dans les langages de contraintes CLP et CC: vers une mthodologie de programmation par modlisation, PhD Thesis, Universit Denis Diderot.
Jourdan, J., Lissajoux, R. (1995), CLP and scheduling of arriving flights (in French), in: Proceeding AI95, 1995.
Kirakowski, J (1988), Human Computer Interaction: from Voltage to Knowledge, CratwellBratt Bromp
W}>ղ{DxشIzض"
KIJef̺ͺ12}ѼabͿο#$CDU'2JU0"p$%/QbAgzv"#~+[\]^iXZ}G23Dkl{MHR3R6TEi,~U%bM.Z[>? p%&ABDEWX: tuM?GReo 3l(FpLjZmkbc.:L T` s t "%&())))** *
**m**+
+++,+++++G,H,c,u,,,,:.;.N....//*/>>>???"@
BB$B5BBBgChCuCEEE^F_FzFF=GMGNGYGlGGGGGdHHHHHH:J;Ja]aaaaa+bObbbb$c>cmccccccccc$$$$$$$