《2016 Scheduling jobs on a k-stage flexible flow-shop》.pdf

Ann Oper Res (2008) 164: 29–40 DOI 10.1007/s10479-007-0257-2 Scheduling jobs on a k-stage flexible flow-shop Carlos D. Paternina-Arboleda · Jairo R. Montoya-Torres · Milton J. Acero-Dominguez · Maria C. Herrera-Hernandez Published online: 9 November 2007 © Springer Science+Business Media, LLC 2007 Abstract We consider the problem of makespan minimization on a flexible flow shop with k stages and ms machines at any stage. We propose a heuristic algorithm based on the identi- fication and exploitation of the bottleneck stage, which is simple to use and to understand by practitioners. A computational experiment is conducted to evaluate the performance of the proposed method. The study shows that our method is, in average, comparable with other bottleneck-based algorithms, but with smaller variance, and that it requires less computa- tional effort. Keywords Flexible flow-shop · Heuristic · Computational experiments 1 Introduction We consider the flexible flow shop (FFS) machine environment with k stages in series; at stage s, s = 1, . . . , k, there are ms identical machines in parallel. There is unlimited inter- mediate storage between two successive stages. Job j, j = 1, . . . , n has to be processed at each stage on any one machine. The processing times of job j at the various stages are p1j , p2j , . . . , pkj . The goal is to find a schedule without preemption that minimizes the max- imum completion time of all jobs (makespan). The flexible flow shop scheduling problem C.D. Paternina-Arboleda · M.J. Acero-Dominguez · M.C. Herrera-Hernandez Departamento de Ingeniería Industrial, Universidad del Norte, Km 5 via Puerto Colombia, Barranquilla, Colombia C.D. Paternina-Arboleda e-mail: cpaterni@.co J.R. Montoya-Torres ( ) Escuela Internacional de Ciencias Económicas y Administrativas, Universidad de La Sabana, Km. 21 Autopista Norte de Bogotá, D.C., Chia, Colombia e-mail: jrmontoy@ J.R. Montoya-Torres e-mai