Lot sizing and scheduling problem for parallel machines

Abstract

This thesis focuses on developing a methodology for scheduling production machines while considering lot sizes. This research is motivated by the scheduling challenges observed in an actual tire manufacturing plant, and aimed to apply the research findings to the practical operations of the tire factory. The factory's planning can be classified into daily and hourly planning. In the daily planning, the production quantity and items to be produced for individual machines are determined by considering the entire parallel machine system. In the hourly planning, based on the products and production quantities determined in the daily planning, the lot sizes and production sequences are determined. However, in the daily planning, uneven workloads on the machine frequently occur due to the allocation of jobs without considering the sequence of operation and lot size. In this research, we deal with two types of lot size problems. (1) The problem of generating hourly planning on individual machines assuming that job assignments have been completed. (2) The problem involves generating hourly schedule on parallel machines under the assumption of job reassignment for every job. Due to the increased complexity in the production scheduling of parallel machines compared to individual machines scheduling, different approaches are required.

The problem of determining lot sizes and sequences while taking into account setup change is a well-known NP-hard problem. Mathematical modeling is simple and intuitive, but the required computation time increases exponentially as the planning horizon, the number of products, and the number of machines increase. In production scheduling research that considers lot size, it is necessary to reduce the period size for improved planning accuracy. And to generate long-term plans, including multiple parallel production machines, the planning horizon is extended as much as possible. For these reasons, this research requires high computational complexity, but quick computation times are essential due to the need to frequently adjust production plans to account for factory variability. Heuristics are usually used to solve problems of industrial size. In this thesis, we utilize reinforcement learning(RL) to ensure fast computation times. To avoid myopic scheduling, we proposes a modeling approach with an infinite planning horizon to generate schedules from a long-term perspective.

Single-agent reinforcement learning and multi-agent reinforcement learning models are employed to find solutions to the lot sizing problem for individual and parallel machines, respectively. Learning-based algorithms can produce quick solutions, but when applied in real-world scenarios, there can be issues with ensuring the stability of solution quality. In this research, a methodology is proposed that combines RL with mixed-integer programming to address the stability issues of learning-based algorithms. Through RL, the initial solution is generated, and the solutions for some variables are determined using mixed-integer programming.

This research drew motivation from actual tire manufacturing plants and made practical contributions to the industry by applying experiments to real-world tire factory operations. (1) Based on the algorithm proposed in this research, the schedules for dozens of parallel facilities are currently being generated in tire factory. (2) In tire factories, the scheduling computations are performed rapidly when there are changes in product mix and demand, which are then utilized for estimating the capacity of the production process.