Купить СНПЧ А7 Архангельск, оперативня доставка


Applying Milp/Heuristic Algorithms to Automated Job-Shop Scheduling Problems in Aircraft-Part Manufacturing

DOI: http://dx.doi.org/10.13084/2175-8018.v05n10a03



Adrián M. Aguirre1, Carlos A. Méndez2, Álvaro G. Sánchez3 & Miguel O. Mier4


Abstract: This work presents efficient algorithms based on Mixed-Integer Linear Programming (MILP) and heuristic strategies for complex job-shop scheduling problems raised in Automated Manufacturing Systems. The aim of this work is to find alternative a solution approach of production and transportation operations in a multi-product multi-stage production system that can be used to solve industrial-scale problems with a reasonable computational effort. The MILP model developed must take into account; heterogeneous recipes, single unit per stage, possible recycle flows, sequence-dependent free transferring times and load transfer movements in a single automated material-handling device. In addition, heuristic-based strategies are proposed to iteratively find and improve the solutions generated over time. These approaches were tested in different real-world problems arising in the surface-treatment process of metal components in the aircraft manufacturing industry.

Key words: MILP-based algorithm. Automated Manufacturing Systems. Job-shop Scheduling problems. Real-world applications in aircraft-part fabrication process.


1 Dr., Universidad Nacional del Litoral, Consejo Nacional de Investigaciones Científicas y Técnicas (UNL-CONICET), CAPSE-INTEC. E-mail: aaguirre@intec.unl.edu.ar .
2 Dr., Universidad Nacional del Litoral, Consejo Nacional de Investigaciones Científicas y Técnicas (UNL-CONICET), CAPSE-INTEC: E-mail: cmendez@intec.unl.edu.ar.
3 Dr., Escuela Técnica Superior de Ingenieros Industriales, Universidad Politécnica de Madrid (ETSII-UPM), Ingeniería de Organización. E-mail: alvaro.garcia@upm.es .
4 Dr., Escuela Técnica Superior de Ingenieros Industriales, Universidad Politécnica de Madrid, (ETSII-UPM), Ingeniería de Organización. E-mail: miguel.ortega.mier@upm.es .


Literatura Citada

AGUIRRE, A.M.; MÉNDEZ, C.; DE PRADA, C. An iterative MILP-based approach to automated multi-product multi-stage manufacturing systems. Computer Aided Chemical Engineering, v. 31, p. 1085-1089

AGUIRRE, A.M.; MÉNDEZ, C.A.; CASTRO, P.M. A novel optimization method to automated wet-etch station scheduling in semiconductor manufacturing systems. Computers & Chemical Engineering, v. 35, n. 12, p. 2960-2972, 2011. http://dx.doi.org/10.1016/j.compchemeng.2011.02.014

AGUIRRE, A.M.; MÉNDEZ, C.A.; CASTRO, P.M.; DE PRADA, C. MILP-based Approach for the Scheduling of Automated Manufacturing System with Sequence-Dependent transferring times. Computer Aided Chemical Engineering, v. 30, p. 477-481, 2012. http://dx.doi.org/10.1016/B978-0-444-59519-5.50096-4

AGUIRRE, A.M.; MÉNDEZ, C.A.; GUTIERREZ, G.; DE PRADA, C. An improvement-based MILP optimization approach to complex AWS scheduling. Computers & Chemical Engineering, v. 47, p. 217-226, 2012. http://dx.doi.org/10.1016/j.compchemeng.2012.06.036

BHUSHAN, S.; KARIMI, I.A. An MILP approach to automated wet-etch station scheduling. Industrial & Engineering Chemistry Research, v. 42, n. 7, p. 1391-1399, 2003. http://dx.doi.org/10.1021/ie020296c

BHUSHAN, S.; KARIMI, I.A., Heuristic algorithms for scheduling an automated wet-etch station. Computers & Chemical Engineering, v. 28, n. 3, p. 363-379, 2004. http://dx.doi.org/10.1016/S0098-1354(03)00192-3

CASTRO, P.M.; AGUIRRE, A.M.; ZEBALLOS, L.J.; MÉNDEZ, C.A., Hybrid mathematical programming discrete-event simulation approach for large-scale scheduling problems. Industrial & Engineering Chemistry Research, v. 50, n. 18, p. 10665-10680, 2011. http://dx.doi.org/10.1021/ie200841a

CASTRO, P.M.; ZEBALLOS, L.J.; MÉNDEZ, C.A. Hybrid time slots sequencing model for a class of scheduling problems. AIChE Journal, v. 58, n. 3, p. 789-800, 2012.

GEIGER, C.E.; KEMPF, K.G.; UZSOY, R. A Tabu search approach to scheduling an automated wet etch station. Journal of Manufacturing Systems, v.16, n. 2, p. 102-116, 1997. http://dx.doi.org/10.1016/S0278-6125(97)85674-9

MÉNDEZ C.A; CERDÁ, J. An MILP Continuous-time framework for short-term scheduling of multipurpose batch processes under different operation strategies. Optimization and Engineering, v. 4, n. 1-2, p. 7-22, 2003. http://dx.doi.org/10.1023/A:1021856229236

NAWAZ, M.; ENSCORE Jr., E.E.; HAM, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, v. 11, p. 91-95, 1983. http://dx.doi.org/10.1016/0305-0483(83)90088-9

NOVAS, J.M.; HENNING, G.P. A comprehensive constraint programming approach for the rolling horizon-based scheduling of automated wet-etch stations. Computers & Chemical Engineering, v. 42, p. 189-205, 2012. http://dx.doi.org/10.1016/j.compchemeng.2012.01.005

PAUL, H.J.; BIERWIRTH, C.; KOPFER, H. A heuristic scheduling procedure for multi-item hoist production lines. International Journal Production Economics v. 105, p. 54-69, 2007. http://dx.doi.org/10.1016/j.ijpe.2005.11.008

PHILLIPS, L.W.; UNGER, P.S. Mathematical programming solution of a hoist scheduling programm. AIIE Transactions, v. 28, n. 2, p. 219-225, 1976. http://dx.doi.org/10.1080/05695557608975070

SHAPIRO, G.W.; NUTTLE, H.L. Hoist scheduling for a PCB electroplating. IIE Transactions, v. 20, n. 2, p. 157-1, 1988. http://dx.doi.org/10.1080/07408178808966165

ZEBALLOS, L.J.; CASTRO, P.M.; MÉNDEZ, C.A. Integrated constraint programming scheduling approach for automated wet-etch stations in semiconductor manufacturing. Ind Eng Chem Res. v. 50, p.1705-1715, 2011. http://dx.doi.org/10.1021/ie1016199