Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic. (English) Zbl 1073.90512
Summary: This paper presents an ant colony optimization metaheuristic for the solution of an industrial scheduling problem in an aluminum casting center. We present an efficient representation of a continuous horizontal casting process which takes account of a number of objectives that are important to the scheduler. We have incorporated the methods proposed in software that has been implemented in the plant.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C27 | Combinatorial optimization |
| 90B90 | Case-oriented studies in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
Scheduling; Metaheuristics; Ant colony optimization; Aluminum; Casting; Multiple objectivesSoftware:
Tabu searchReferences:
| [1] | Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York |
| [2] | Belton, V.; Elder, M. D., Exploring a multicriteria approach to production scheduling, The Journal of the Operational Research Society, 47, 1, 162-175 (1996) · Zbl 0842.90052 |
| [3] | Bjorndal, M. H.; Capara, A.; Cowling, P. I.; Della Croce, F.; Lourenço, H. R.; Malucelli, F.; Orman, A. J.; Pisinger, D.; Rego, C.; Salazar, J. J., Some thoughts on combinatorial optimization, European Journal of Operational Research, 83, 253-270 (1995) · Zbl 0904.90137 |
| [4] | Blazewicz, J.; Wolfgang, D.; Pesch, E., The job shop scheduling problem: Conventional and new solution techniques, European Journal of Operational Research, 93, 1-33 (1996) · Zbl 0980.90024 |
| [5] | Brandimarte, P., Exploiting process plan flexibility in production scheduling: A multi-objective approach, European Journal of Operational Research, 114, 1, 59-71 (1999) · Zbl 0946.90018 |
| [6] | Brandimarte, P.; Calderini, M., A hierarchical bicriterion appraoch to integrated process plan selection and job-shop scheduling, International Journal of Production Research, 33, 161-181 (1995) · Zbl 0914.90156 |
| [7] | Cavalieri, S.; Gaiardelli, P., Hybrid genetic algorithms for multiple-objective scheduling problem, Journal of Intelligent Manufacturing, 9, 4, 361-367 (1998) |
| [8] | Colorni, A.; Dorigo, M.; Maniezzo, V., Distributed optimization by ant-colonies, (Bourgine, F. V.a. P., Proceedings of the European Conference on Artificial Life (ECAL’91) (1991), MIT Press: MIT Press Cambridge, MA), 134-142 |
| [9] | Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for job-shop scheduling, Belgian Journal of Operations Research (JORBEL), Statistics and Computer Science, 34, 1, 39-53 (1994) · Zbl 0814.90047 |
| [10] | Conway, R. N.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500 |
| [11] | den Besten, M.; Stützle, T.; Dorigo, M., Ant colony optimization for the total weighted tardiness problem, (Schoenauer, M. K.D.; Rudolph, G.; Yao, X.; Lutton, E.; Merelo, J. J.; Schwefel, H.-P., Parallel Problem Solving from Nature: 6th International Conference. Parallel Problem Solving from Nature: 6th International Conference, Lecture Notes on Computer Science, vol. 1917 (2000), Springer: Springer Berlin), 611-620 |
| [12] | Deneubourg, J. L.; Goss, S., Collective patterns and decision-making, Ethology and Evolution, 1, 295-311 (1989) |
| [13] | Deneubourg, J. L.; Pasteels, J. M.; Verhaeghe, J. C., Probabilistic behaviour in ants: A strategy of errors?, Journal of Theorical Biology, 105, 259-271 (1983) |
| [14] | Dorigo, M., 1992. Optimization, learning and natural algorithms. Ph.D. Thesis, Politecnico di Milano, Italy; Dorigo, M., 1992. Optimization, learning and natural algorithms. Ph.D. Thesis, Politecnico di Milano, Italy |
| [15] | Dorigo, M.; Di Caro, G., The ant colony optimization meta-heuristic, (Corne, D.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGraw-Hill: McGraw-Hill New York) |
| [16] | Dorigo, M.; Gambardella, L. M., Ant colonies for the traveling salesman problem, BioSystems, 43, 73-81 (1997) |
| [17] | Dorigo, M., Maniezzo, V., Colorni, A., 1991. Positive feedback as a search strategy, Technical Report No 91-016, Politecnico di Milano, Italy, 20 pp; Dorigo, M., Maniezzo, V., Colorni, A., 1991. Positive feedback as a search strategy, Technical Report No 91-016, Politecnico di Milano, Italy, 20 pp · Zbl 0825.90549 |
| [18] | Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man and Cybernitics, 26, 1, 29-41 (1996) |
| [19] | Du, J.; Leung, J. Y., Minimizing total tardiness onone machine is NP-hard, Mathematics of Operations Research, 15, 483-494 (1990) · Zbl 0714.90052 |
| [20] | Fanti, M. P.; Maione, B.; Naso, D.; Turchiano, B., Genetic multi-criteria approach to flexible line scheduling, International Journal of Approximate Reasoning, 19, 1-2, 5-21 (1998) · Zbl 1044.90507 |
| [21] | Franca, P. M.; Gendreau, M.; Laporte, G.; Muller, F. M., A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times, International Journal of Production Economics, 43, 79-89 (1996) |
| [22] | Glover, F.; Laguna, M., Tabu search, (Modern Heuristic Techniques for Combinatorial Problems (1993), Wiley: Wiley New York), 70-150 · Zbl 0942.90500 |
| [23] | Goss, S.; Beckers, R.; Deneubourg, J. L.; Aron, S.; Pasteels, J. M., How trail laying and trail following can solve foraging problems for ant colonies, (Hughes, R. N., Behavioural Mechanisms of Food Selection. Behavioural Mechanisms of Food Selection, NATO-ASI Series, vol. G20 (1990), Springer: Springer Berlin) |
| [24] | Gravel, M.; Price, W. L.; Gagné, C., Scheduling jobs in an Alcan aluminium factory using a genetic algorithm, International Journal of Production Research, 38, 13, 3031-3041 (2000) |
| [25] | Huang, S. H.; Zhang, H.-C., Artificial neural network in manufacturing: Concepts, applications and perspectives, IEEE Transactions on Components, Packaging and Manufacturing Technology - Part A, 17, 2, 212-228 (1994) |
| [26] | Ishibuchi, H.; Murata, T., A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE Transactions on Systems, Man and Cybernetics - Part C: Applications and Reviews, 28, 3, 392-403 (1998) |
| [27] | Kim, C.-O.; Min, H.-S.; Yih, Y., Integration of inductive learning and neural networks for multi-objective FMS scheduling, International Journal of Production Research, 36, 9, 2497-2509 (1998) · Zbl 0953.90522 |
| [28] | Lee, H. L.; Pinedo, M., Scheduling jobs on parallel machines with sequence-dependent setup times, European Journal of Operational Research, 100, 3, 464-474 (1997) · Zbl 0917.90193 |
| [29] | Lenstra, J. K.; Rinnooy Kan, A. H.G., Computational complexity of discrete optimization problems, Annals of Discrete Mathematics, 4, 121-140 (1979) · Zbl 0411.68042 |
| [30] | Leong, G. K.; Oliff, M. D., A sequencing heuristic for dependent setups in a batch process industry, Omega, 18, 283-297 (1990) |
| [31] | MacCarthy, B. L.; Liu, J., Addressing the gap inscheduling research: A review of optimization and heuristic methods in production scheduling, International Journal of Production Research, 31, 1, 59-79 (1993) |
| [32] | Marett, R.; Wright, M., A comparison of neighborhood search techniques for multi-objective combinatorial problems, Computers and Operations Research, 23, 5, 465-483 (1996) · Zbl 0847.90082 |
| [33] | Min, H.-S.; Yih, Y.; Kim, C.-O., A competitive neural network approach to multi-objective scheduling, International Journal of Production Research, 36, 7, 1749-1765 (1998) · Zbl 0949.90628 |
| [34] | Murata, T.; Ishibuchi, H.; Tanaka, H., Multi-objective genetic algorithm and its applications to flowshop scheduling, Computers and Industrial Engineering, 30, 4, 957-968 (1996) |
| [35] | Nagar, A.; Haddock, J.; Heragu, S., Multiple and bicriteria scheduling: A literature survey, European Journal of Operational Research, 81, 88-104 (1995) · Zbl 0913.90178 |
| [36] | Rubin, P. A.; Ragatz, G. L., Scheduling in a sequence dependent setup environment with genetic search, Computers and Operations Research, 22, 2, 85-99 (1995) · Zbl 0813.90065 |
| [37] | Ruiz-Torres, A. J.; Enscore, E. E.; Barton, R. R., Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem, Computers and Industrial Engineering, 33, 1-2, 257-260 (1997) |
| [38] | Sabuncuoglu, I.; Gurgun, B., A neural network model for scheduling problems, European Journal of Operational Research, 93, 2, 288-299 (1996) · Zbl 0913.90180 |
| [39] | Santos, A.; Dourado, A., Global optimization of energy and production in process industries: A genetic algorithm application, Control Engineering Practice, 7, 549-554 (1999) |
| [40] | Selen, W. J.; Heuts, R. M.J., Operational production planning in a chemical manufacturing environment, European Journal of Operational Research, 45, 38-46 (1990) |
| [41] | Stützle, T., An ant approach to the flow shop problem, (Proceedings of the 6th European Congress on Intelligent Techniques and Soft Computing (EUFIT ’98), vol. 3 (1998), Verlag Mainz: Verlag Mainz Aachen), 1560-1564 |
| [42] | Valls, V.; Perez, M. A.; Quintanilla, M. S., A tabu search approach to machine scheduling, European Journal of Operational Research, 106, 277-300 (1998) · Zbl 0991.90054 |
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.
