Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Shift Design and Driver Scheduling Problem
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2018 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Skift design och schemaläggning för förare (Swedish)
Abstract [en]

Scheduling problem and shift design problems are well known NP-hard problems within the optimization area. Often time, the two problems are studied individually. In this thesis however, we are looking at the combination of both problems. More specifically, the aim of this thesis is to suggest an optimal scheduling policy given that there are no predefined shifts to begin with. The duration of a shift, along with the start and end time may vary. Thus we have proposed to split the problem into two sub-problems: weekly scheduling problem and daily scheduling problem. As there are no exact solution methods that are feasible, two meta-heuristics method has been employed to solve the sub-problems: Simulated Annealing (SA) and Genetic Algorithm (GA). We have provided proofs of concepts for both methods as well as explored the scalability. This is especially important as the number of employee is expected to grow significantly throughout the year. The results obtained has shown to be promising and can be built upon for further capabilities.

Abstract [sv]

Schemaläggning och skiftdesignsproblem är välkända och välstuderade NP-svåra beslutsproblem inom optimeringsområdet. Oftast så studeras dessa problem enskilt, men i detta arbete så studeras en kombination av båda problemen. Mer specifikt är målet med detta arbete att föreslå ett förnuftigt handlingsätt till att skapa ett veckoschema där skift inte är predefinierade för alla veckor. Starttiden, sluttiden och varaktigheten av ett skift kan förändras från vecka till vecka. Därför har problemet delats upp till två delar: Veckoschemaläggnings- och dagsschemaläggningsproblem. Trots uppdelningen så är båda delproblem för komplexa för att lösas exakt. Därför har två metaheuristiska metoder använts som lösningsmetoder: Simulerad Glödgning och Genetisk Algoritm. I detta arbete bevisas båda lösningsmetoderna till att vara bra nog, och dessutom studeras även skalbarheten av modellen. Detta senare är särskilt viktigt eftersom antal anställda som ska schemaläggas förväntas att öka genomåren. De erhållna resultaten har visat sig vara lovande och bevisligen så kan modellen expanderas med er villkor

Place, publisher, year, edition, pages
2018.
Series
TRITA-SCI-GRU ; 2018:051
Keywords [en]
Integer Linear Programming, Scheduling Problem, Shift-design problem, Genetic Algorithm, Simulated Annealing
Keywords [sv]
Integer Linjar Programmering, Schemaläggning Problem, Skift Design
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-227263OAI: oai:DiVA.org:kth-227263DiVA, id: diva2:1203979
External cooperation
Bzzt AB
Subject / course
Optimization and Systems Theory
Educational program
Master of Science - Applied and Computational Mathematics
Supervisors
Examiners
Available from: 2018-05-05 Created: 2018-05-05 Last updated: 2018-05-05Bibliographically approved

Open Access in DiVA

fulltext(1410 kB)144 downloads
File information
File name FULLTEXT01.pdfFile size 1410 kBChecksum SHA-512
126e0bd65665ccc4a5d886b5bfa0faeaefbbb5f4305fe6779a80f8c7a5a13546721eb0264793778927c7f7d0940a6f80d62525127549a4513d51e0f04ae71f07
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 144 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 372 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf