Multi-product valid inequalities for the discrete lot-sizing and scheduling problem. (February 2015)

• Record Type: Journal Article
• Authors: Gicquel, C.; Minoux, M.
• Is Part Of: Computers & operations research. Volume 54(2015)
• Page Start: 12
• Page End: 20
• Publication Date: 2015-02
• Subjects: Production planning -- Discrete lot-sizing problem -- Mixed-integer linear programming -- Valid inequalities; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2014.08.022
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We consider a problem arising in the context of industrial production planning, namely the multi-product discrete lot-sizing and scheduling problem with sequence-dependent changeover costs. We aim at developing an exact solution approach based on a Cut & Branch procedure for this combinatorial optimization problem. To achieve this, we propose a new family of multi-product valid inequalities which corresponds to taking into account the conflicts between different products simultaneously requiring production on the resource. We then present both an exact and a heuristic separation algorithm which form the basis of a cutting-plane generation algorithm. We finally discuss computational results which confirm the practical usefulness of the proposed inequalities at strengthening the MILP formulation and at reducing the overall computation time.