Using aggregation to optimize long-term production planning at an underground mine. (English) Zbl 1103.90333
Summary: Motivated by an underground mining operation at Kiruna, Sweden, we formulate a mixed integer program to schedule iron ore production over multiple time periods. Our optimization model determines an operationally feasible ore extraction sequence that minimizes deviations from planned production quantities. The number of binary decision variables in our model is large enough that directly solving the full, detailed problem for a three year time horizon requires hours, or even days. We therefore design a heuristic based on solving a smaller, more tractable, model in which we aggregate time periods, and then solving the original model using information gained from the aggregated model. We compute a bound on the worst case performance of this heuristic and demonstrate empirically that this procedure produces good quality solutions while substantially reducing computation time for problem instances from the Kiruna mine.
MSC:
| 90B30 | Production models |
| 90B35 | Deterministic scheduling theory in operations research |
| 90C10 | Integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
production scheduling applications; mining and metals industries; heuristic integer programming algorithmsReferences:
| [1] | Almgren, T., 1994. An approach to long range production and development planning with application to the Kiruna mine, Sweden. Luleå University of Technology, Doctoral Thesis number 1994:143D.; Almgren, T., 1994. An approach to long range production and development planning with application to the Kiruna mine, Sweden. Luleå University of Technology, Doctoral Thesis number 1994:143D. |
| [2] | Babayev, D.; Glover, F.; Ryan, J., A new knapsack solution approach by integer equivalent aggregation and consistency determination, INFORMS Journal on Computing, 9, 1, 43-50 (1997) · Zbl 0890.90146 |
| [3] | Bell Laboratories, 2001. AMPL, Version 10.6.16.; Bell Laboratories, 2001. AMPL, Version 10.6.16. |
| [4] | Belvaux, G.; Wolsey, L., Modeling practical lot-sizing problems as mixed-integer programs, Management Science, 47, 7, 993-1007 (2001) · Zbl 1232.90169 |
| [5] | Bertsimas, D.; Patterson, S., The traffic flow management rerouting problem in air traffic control: A dynamic network flow approach, Transportation Science, 34, 2, 239-255 (2000) · Zbl 0991.90516 |
| [6] | Carlyle, M.; Eaves, B., Underground planning at stillwater mining company, Interfaces, 31, 4, 50-60 (2001) |
| [7] | Dagdelen, K.; Kuchta, M.; Topal, E., Linear programming model applied to scheduling of iron ore production at the Kiruna mine, Kiruna, Sweden, Transactions of the Society for Mining, Metallurgy, and Exploration, Inc., 312, 194-198 (2001) |
| [8] | Daichendt, M.; Grossmann, I., Preliminary screening procedure for the MINLP synthesis of process systems—I. Aggregation and decomposition techniques, Computers and Chemical Engineering, 18, 8, 663-677 (1994) |
| [9] | Fourer, R.; Gay, D.; Kernighan, B., AMPL: A Modeling Language for Mathematical Programming (1993), Boyd and Fraser: Boyd and Fraser Massachusetts |
| [10] | Glover, F.; Woolsey, R., Aggregating diophantine equations, Zeitschrift für Operations Research, 16, 1, 1-10 (1972) · Zbl 0244.90030 |
| [11] | Harjunkoski, I.; Grossmann, I., A decomposition approach for the scheduling of a steel plant production, Computers and Chemical Engineering, 25, 1647-1660 (2001) |
| [12] | ILOG Corporation, 2001. CPLEX, Version 7.0.; ILOG Corporation, 2001. CPLEX, Version 7.0. |
| [13] | Iyer, R.; Grossmann, I.; Vasantharajan, S.; Cullick, A., Optimal planning and scheduling of offshore oil field infrastructure investment and operations, Industrial and Engineering Chemistry Research, 37, 1380-1397 (1998) |
| [14] | Kannan, R., Polynomial-time aggregation of integer programming problems, Journal of the Association for Computing Machinery, 30, 1, 133-145 (1983) · Zbl 0512.90075 |
| [15] | Kuchta, M.; Newman, A.; Topal, E., Implementing a production schedule at LKAB’s Kiruna mine, Interfaces, 34, 2, 124-134 (2004) |
| [16] | Kulkarni, R.; Mohanty, R., Multilocation plant sizing and timing problem: A study of spatial-temporal decomposition procedure, Production Planning and Control, 7, 5, 471-481 (1996) |
| [17] | Marchand, H.; Wolsey, L., Aggregation and mixed integer rounding to solve MIPs, Operations Research, 49, 3, 363-371 (2001) · Zbl 1163.90671 |
| [18] | Martin, R., Large Scale Linear and Integer Optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 1053.90001 |
| [19] | Mathews, G., On the partition of numbers, Proceedings of the London Mathematical Society, 28, 486-490 (1897) · JFM 28.0168.03 |
| [20] | Mohanty, R.; Singh, R., A hierarchical production planning approach for a steel manufacturing system, International Journal of Operations and Production Management, 12, 5, 69-78 (1992) |
| [21] | Newman, A., Kuchta, M., Martinez, M., 2005. Long- and short-term production at LKAB’s Kiruna mine. Working Paper, Division of Economics and Business and Mining Engineering Department, Colorado School of Mines, Golden, CO, January.; Newman, A., Kuchta, M., Martinez, M., 2005. Long- and short-term production at LKAB’s Kiruna mine. Working Paper, Division of Economics and Business and Mining Engineering Department, Colorado School of Mines, Golden, CO, January. |
| [22] | Puelz, A., A stochastic convergence model for portfolio selection, Operations Research, 50, 3, 462-476 (2002) · Zbl 1163.91419 |
| [23] | Rardin, R., Optimization in Operations Research (1998), Prentice Hall: Prentice Hall Upper Saddle River, NJ |
| [24] | Rogers, D.; Plante, R.; Wong, R.; Evans, J., Aggregation and disaggregation techniques and methodology in optimization, Operations Research, 39, 4, 553-582 (1991) · Zbl 0729.90738 |
| [25] | Sarin, S.; West-Hansen, J., The long-term mine production scheduling problem, IIE Transactions, 37, 2, 109-121 (2005) |
| [26] | Smith, M., Optimizing short-term production schedules in surface mining: Integrating mine modeling software with AMPL/CPLEX, International Journal of Surface Mining, 149-155 (1998) |
| [27] | Smith, M., Sheppard, I., Karunatillake, G., 2003. Using MIP for strategic life-of-mine planning of the lead/zinc stream at Mount Isa Mines. In: 31st International APCOM Symposium Proceedings, Capetown, South Africa, pp. 465-474.; Smith, M., Sheppard, I., Karunatillake, G., 2003. Using MIP for strategic life-of-mine planning of the lead/zinc stream at Mount Isa Mines. In: 31st International APCOM Symposium Proceedings, Capetown, South Africa, pp. 465-474. |
| [28] | Srinivasa, A.; Wilhelm, W., A procedure for optimizing tactical response in oil spill clean up operations, European Journal of Operational Research, 102, 3, 554-574 (1997) · Zbl 0955.90043 |
| [29] | Topal, E., 1998. Long and short term production scheduling of the Kiruna iron ore mine, Kiruna, Sweden. Master of Science Thesis, Colorado School of Mines, Golden, Colorado.; Topal, E., 1998. Long and short term production scheduling of the Kiruna iron ore mine, Kiruna, Sweden. Master of Science Thesis, Colorado School of Mines, Golden, Colorado. |
| [30] | Trout, L., 1995. Underground mine production scheduling using mixed integer programming. In: 25th International APCOM Symposium Proceedings, Brisbane, Australia, pp. 395-400.; Trout, L., 1995. Underground mine production scheduling using mixed integer programming. In: 25th International APCOM Symposium Proceedings, Brisbane, Australia, pp. 395-400. |
| [31] | Winkler, B., 1996. Using MILP to optimize period fix costs in complex mine sequencing and scheduling problems. In: 26th International APCOM Symposium Proceedings, Pennsylvania State University, University Park, Pennsylvania, pp. 441-446.; Winkler, B., 1996. Using MILP to optimize period fix costs in complex mine sequencing and scheduling problems. In: 26th International APCOM Symposium Proceedings, Pennsylvania State University, University Park, Pennsylvania, pp. 441-446. |
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.
