An exact approach based on a new pseudo-polynomial network flow model for integrated planning and scheduling

• Published in: Computers & operations research 2016-12, Vol.76, p.183-194
• Main Authors: Rietz, Jürgen, Alves, Cláudio, Braga, Nuno, Valério de Carvalho, José
• Format: Article
• Language: English
• Subjects: Benchmarking; Integer linear programming; Mathematical models; Network flow models; Networks; Operations research; Polynomials; Production planning; Production planning and scheduling; Production scheduling; Scheduling; State of the art; Strategy; Studies; Supply chain management
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2016.07.008

The resolution of planning and scheduling problems in a coordinated way within the supply chain is very challenging. In this paper, we address the integration of medium-term production planning and short-term scheduling models. We particularly focus on a specific problem defined on parallel machines that has recently been explored in the literature. The problem is characterized by a set of jobs that can be processed only from a given release date onward, and which should be finished at a given due date. At a first stage, the problem consists in assigning the jobs to consecutive time periods within the planning horizon, while at a second stage, the jobs have to be scheduled on the available machines. Our contribution consists in the description and analysis of a new detailed scheduling model based on a pseudo-polynomial network flow formulation that can be used to exactly solve real size instances. We explore different strategies to simplify the model and reduce its number of constraints. To evaluate the performance of our approaches, we report an extensive set of computational experiments on benchmark instances from the literature. The results obtained show that our approach outperforms, on some classes of instances, other state-of-the-art methods described recently in the literature. •New pseudo-polynomial network flow model for integrated planning and scheduling.•We describe procedures to simplify the model.•The problem arises in the area of production planning.•Our model improves the resolution of the problem for different classes of instances.