Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
A column generation approach to scheduling of parallel identical machines
Linköping University, Department of Mathematics.
2019 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

This thesis aims to implement a combination of Linear Programming Column Generation and a Large Neighbourhood Search heuristic to solve scheduling problems. The resulting method is named Integer Programming Column Search (IPCS). For computational evaluation, the IPCS method is applied to the problem Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources generalised to parallel identical machines.

The interest of combining exact procedures with heuristic approaches is quickly growing since scheduling problems have many and complex real-world applications. Most of these problems are NP-hard and therefore very challenging to solve. By using a combination of heuristic strategies and exact procedures, it can be possible to find high-quality solutions to such problems within an acceptable time horizon.

The IPCS method uses a greedy integer programming column generating problem introduced in a previous work. This problem is designed to generate columns that are useful in near-optimal integer solutions. A difference to previously introduced method is that we here build a master problem, an Integer Programming Column Search Master (IPCS-Master). This is used to update the dual solution that is provided to the greedy integer programming column generating problem.

The computational performance of the IPCS method is evaluated on instances with 60, 70, 80, 90 and 100 jobs. The result shows that the combined design encourage the generation of columns that benefit the search of near-optimal integer solutions. The introduction of an IPCS-Master, which is used to update the dual variable values, generally leads to fewer pricing problem iterations than when no master problem is used.

Place, publisher, year, edition, pages
2019. , p. 52
Keywords [en]
Scheduling, Parallel Identical Machines, Column Generation, Large Neighbourhood Search, Mixed Integer Programming, GCG
National Category
Other Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-160220ISRN: LiTH-MAT-EX--2019/07--SEOAI: oai:DiVA.org:liu-160220DiVA, id: diva2:1350640
Subject / course
Applied Mathematics
Supervisors
Examiners
Available from: 2019-09-12 Created: 2019-09-11 Last updated: 2019-09-12Bibliographically approved

Open Access in DiVA

fulltext(2985 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 2985 kBChecksum SHA-512
fee8a823e508ef1471046aadb4e5d24a0251c89d8a179ae743a99262e125dfa5c7d4c6b02a76ada679e9b4ae330fe49bc626096fa0a977ed861ea3399f2c6fff
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics
Other Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 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: 67 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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