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.
본 학위 연구는 로트 크기를 고려한 생산설비의 스케줄링을 생성하는 방법론을 연구 대상으로 한다. 본 연구는 타이어 공장의 성형설비 스케줄링에서 연구 동기를 얻었으며, 연구 결과를 타이어 공장에 실제 적용하는 것을 목표로 하였다. 공장의 생산계획은 일 단위 계획과 시간 단위 계획으로 분류할 수 있다. 일 단위 계획에서는 병렬 설비 전체를 고려하여 개별 설비에 생산할 량과 제품을 결정한다. 시간 단위 계획에서는 일 단위 계획에서 결정된 제품과 생산량을 기반으로 로트 크기와 생산 순서를 결정한다. 본 연구에서는 두 가지 유형의 로트 크기와 순서를 결정하 연구를 다룬다. (1) 작업 할당이 완료되었다고 가정하고 개별 설비에서 시간 단위 계획을 생성하는 문제, (2) 작업 재할당을 가정하고 병렬 설비에서 시간 단위 계획을 생성하는 문제를 다룬다. 병렬 설비의 생산계획은 개별 설비의 생산 계획보다 문제의 복잡도가 높아지기 때문에 서로 다른 접근 방법이 필요하다.
규격 교체를 고려하여 로트의 크기와 순서를 결정하는 문제는 잘 알려진 NP-난해 문제이다. 수학적 모델링은 간단하고 직관적이지만 계획기간, 규격과 설비의 수가 늘어남에 따라 요구되는 연산시간이 기하급수적으로 증가한다. 특히 로트 크기를 고려한 생산설비 스케줄링 연구는 계획의 정확성을 향상시키기 위해서 계획 수립 단위를 최소화하고, 장기적 관점의 계획 생성을 하기 위해서 계획 대상 기간을 길게 설정한다. 또한 다대수의 병렬 생산 설비의 계획을 생성해야 한다. 공장 설비의 스케줄링은 계산 복잡도가 높지만, 공장의 변동성을 고려하여 여러 설비의 생산계획을 자주 변경해야 하기 때문에 빠른 연산시간이 필수적이다. 이와 같이 복잡성이 높은 문제에서는 경험적 알고리즘이 주로 사용되었다. 본 연구에서는 빠른 연산시간을 보장하기 위해 강화학습 방법론을 사용한다. 일반적으로 근시안적인 계획 생성을 배제하기 위해 롤링 호라이즌 방법을 사용하는데 본 연구에서 장기적인 관점에서 계획을 생성하기 위해서 무한한 계획기간으로 문제를 근사한 모델링 방법을 제안한다.
본 연구에서는 개별 설비와 병렬 설비의 로트크기를 결정하는 문제의 해를 구하기 위해서 각각 싱글 에이전트 강화학습과 다중 에이전트 강화학습 모델을 사용하였다. 학습 기반의 알고리즘은 빠르게 해를 생성할 수 있지만, 현실에 적용할 때는 해의 품질을 안정적으로 보장할 수 없는 문제가 발생한다. 본 연구에서는 강화학습과 혼합 정수계획법을 결합하여 학습 기반 알고리즘의 안정성 문제를 보완하는 알고리즘을 제안한다. 강화학습을 통해서 초기해를 생성하고, 일부 변수만 혼합 정수계획법을 이용하여 최적화하면 문제의 복잡도가 감소하여 제한된 연산시간 내에 정확한 해를 생성할 수 있다.
본 연구는 실제 타이어 공장의 스케줄링에서 동기를 얻었으며, 실험도 타이어 공장의 데이터를 활용함으로써 연구를 산업계에 적용하는 기여를 하였다. (1) 본 연구에서 제안한 알고리즘을 기반으로 타이어 공장에서 수십대 이상의 설비에 대한 스케줄을 생성하는데 기여하였다. (2) 타이어공장에서 Product mix와 수요가 변경될 때 빠르게 스케줄링 연산을 수행함으로써 공정의 capacity 추정에 활용하고 있다.