DM204: Skedulering, Skemalægning og Ruteplanlægning (10 ECTS)

STADS: 15005401

Niveau
PhD-kursus

Undervisningsperiode

Udbydes efter behov.

Ansvarlige undervisere
Email: marco@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Ubegrænset deltagerantal. 3. + 4. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Bachelorgraden skal være bestået. Stoffet fra DM507 Algoritmer og Datastrukturer, og DM508 Algoritmer og kompleksitet antages kendt.

Kursusintroduktion
Kursets formål er at give deltagerne evnen til at formulere og løse, via eksakte og heuristiske metoder, problemer der opstår indenfor planlægning, skemalægning og ruteplanlægning.

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:

- gengive i et præcist og passende sprog de generelle algoritmiske metoder som præsenteres i kurset;
- klassificere skedulerings, skemalægnings og ruteplanlægnings problemer å under brug af passende formel notation. ;
- gengive i detaljer de tilegnede algoritmer for et specifikt problem diskuteret i undervisningen (se pensum);
- formulere heltalsprogrammerings modeller for problemerne diskuteret i undervisningen;
- anvende de generelle metoder på nye kombinatoriske optimeringsproblemer, som i natur minder om problemer fra kurset. Herunder give en præcis skriftlig beskrivelse af, hvorledes algoritmen vil se ud i denne anvendelse;
- implementere de designede algoritmer i et passende valgt programmeringssprog;
- analysere de anvendte heuristikker mht. løsningskvalitet, tid- og pladsforbrug og andre relevante karakteristika ved metoderne;
- foretage empiriske afprøvninger af de anvendte metoder, og diskutere de opnåede resultater.

Emneoversigt
Kurset omhandler matematisk modellering og optimering indenfor tre industrielle anvendelsesområder: produktionsplanlægning, serviceskemalægning og ruteplanlægning for køretøjer. Eksempler på anvendelser som betragtes i kurset er flow-shop og job-shop skedulering, resource begrænset projektplanlægning, mandskabsskemalægning, uddannelsesskemalægning og personaleplanlægning, og ruteplanlægning for køretøjer med begrænsninger som kommer fra kapacitet, tidsintervaller og besøgsorden. Hvert problem vil blive præcist formuleret, matematisk modelleret og løst. Blandt de løsningsteknikker som vil blive introduceret og anvendt er heltalsprogrammering, constraint programming og heuristikker. Dedikerede algoritmer baseret på dynamisk programmering eller branch & bound, skitseres også når de med fordel kan anvendes på problemerne.

Litteratur

Meddeles ved kursets start.

Pensum
Se pensumbeskrivelse.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
(a) Projektopgave der bedømmes med karakter efter 7-skalaen og med intern censur. Projektopgaven skal være bestået, for at man kan indstille sig til eksamen. Projektopgaven tæller 40 % af den samlede karakter.

(b) Mundtlig eksamen der bedømmes med karakter efter 7-skala og ekstern censur. Den mundtlige eksamen tæller 60% af den samlede karakter.

Der gives én samlet karakter for kurset.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger, antal timer 50.
Laboratorieøvelser, antal timer 10.
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på engelsk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2009 til 31. januar 2010.