This paper aims at presenting an algorithm for solving the blocking flow shop problem with sequence dependent setup times (BFSP-SDST) with minimization of the makespan. In order to do so, we propose an adapted Bounded Dynamic Programming (BDP-SN) algorithm as solution method, since the problem itself does not present a significant number of sources in the state-of-art references and also because Dynamic Programming and its variants have been resurfacing in the flowshop literature. Therefore, we apply the modified method to two sets of problems and compare the results computationally and statistically for instances with a MILP and a B&B method for at most 20 jobs and 20 machines. The results show that BDP-SN is promising and outperforms both MILP and B&B within the established time limit. In addition, some suggestions are made in order to improve the method and employ it in parallel research regarding other branches of machine scheduling.

This study contributes to the hybrid flow shop due to a lack of consideration of characteristics existing in real-world problems. Prior studies are neglecting identical machines, explicit and sequence-dependent setup times, and machine blocking. We propose a hybrid genetic algorithm to solve the problem. Furthermore, we also propose a mixed-integer linear programming formulation. We note a predominance of the mathematical model for small instances, with five jobs and three machines because of how fast there is convergence. The objective function adopted is to minimize the makespan, and relative deviation is used as a performance criterion. Our proposal incorporates two metaheuristics in this process: a genetic algorithm to generate sequences (the flow shop subproblem) and a GRASP to allocate the jobs in the machines (the parallel machines subproblem). The extensive computational experience carried out shows that the proposed hybrid genetic algorithm is a promising procedure to solve large-sized instances.

The integration between production and distribution to minimize total elapsed time is an important issue for industries that produce products with a short lifespan. However, the literature focus on production environments with a single stage. This paper enhances the complexity of the production system of an integrated production and distribution system by considering flowshop environment decisions integrated with a vehicle routing problem decision. In this case, each order is produced in a permutation flowshop subsystem and then shipped to its destination by a capacitated vehicle, and the objective is to sequence these orders to minimize the makespan of the schedule. This paper uses two approaches to address this integrated problem: a mixed-integer formulation and an Iterated Greedy algorithm. The experimentation shows that the Iterated Greedy algorithm yields results with a 0.02% deviation from the optimal for problems with five jobs, and is a viable option to be used in practical cases due to its short computational time.