Production planning and scheduling problems are a key component in many supply chains. A recurring model in these problems is the multi-item lot sizing model in which a schedule of production is determined for each item being produced so that the demand for each item is satisfied subject to constraints on production, inventory and the operation of the machinery. In order to better understand how to effectively solve mixed-integer programming formulations of multi-item lot sizing models, much of the work in the literature has focused on different variants of the single-item problem.
Recently, a variant in which the underlying network is a cycle has been investigated. Such a variant is motivated by strategic production planning and scheduling problems in which it is often convenient to assume that the planning horizon wraps around on itself, thereby eliminating the need to specify boundary conditions and avoiding possible end effects. Such an approach can be viewed as a form of steady state model.
For this problem a mixed-integer programming formulation for the single-item lot sizing problem on a cycle was proposed, as was an efficient dynamic programming algorithm for its solution which established the computational complexity of the problem. A preliminary investigation of the polyhedral structure of the convex hull of the set of feasible solutions to the problem identified a family of valid inequalities for the mixed-integer programming formulation.
In this project we will extend this work, improve the efficiency of the dynamic programming algorithm, complete the investigation of the polyhedral structure of the convex hull of the set of feasible solutions to the problem, and propose extended formulations and strong reformulations for the problem. We will also consider important variants of the lot-sizing problem such as start-up costs and backlogging.
The University of Newcastle
Bowen Parnell is about to finish a combined Bachelors degree in Mathematics and Mechatronics Engineering (Honours). Bowen strongly believes that we are living in a time where technology has incredible potential to achieve things like automating away our basic needs, and that it should be carefully used to try and make the world a better place. Everything to do with improving processes, making things more efficient and the field of optimisation is a source of enjoyment for Bowen. However learning about the realities of solving these problems from work experiences like building an agriculture start-up in India, developing electronics products as an intern at NewieVentures, and modelling the local rail network to then optimise timetable generation and test new control strategies, these chances to learn about the practicalities of solving problems have been especially appreciated.