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.

We investigated a variant of the customer order scheduling problem taking into consideration due dates to minimize the total tardiness. Since the problem under study is NP-hard, we propose an efficient size reduction algorithm (SR). We perform an extensive computational experience and compare our proposition with JPO-20 matheuristic, the best existing algorithm for the problem under study. We use the Relative Deviation Index (RDI) and the Success Rate (SRa) as the statistical indicators for the performance measure. We must emphasize that SR presented the lowest average RDI (around 15.5 %), whereas the JPO-20 presented an average RDI approximately three times higher (around 52.5 %). Furthermore, the proposed SR presented a higher average SRa (around 66.9%), whereas the JPO-20 presented a lower average success (around 25.7%). Our proposal used a lower computational effort, resulting in a reduction for the computation times of approximately 22%. The obtained results point to the superiority of the proposed SR in comparison with the JPO-20.