Combining GLSP and ATSP approaches to lot sizing and sequencing in the production of animal feed supplements. (Combinação de abordagens GLSP e ATSP para o problema de dimensionamento e sequenciamento de lotes de produção de suplementos para nutrição animal.) (Portuguese. English summary) Zbl 1257.90026
Summary: In this paper we study the combination of GLSP (General Lot Sizing and Scheduling Problem) and ATSP (Asymmetric Travelling Salesman Problem) approaches with sub-tour elimination and patching to a lot sizing and sequencing problem in the animal nutrition industry. This problem consists of deciding the lots size for each product as well the production sequence of the lots, while meeting demand without backlogs and minimizing production and inventory costs. The coordination of these decisions is a challenge for production scheduling in this industry as the setup times are sequence dependent. The ATSP approaches are compared with relax-and-fix approaches applied to the GLSP (General Lot-sizing and Scheduling Problem) formulated in previous research, using real data from an animal nutrition plant in Sao Paulo state.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C27 | Combinatorial optimization |
| 90B30 | Production models |
References:
| [1] | Allahverdi A., A Review of Scheduling Research Involving Setup Considerations, Omega International Journal of Management Science 27 pp 219– (1999) · doi:10.1016/S0305-0483(98)00042-5 |
| [2] | Applegate D., Implementing the DantzigFulkerson -Johnson Algorithm for Large Traveling Salesman Problems, Mathematical Programming 97 pp 91– (2003) · Zbl 1106.90369 · doi:10.1007/s10107-003-0440-4 |
| [3] | Araujo S.A., Problema de Dimensionamento de Lotes Monoestágio com Restrição de Capacidade: Modelagem, Método de Resolução e Resultados Computacionais, Pesquisa Operacional 23 (3) pp 403– (2003) |
| [4] | Araujo S.A., Dimensionamento de lotes e programação do forno numa fundição de pequeno porte, Gestão & Produção 11 (2) pp 165– (2004) · doi:10.1590/S0104-530X2004000200003 |
| [5] | Arenales M.N., Pesquisa Operacional 1 (2007) |
| [6] | Armentano V.A., Omega 27 pp 275– (1999) · doi:10.1016/S0305-0483(98)00045-0 |
| [7] | Askin R., Modeling and analysis of manufacturing systems (1993) · Zbl 0840.90081 |
| [8] | Blazewicz J., The job shop scheduling problem: Conventional and new solution techniques, European Journal of Operational Research 93 (1) pp 1– (1996) · Zbl 0980.90024 · doi:10.1016/0377-2217(95)00362-2 |
| [9] | Brito A.B. (2006) |
| [10] | Buriol L., A new memetic algorithm for the asymmetric traveling salesman problem (2003) · Zbl 1062.90052 |
| [11] | Carpaneto G., Exact solution of large scale asymmetric travelling salesman problems, ACM Transactions on Mathematical Software 21 (4) pp 394– (1995) · Zbl 0887.65058 · doi:10.1145/212066.212081 |
| [12] | Cirasella J., The asymmetric traveling salesman problem: Algorithms, instance generators, and tests, Springer Lecture Notes in Computer Science 2153 pp 32– (2001) · Zbl 1010.68848 · doi:10.1007/3-540-44808-X_3 |
| [13] | Clark A.R., Rolling-horizon lot-sizing when set-up times are sequence-dependent, International Journal of Production Research 38 pp 2287– (2000) · Zbl 0973.90517 · doi:10.1080/00207540050028106 |
| [14] | Clark A.R., Optimization Approximations for Capacity Constrained Material Requirement Planning: Internal Research Report. MS-20020-2 (2003) |
| [15] | Drexl A., Proportional Lot sizing and Scheduling, International Journal of Production Economics 40 pp 73– (1995) · Zbl 1002.90024 · doi:10.1016/0925-5273(95)00040-U |
| [16] | Drexl A., Lot sizing and Scheduling: Survey and extensions, European Journal of Operational Research 99 (2) pp 221– (1997) · Zbl 0923.90067 · doi:10.1016/S0377-2217(97)00030-1 |
| [17] | Ferreira D., Um modelo de otimização inteira mista e heurísticas relax and fix para a programação da produção de fábricas de refrigerantes de pequeno porte, Produção 18 (1) pp 76– (2008) · doi:10.1590/S0103-65132008000100006 |
| [18] | Ferreira D., Solution approaches for the soft drink integrated production lot sizing and scheduling problem, European Journal of Operational Research (2008) |
| [19] | Santini Giuliana, Relatório Setorial Final: Setor: Insumos Suínos (2004) |
| [20] | Fleischmann B., The discrete lot-sizing and scheduling problem with sequence-dependent setup-costs, European Journal of Operational Research 75 pp 395– (1994) · Zbl 0804.90070 · doi:10.1016/0377-2217(94)90083-3 |
| [21] | Fleischmann B., The general lot sizing and scheduling problem, OR Spectrum 19 (1) pp 11– (1997) · Zbl 0892.90055 · doi:10.1007/BF01539800 |
| [22] | França P.M., A heuristic method for lot-sizing in multi-stage systems, Computers & Operations Research 24 (9) pp 861– (1997) · Zbl 0891.90056 · doi:10.1016/S0305-0548(96)00097-4 |
| [23] | Frieze A.M., On patching algorithms for random asymmetric travelling salesman problem, Mathematical Programming 46 pp 361– (1990) · Zbl 0742.90064 · doi:10.1007/BF01585751 |
| [24] | Frieze A.M., When is the assignment bound tight for the asymmetric traveling-salesman problem?, SIAM Journal on Computing 24 (3) pp 484– (1995) · Zbl 0833.90096 · doi:10.1137/S0097539792235384 |
| [25] | Gershwin S., Manufacturing systems engineering (1994) · Zbl 0903.90070 |
| [26] | Glover F., Construction heuristics for the asymmetric TSP, European Journal of Operational Research 129 pp 555– (2001) · Zbl 1125.90402 · doi:10.1016/S0377-2217(99)00468-3 |
| [27] | Graham E.L., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics 5 pp 287– (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [28] | Graves S.C., Logistics of Production and Inventory 4 (1993) · Zbl 0798.90028 |
| [29] | Gutin G., The Traveling Salesman Problem and its Variations, in: Exponential Neighborhoods and Domination Analysis for the TSP (2002) |
| [30] | Haase K., Capacitated Lot-Sizing with Sequence Dependent Setup Costs, OR Spectrum 18 pp 51– (1996) · Zbl 0843.90038 · doi:10.1007/BF01539882 |
| [31] | Haase K., Lot Sizing and Scheduling with Sequence Dependent Setup Costs and Times and Efficient Rescheduling Opportunities, International Journal of Production Economics 66 pp 159– (2000) · doi:10.1016/S0925-5273(99)00119-X |
| [32] | Hax A., Production and inventory management (1984) |
| [33] | A Global Perspective on the Animal Feed Industry (2006) |
| [34] | Johnson D.S., The Traveling Salesman Problem and its Variations, in: Experimental analysis of heuristics for the asymmetric travelling salesman problem: algorithms, instance generators and tests (2002) |
| [35] | Jonhson L.A., Operations research in production planning, scheduling and inventory control (1974) |
| [36] | Junger M., Network Models 7, in: The traveling salesman problem pp 225– (1995) |
| [37] | Karimi B., The capacitated lot sizing problem: a review of models and algorithms, Omega International Journal of Management Science 31 (5) pp 365– (2003) · doi:10.1016/S0305-0483(03)00059-8 |
| [38] | Karp R.M., A patching algorithm for the nonsymmetric traveling-salesman problem, SIAM Journal on Computing 8 (4) pp 561– (1979) · Zbl 0427.90064 · doi:10.1137/0208045 |
| [39] | Karp R.M., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, in: Probabilistic analysis of heuristics (1985) |
| [40] | Laguna M.A., Heuristic for Production Scheduling and Inventory Control in the presence of Sequence-Dependent Setup Times: Internal Research Report (1999) |
| [41] | Laporte G., The traveling salesman problem: An overview of exact and approximate algorithms, European Journal of Operational Research 59 pp 231– (1992) · Zbl 0760.90089 · doi:10.1016/0377-2217(92)90138-Y |
| [42] | Laporte G., A Cutting Planes Algorithm for the m-Salesmen Problem, The Journal of the Operational Research Society 31 (11) pp 1017– (1980) · Zbl 0441.90067 · doi:10.1057/jors.1980.188 |
| [43] | Lawler E.L., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985) · Zbl 0562.00014 |
| [44] | Lawler E.L., Logistics of Production and Inventory 4, in: Sequencing and scheduling: Algorithms and complexity pp 445– (1993) |
| [45] | Luche J.R., Otimização na programação da produção de grãos eletrofundidos: Um estudo de caso, Gestão & Produção 12 (1) pp 135– (2005) · doi:10.1590/S0104-530X2005000100012 |
| [46] | Maes J., Multi-item single-level capacitated dynamic lot-sizing heuristics: a general review, Journal of the Operational Research Society 39 pp 991– (1988) · Zbl 0655.90018 · doi:10.1057/jors.1988.169 |
| [47] | Meyr H., Simultaneous lot sizing and scheduling by combining local search with dual reoptimization, European Journal of Operational Research 120 pp 311– (2000) · Zbl 0943.90037 · doi:10.1016/S0377-2217(99)00159-9 |
| [48] | Meyr H., Simultaneous lot sizing and scheduling on parallel machines, European Journal of Operational Research 139 pp 277– (2002) · Zbl 1001.90034 · doi:10.1016/S0377-2217(01)00373-3 |
| [49] | Nahmias S., Production and Operations Analysis (1995) |
| [50] | Orman A.J., A survey of different integer programming formulations of the traveling salesman problem: Working paper LSEOR 04.67 (2004) |
| [51] | Padberg M., A Branch and Cut Algorithm for the Resolution of Large-scale Symmetric Traveling Salesman Problems, SIAM Review 33 (1) pp 66– (1991) · Zbl 0734.90060 · doi:10.1137/1033004 |
| [52] | Pataki G., Teaching Integer Programming Formulations Using the Traveling Salesman Problem, SIAM review 45 pp 116– (2003) · Zbl 1040.90024 · doi:10.1137/S00361445023685 |
| [53] | Pekny J.F., A parallel Branch and Bound Algorithm for Solving Large Asymetric Travelling Salesman Problems, Proceedings ACM pp 56– (1990) |
| [54] | Pinedo M., Scheduling: theory, algorithms, and systems (1995) · Zbl 1145.90393 |
| [55] | Pochet Y., Production Planning by Mixed Integer Programming (2006) · Zbl 1102.90039 |
| [56] | Potts C., Scheduling with batching: a review, European Journal of Operational Research 120 (2) pp 228– (2000) · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8 |
| [57] | Rangel S., Um modelo de dimensionamento de lotes para uma fábrica de refrigerantes, Tema - Tendências em Matemática Aplicada e Computacional 4 (2) pp 237– (2003) · doi:10.5540/tema.2003.04.02.0237 |
| [58] | Salomon M., Solving the discrete lot sizing and scheduling problem with sequence dependent set-up costs and set-up times using the Travelling Salesman Problem with time windows, European Journal of Operational Research 100 pp 494– (1997) · Zbl 0918.90087 · doi:10.1016/S0377-2217(96)00020-3 |
| [59] | Perfil 2005: Posicionamento da Indústria de Alimentação Animal (2006) |
| [60] | Toledo C.F., Um modelo de otimização para o problema integrado de dimensionamento de lotes e programação da produção em fábricas de refrigerantes, Pesquisa Operacional 27 (1) pp 155– (2007) · Zbl 1161.90400 · doi:10.1590/S0101-74382007000100009 |
| [61] | Toledo C.F., Multi-population genetic algorithm to solve the synchronized and integrated two-level lot-sizing and scheduling problem, International Journal of Production Research (2008) |
| [62] | Toledo F.M.B., A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines, European Journal of Operational Research 175 (2) pp 1070– (2006) · Zbl 1142.90511 · doi:10.1016/j.ejor.2005.06.029 |
| [63] | Toso E.A.V., Dimensionamento e Sequenciamento de Lotes de Produção na Indústria de Suplementos para Nutrição Animal (2008) |
| [64] | Toso E.A.V., Lot-Sizing and Sequencing Optimisation at an Animal-Feed Plant (2007) |
| [65] | Toso E.A.V., Otimização no dimensionamento e sequenciamento de lotes de produção: estudo de caso numa fábrica de rações, Gestão & Produção 12 (2) pp 203– (2005) · doi:10.1590/S0104-530X2005000200006 |
| [66] | Trigeiro W.W., Management Science 35 (3) pp 353– (1989) · doi:10.1287/mnsc.35.3.353 |
| [67] | Williams P., Model Building in Mathematical Programming (1993) |
| [68] | Winston W., Operations Research: Applications and algorithms (1991) · Zbl 0723.90048 |
| [69] | Wolsey L.A., Integer Programming (1998) · Zbl 0930.90072 |
| [70] | Zhang W., Truncated Branch-and-Bound: A Case Study on the Asymmetric TSP, Spring Symposium on AI and NP-Hard Problems pp 160– (1993) |
| [71] | Zhang W., A note on the complexity of the asymmetric travelling salesman problem, Operations Research Letters 20 pp 31– (1997) · Zbl 0892.90177 · doi:10.1016/S0167-6377(96)00037-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
