Applying MILP/heuristic algorithms to automated job-shop scheduling problems in aircraft-part manufacturing


  • Adrián Marcelo Aguirre Universidad Nacional del Litoral (UNL-CONICET)
  • Carlos Alberto Méndez Universidad Nacional del Litoral (UNL-CONICET.
  • Álvaro García-Sánchez Escuela Técnica Superior de Ingenieros Industriales (ETSII-UPM),
  • Miguel Ortega-Mier Escuela Técnica Superior de Ingenieros Industriales (ETSII-UPM).


MILP-based algorithm, Automated manufacturing systems, Job-shop scheduling problems, Real-world applications in aircraft-part fabrication pocess


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.   10.13084/2175-8018.v05n10a03

Biografia do Autor

Adrián Marcelo Aguirre, Universidad Nacional del Litoral (UNL-CONICET)


Carlos Alberto Méndez, Universidad Nacional del Litoral (UNL-CONICET.


Álvaro García-Sánchez, Escuela Técnica Superior de Ingenieros Industriales (ETSII-UPM),


Miguel Ortega-Mier, Escuela Técnica Superior de Ingenieros Industriales (ETSII-UPM).



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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

PHILLIPS, L.W.; UNGER, P.S. Mathematical programming solution of a hoist scheduling programm. AIIE Transactions, v. 28, n. 2, p. 219-225, 1976.

SHAPIRO, G.W.; NUTTLE, H.L. Hoist scheduling for a PCB electroplating. IIE Transactions, v. 20, n. 2, p. 157-1, 1988.

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.