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

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/217994
Download file(s):
File Description SizeFormat 
217994.pdfFulltext1.38 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: New valid inequalities for a time-indexed formulation of the flexible job shop scheduling problem
Authors: Leffler, David
Abstract: In 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
Keywords: Matematik;Grundläggande vetenskaper;Mathematics;Basic Sciences
Issue Date: 2015
Publisher: Chalmers tekniska högskola / Institutionen för matematiska vetenskaper
Chalmers University of Technology / Department of Mathematical Sciences
URI: https://hdl.handle.net/20.500.12380/217994
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.