A New Branching Rule to Solve the Capacitated Lot Sizing and Scheduling Problem with Sequence Dependent Setups
DOI:
https://doi.org/10.5540/tema.2017.018.03.515Keywords:
Lot Sizing, Scheduling, Mixed Integer Linear Programming, Branch-and-Bound AlgorithmAbstract
In this paper, we deal with the Capacitated Lot Sizing and Scheduling Problem with sequencedependent setup times and costs - CLSD model. More specifically, we propose a simple reformulation for the CLSD model that enables us to define a new branching rule to be used in Branch-and-Bound (or Branch-and-Cut) algorithms to solve this NP-hard problem. Our branching rule can be easily implemented in commercial solvers. Computational tests performed in 240 test instances from the literature show that our approach can significantly reduce the running time to solve this problem using a Branch-and-Cut algorithm of a commercial MIP solver.Therefore, our approach can also improve the performance of other approaches that need to solve partial sub problems of the CLSD model in each iteration, such as Lagrangian approaches and heuristics based on the mathematical formulation of the problem.References
B. Almada-Lobo, et al. ``Industrial insights into lot sizing and scheduling modeling''. Pesquisa Operacional, 2015.
C. Almeder and B. Almada-Lobo. ``Synchronisation of scarce resources for a parallel machine lotsizing problem''. International Journal of Production Research, v. 49, n. 24, p. 7315-7335, 2011.
S. A. de Araujo, M. N. Arenales and A. R. Clark. ``Lot sizing and furnace scheduling in small foundries''. Computers & Operations Research, 35.3: 916-932, 2008.
H. Chen. ``Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems''. Omega, 2015.
A. R. Clark and S. J. Clark. ``Rolling-horizon lot-sizing when set-up times are sequence-dependent''. International Journal of Production Research, 38.10: 2287-2307, 2000.
K. Copil, et al. ``Simultaneous lotsizing and scheduling problems: a classification and review of models''. OR Spectrum, 2016.
D. Ferreira, R. Morabito, and Socorro Rangel. ``Solution approaches for the soft drink integrated production lot sizing and scheduling problem''. European Journal of Operational Research, 196.2: 697-706, 2009.
D. Ferreira, R. Morabito, and Socorro Rangel. ``Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants''. Computers & Operations Research, 37.4: 684-691, 2010.
B. Fleischmann and H. Meyr. ``The general lotsizing and scheduling problem''. Operations-Research-Spektrum, v. 19, n. 1, p. 11-21, 1997.
C. H. Glock, E. H. Grosse, and J. M. Ries. ``The lot sizing problem: A Tertiary study''. International Journal of Production Economics, 155: 39-51, 2014.
L. Guimaraes, D. Klabjan, and B. Almada-Lobo. ``Pricing, relaxing and fixing under lot sizing and scheduling''. European Journal of Operational Research, 230.2: 399-411, 2013.
L. Guimarães, D. Klabjan, and B. Almada-Lobo. ``Modeling lotsizing and scheduling problems with sequence dependent setups''. European Journal of Operational Research, v. 239, n. 3, p. 644-662, 2014.
K. Haase. ``Capacitated lot-sizing with sequence dependent setup costs''. Operations-Research-Spektrum, 18.1: 51-59, 1996.
R. J. W. James and B. Almada-Lobo. ``Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics''. Computers & Operations Research, 38.12: 1816-1825, 2011.
G. M. Kopanos, L. Puigjaner and C. T. Maravelias. ``Production planning and scheduling of parallel continuous processes with product families''. Industrial & engineering chemistry research, 50.3: 1369-1378, 2010.
H. Meyr. ``Simultaneous lotsizing and scheduling by combining local search with dual reoptimization''. European Journal of Operational Research, v. 120, n. 2, p. 311-326, 2000.
H. Meyr. ``Simultaneous lotsizing and scheduling on parallel machines''. European Journal of Operational Research, v. 139, n. 2, p. 277-292, 2002.
H. Meyr and M. Mann. ``A decomposition approach for the General Lotsizing and Scheduling Problem for Parallel production Lines''. European Journal of Operational Research, v. 229, n. 3, p. 718-731, 2013.
W. Wei, et al. ``Tactical production and distribution planning with dependency issues on the production process''. Omega, 2016.
L. A. Wolsey. ``MIP modelling of changeovers in production planning and scheduling problems''. European Journal of Operational Research, v. 99, n. 1, p. 154-165, 1997.
J. Xiao, et al. ``A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times''. Computers & Operations Research, 63: 72-82, 2015.
S. Çgri and B. Bilgen. ``Hybrid simulation and MIP based heuristic algorithm for the production and distribution planning in the soft drink industry''. Journal of Manufacturing Systems, 33.3: 385-399, 2014.
Downloads
Additional Files
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.