Datalogisk Institut
Københavns Universitet

Optimeringsproblemer i Productionsplanlægning, blok 1, 2007-08

[Undervisningsplan] [Meddelelser] [Litteratur] [SIS] [skema]

Meddelelser

[25 september] The plan has been changed for the lecture at October 10.
[11 september] Exercise 3 on MIP heuristics added.
[15 august] Kursushjemmeside oprettet

Formål

The purpose of the course is to give an in-depth overview of modeling, reformulation and optimization techniques for solving production planning and supply chain planning problems.

Indhold

Production planning is a key issue in the industry, and several interesting optimization problems can be studied. We will study various planning models and discuss the corresponding solution methods. Due to the large data sets, long planning horizont, and complicated constraints, advanced algorithmic approaches are needed. The list of topics will include: Demand planning, production planning, capacity planning and production controle. Some of the lectures will be given by external speakers from leading developer of planning tools.

Målbeskrivelse

Ved kursets afslutning skal den studerende kunne: Kende forskellige produktionsstrategier, heriblandt MRP og Just-in-time management.
Kunne relaterer de enkelte faser af produktionsplanlægning og kunne modellere disse som optimeringsmodeller.
Have kendskab til den terminologi der anvendes i litteratur og erhvervsliv.
Kunne estimere produktionsbehov ud fra forecasting modeller, samt have kendskab til forecasting modellers begrænsninger.
Kende metoder til dekomponering af modeller.
Kende forskel mellem big-bucket og small-bucket modeller.
Kunne dekomponere produktionsproblemer og have kendskab til hvorledes de enkelte komponenter løses.
Have indsigt i heuristiske løsningsmetoder til produktionsplanlægning.

Undervisere

David Pisinger (kursusansvarlig) (DP), Mads Jepsen (MJ), Bjorn Petersen (BP), Simon Spoorendonk (SS), Thomas Jensen, MDCC (TJ) Steen Sloth Christensen, MDCC (SC)

Forelæsninger

mandag 12-14, N004, DIKU
onsdag 13-15, Lille Auditorium, DIKU

Undervisningsplan

Foreløbig plan for kurset. Forbehold for ændringer.

Dato	Lærer	Indhold/Emne	Litteratur	Plancher	Opgaver
27/8	DP/TJ	Introduction and Beergame	FP kap 1	intro, MIT beer game,beer game	beskriv bullwhip effekten i spillet, og overvej hvad man kan gøre for at undgå den (1 side tekst)
29/8	BP	Simple Production models and lot sizing	FP kap 2, Wagner algorithm	slides	se slides
3/9	MJ	MRP, MRP-II and Rough-Cut Planning	FP kap 3, artikel med RCCP	slides	exercises
5/9	BP	Banch and Cut for Lot Sizing	PP	slides	se slides cplex file
10/9	SS	MIP heuristics	Papers below and PP kap 3.6	slides	ex cls.lp
12/9	MJ	Branch and price	Chapter 26 handed out at lectures	slides	See slides lp format file for master problem master lp format file for pricing problem pricing
17/9	TJ	JIT +What Went Wrong	FP kap 4+5		diskuter forskelle mellem MRP og JIT og diskuter passende anvendelser af begge principper
19/9	SC/TJ	Basic Factory Dynamics and Push-Pull sytem	FP kap 7+10		FP chap 7 study-questions 1,2,3 FP chap 10 problems 1,2
24/9	MJ/DP	Branch and Price for CLST / multiple choice knapsack	CLST+knapsack litt	Clst Mckp	ex1 ex2+3
26/9	DP	Forecasting, capacity planning	Hyndman (2002), Asmundsson (2002)	slides slides	ex,ex
1/10	NO	Multi-site production planning	---
3/10	SS	An Adaptive Large Neighborhood Search for the Multi Resource Multi Level Lot Sizing Problem	Pisinger and Ropke (2007)	slides	ex
8/10	DP	Variability Basics	FP kap 8	ppt
10/10	SS/MJ	The Vehicle Routing Problem with Time Windows Presentation of the 2-week implementation assignment	Jepsen et al. (2006) Petersen et al. (2007)	slides

Litteratur

Factory Physics (FP)
Production Planning (PP) by Pochet and Wolsey
Linear-programming-based heuristic for project capacity planning (RCCP) pdf her
12/9 MIP heuristics (available from DIKU):
T. Achterberg and T. Berthold, "Improving the Feasibility Pump", Discrete Optimization, Volume 4, Issue 1, 1 March 2007, Pages 77-86 pdf
E. Danna, E. Rothberg and C. Le Pape, Mathematical Programming, Volume 102, Number 1 / January, 2005, "Exploring relaxation induced neighborhoods to improve MIP solutions" pdf
M. Fischetti and A. Lodi, "Local branching", Mathematical Programming, Volume 98, Numbers 1-3 / September, 2003, pdf
Rob J. Hyndman (2002): Forecasting based on state space models for exponential smoothing. pdf
Asmundsson, Rardin, Uzsoy (2002) Tractable Nonlinear Capacity Models for Production Planning Part I: Modelling and Formulations pdf
FP chapter 8 pdf
Ryan, Ehrgott ps

Exercises

The following exercises have been handed in for correction

Name	ex1	ex2	ex3	ex4	ex5	ex6	ex7	implement	passed
Mette Gamst	100	75	o
Rasmus Michael Torpe	100	95	58	100	100
Goran Tomic	90
Stefan Bangerth	50	38
Nicolai Esbensen	80	95	38	80	100
Anders Bøggild-Povlsen	75	95	38	80	100
Fabio Fernander
Jens Rasmussen
Mikkel B0ttcher Mertz
Morten Nikolaj Sidoroff Gryning
Simon Christiansen
Thomas Alexander Jacobsen
Wojciech Jamrozy

x = corrected, x procent credit
o = handed in (not yet corrected)