A Novel Decomposition-Based Exact Solution Approach for a Lot-sizing and Scheduling Problem

Işık E. E., Taşkın Z. C., Ağralı S.

15th International Workshop on Lot Sizing, Groningen, Hollanda, 27 - 29 Ağustos 2025, ss.20-24, (Özet Bildiri)

  • Yayın Türü: Bildiri / Özet Bildiri
  • Basıldığı Şehir: Groningen
  • Basıldığı Ülke: Hollanda
  • Sayfa Sayıları: ss.20-24
  • Yıldız Teknik Üniversitesi Adresli: Evet

Özet

In this study, we focus on a single-machine single-level lot-sizing and scheduling problem with sequence-dependent setup costs. The problem is essential for production planning due to its effect on overall efficiency. To find efficient solutions, we develop a decomposition-based exact solution approach. Using this approach, we decompose the problem and use the integer L-shaped cuts to reach exact solutions. In the decomposed model, our master problem determines which products are produced in which period and in what quantity. On the other hand, our subproblem determines the sequence of production that is decided in the master problem. We are using the integer L-shaped cuts since our subproblem has binary variables. However, the integer L-shaped cuts are weak in their basic version. Therefore, we perform improvements on the basic model. We start by strengthening the cuts by calculating better lower bounds and through lifting. Afterwards, we disaggregate the cuts to develop another set of cutting planes. Our preliminary studies show that the algorithm spends most of its time solving the subproblem. Considering this, we introduce a dynamic programming-based algorithm to efficiently solve our subproblem. We make our computational tests on a benchmark dataset to compare the efficacy of the developed algorithm and the improvements. The results show that our decomposition-based exact solution approach outperforms exact solution approaches in the literature.