New valid inequalities for a time-indexed formulation of the flexible job shop scheduling problem

dc.contributor.authorLeffler, David
dc.contributor.departmentChalmers tekniska högskola / Institutionen för matematiska vetenskapersv
dc.contributor.departmentChalmers University of Technology / Department of Mathematical Sciencesen
dc.date.accessioned2019-07-03T13:39:19Z
dc.date.available2019-07-03T13:39:19Z
dc.date.issued2015
dc.description.abstractIn this thesis a family of valid inequalities originally formulated for single- and parallel machine scheduling problems are extended to a time-indexed, mixed integer linear programming formulation of the exible job shop scheduling problem. The model of the exible job shop scheduling problem that is used for this purpose was originally formulated in the licentiate thesis [22], and is based on the practical case of scheduling the production of aircraft engine components at a multitask production cell in Trollhättan, Sweden. The strength of the valid inequalities when applied to this model is assessed by means of computational testing. This has been performed using a cutting-plane method on Fattahi test instances, both with the objective of minimizing makespan as well as minimizing tardiness. For both objectives the new valid inequalities have yielded improved lower bounds, however with varying effect. Computational results are reported along with suggestions for implementation of the valid inequalities that are likely to grant the best results. Keywords: multipurpose machine, exible job shop scheduling problem, MILP, mathe- matical optimization, time-indexed decision variables, valid inequalities, polyhedral methods, cutting-plane methods, makespan-tardiness
dc.identifier.urihttps://hdl.handle.net/20.500.12380/217994
dc.language.isoeng
dc.setspec.uppsokPhysicsChemistryMaths
dc.subjectMatematik
dc.subjectGrundläggande vetenskaper
dc.subjectMathematics
dc.subjectBasic Sciences
dc.titleNew valid inequalities for a time-indexed formulation of the flexible job shop scheduling problem
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
local.programmeEngineering mathematics and computational science (MPENM), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
217994.pdf
Storlek:
1.35 MB
Format:
Adobe Portable Document Format
Beskrivning:
Fulltext