Lot-sizing and scheduling in flat-panel display manufacturing process

In this paper, we consider a lot-sizing and scheduling problem arising in the real-world flat-panel display industry. This problem is formulated as a variant of the discrete lot-sizing and scheduling problem with a sequence-dependent setup. After describing the characteristics of the problem and analyzing its computational complexity, we propose an extended formulation based on a network structure. Even though the problem is NP-hard in general, we show that there exist special cases solvable in polynomial time. For the general cases, we demonstrate the tightness of the extended formulation by means of both polyhedral analysis and computational experiments with artificially generated data and real-world industry data. We also propose a relax-and-fix heuristic algorithm based on the extended formulation, which has been deployed in practice, with the corresponding computational results.