Integer Linear Programming Applied to Production Planning
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Complex adaptive systems (MPCAS), MSc
Engineering mathematics and computational science (MPENM), MSc
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2024
Författare
BUSKE, JESPER
JENDLE, THEODOR
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
The Job-Shop Scheduling Problem (JSSP) is a classic optimization problem that
has been a focal point in the field of operational research for decades. As industries
advance into Industry 4.0, optimizing production planning becomes increasingly cru cial to enhance efficiency and competitiveness. This thesis explores the application
of Integer Linear Programming (ILP) to an extended version of the JSSP, intro ducing new constraints and utilizing a heuristic when solving the problem. In this
work, we present our mathematical formulation for the extended job-shop schedul ing problem. Our approach embeds additional constraints and variables that reflect
real-world production scenarios more accurately than traditional JSSP models. The
performance of our formulation is evaluated by comparing our results against two
benchmarks, where the first benchmark compares the results to a scheduler solely
based on heuristics, and the other compares the result to a lower bound of the
optimal solution. These comparisons provide insight into the performance of our
proposed model. Furthermore, we discuss difficulties associated with solving this
NP problem. Expressing the complications of computational complexity and its ef fects on our extension. This research not only advances the theoretical understand ing and exploration of different useful techniques regarding job-shop scheduling but
also provides practical tools and insights for optimizing production planning in the
era of Industry 4.0.
Beskrivning
Ämne/nyckelord
ILP, Optimization, Job-shop Scheduling Problem, GLPK, Time-indexed formulation, Extended Job-shop Scheduling Problem