MIP-based fix-and-optimise algorithms for the parallel machine capacitated lot-sizing and scheduling problem

This paper examines the capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such a problem frequently arises in the semiconductor manufacturing industry by which this paper is motivated. A mixed integer programming (MIP) model is constructed for the problem. Two MIP-based fix-and-optimise algorithms are proposed in which the binary decision variables associated with the assignment of machines are first fixed using the randomised least flexible machine (RLFM) rule and the rest of the decision variables are settled by an MIP solver. Extensive experiments show that the proposed algorithms outperform the state-of-the-art MIP-based fix-and-optimise algorithms in the literature, especially for instances with high machine flexibility and high demand variation.