Published Oct 27, 2008

Google Scholar
Search GoogleScholar

Fabián Vargas-Nieto

Jairo Rafael Montoya-Torres



This paper considers the problem of production scheduling in a real-life manufacturing plant belonging to the apparel industry. The problem is modeled as a two-stage flexible flow shop, with minimization of both makespan and number of tardy jobs. For this new scheduling problem, we propose a bi-objective evolutionary algorithm. A set of experiments is performed using real data from the company’s database. Experimental results show the relevance of the proposed procedure in terms of performance metrics, as opposed to the current manual scheduling procedure as well as against available commercial schedulers. The procedure was actually implemented as the scheduler procedure at the company. Such results also illustrate the improvement in key performance metrics of the production line.


Industrias manufactureras-Automatización, programación de la producción, algoritmo evolucionista.Manufacturing industries-Automation, production scheduling, Evolutionary algorithms

ACERO, M. J. R.; MONTOYA-TORRES, C. D. and PATERNINA-ARBOLEDA C. Scheduling jobs on a k–stage flexible flow shop. En OULAMARA, A. and PORTMAN, M. C. (eds.). Proceedings of the Ninth International Workshop on Project Management and Scheduling (PMS2004), April 26-28. Nancy, France: EURO Working Group on Project Management and Scheduling, 2004, pp. 242-245.
ALLAOUI, H. and ARTIBA, A. Scheduling two-stage hybrid flow shop with availability constraints. Computer & Operation Research. 2006, núm. 33, pp. 1399-1419.
AZIZOGLU, M.; CAKMAK, E. and KONDAKCI, S. A flexible flowshop problem with total flow time minimization. European Journal of Operational Research. 2001, núm. 132, pp. 528-538.
BERTEL, S. and BILLAUT, J. C. A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation. European Journal of Operational Research. 2004, núm 159, pp. 651-662.
BOTTA-GENOULAZ, V. Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness. International Journal of Production Economic. 2000, núm. 64, pp. 101-111.
BRAH, S. A. and HUNSUCKER, J. L. Branch and Bound algorithm for the flow shop with multiple processors. European Journal of Operation Research. 1991, núm. 51, pp. 88-99.
CHEN, B. Scheduling multiprocessor flowshops. En Advances in Optimization and Approximation. Kluwer: Dordrecht, 1994.
—. Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. Journal of the Operational Research Society. 1995, núm. 46, pp. 234-244.
COLLETE, Y. and SIARRY, P. Multiobjective optimization: principles and case studies. New York: Springer Verlag, 2004.
DESSOUKY, M.; DESSOUKY, M. and VERMA, S. Flowshop scheduling with identical Jobs and uniform parallel machines. European Journal of Operational Research. 1998, núm. 109, pp. 620-631.
DJELLAB, H. and DJELLAB, K. Preemptive hybrid flowshop scheduling problem of Interval orders. European Journal of Operational Research. 2002, núm. 137, pp. 37-49.
EHRGOTT, M. and GANDIBLEUX, X. Multiple criteria optimization: state of the art annotated bibliographic surveys. Springer: Verlarg, 2002.
GUINET, A. and SOLOMON, M. Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time. International Journal of Production Research. 1996, núm. 34, pp. 1643-1654.
GUPTA, J. Two stage hybrid flow shop scheduling problem. Journal of the Operations Research Society. 1988, núm. 38, pp. 359-364.
HAOUARI, M. and M’HALLAH, R. Heuristic algorithms for the two-stage hybrid flowshop problem. Operations Research Letters. 1997, núm. 21, pp. 43-53.
JIN, Z.; YANG, Z. and ITO, T. Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem. International Journal of Production Economics. 2006, núm. 100, pp. 322-334.
LEE, C. Y. and VAIRAKTARAKIS, G. Minimizing makespan in hybrid flowshops. Operations Research Letter. 1994, núm. 16, pp. 149-158.
LINN, R. and ZHANG, W. Hybrid flow shop scheduling: A survey. Computers and Industrial Engineering. 1999, núm. 37, pp. 57-61.
MORITA, H. and SHIO, N. Hybrid branch and bound method with genetic algorithm for flexible flowshop scheduling problem. JSME International Journal Series C. 2005, vol. 48, pp. 46-52.
MOURSLI, O. and POCHET, Y. A branch and bound algorithm for the hybrid flow shop. International Journal of Production Economics. 2000, núm. 64, pp. 113-125.
PINEDO, M. Scheduling: theory, algorithms, and systems. New Jersey: Prentice-Hall-Englewood Cliffs, 2002.
PORTMANN, M. C.; VIGNIER, A.; DARDILHAC, D. and DEZALAY, D. Branch and bound crossed with GA to solve hybrid flowshops. European Journal of Operational Research. 1998, núm. 107, pp. 389-400.
RIANE, F.; ARTIBA, A. and ELMAGHRABY, S. E. A hybrid three-stage flexible flowshop problem: Efficient heuristics to minimize makespan. European Journal of Operational Research. 1998, núm. 109, pp. 321-329.
RUIZ, R. and MAROTO, C. A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research. 2006, núm. 169, pp. 781-800.
SAWIK, T. An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers. Mathematical and Computer Modelling. 2002, vol. 36, núms. 4-5, pp. 461-471.
SOEWANDI, H. and ELMAGHRABY, S. E. Sequencing three-stage flexible flowshops with identical machines to minimize makespan. IIE Transactions. 2001, núm. 33, pp. 985-993.
SRISKANDARAJAH, C. and WAGNEUR, E. Hierarchical control of the two processor flowshop with state dependent processing times: Complexity analysis and approximate algorithms. INFOR, Canadian Journal of Information Systems and Operational Research.
1991, núm. 29, pp. 193-205.
TANG, L.; XUAN, H. and LIU, J. A new Lagrangian relaxation algorithm for hybrid flowshop
scheduling to minimize total weighted completion time. Computers & Operations Research.
2006, núm. 33, pp. 3344-3359.
T’KINDT, V. and BILLAUT, J. C. Multicriteria Scheduling: Theory, models and algorithms. 2a. ed.
Springer: Verlag, 2006.
VARGAS-NIETO, F. Diseño e implementación de un modelo de programación de operaciones biobjetivo
basado en algoritmos evolutivos aplicado a la industria de marquillas estampadas por transferencia
térmica. Trabajo de grado de Maestría en Ingeniería Industrial. Barranquilla: Universidad
del Norte, 2007.
VARGAS-NIETO, F. and MONTOYA-TORRES, J. R. Design and implementation of a biobjective
EA-based scheduling strategy: Case study in thermal-printed label manufacturing.
Proceedings of the International Industrial Simulation Conference (ISC-2007).
Delft: The Netherlands, 2007a, pp. 219-222.
—. Scheduling a thermal-printed label manufacturing plant using an evolutionary algorithm.
Proceedings of the 19th International Conference on Production Research (ICPR-19). [CD-ROM].
Valparaiso: Chile, 2007b.
VIGNIER, A.; COMMANDEUR, P. and PROUST, C. New lower bound for the hybrid
flowshop scheduling problem. Emerging Technologies and Factory Automation Proceedings,
1997. ETFA ’97, 1997 6th International Conference on, 9-12 de septiembre de 1997, Los
Angeles, pp. 446-451.
XUAN, H. and TANG, L. Scheduling a hybrid flowshop with batch production at the last
stage. Computers & Operations Research. 2007, núm. 34, pp. 2718-2733.
How to Cite
Vargas-Nieto, F., & Montoya-Torres, J. R. (2008). Implementing a scheduling procedure based on evolutionary algorithms for the production of hot-stamped labels. Ingenieria Y Universidad, 12(2). Retrieved from