Search results

The purpose of this paper is to present a hybrid meta-heuristic based on genetic algorithms (GAs), simulated annealing, variable neighborhood descent and path relinking for solving the variant of the unrelated parallel machine scheduling problem considering sequence-dependent setup times.

The authors carried out computational experiments on literature problem instances proposed by Vallada and Ruiz (2011) and Arnaout et al. (2010) to test the performance of the proposed meta-heuristic. The objective function adopted was makespan minimization, and the authors used relative deviation, average and population standard deviation as performance criteria.

The results indicate the competitivity of the proposed approach and its superiority in comparison with several other algorithms. In small instances proposed by Vallada and Ruiz (2011) and on small and large instances proposed by Arnaout et al. (2010), the proposed approach presented the best results in most tested problem instances.

In small instances proposed by Vallada and Ruiz (2011) and on small and large instances proposed by Arnaout et al. (2010), the proposed approach presented the best results in most tested problem instances.

The proposed approach presented high-quality results, with an innovative hybridization of a GA and neighborhood search algorithms, tested in diverse instances of literature. Furthermore, the case study demonstrated that the proposed approach is recommended for solving real-world problems.

This study aims to address the hybrid open shop problem (HOSP) with respect to the minimization of the overall finishing time or makespan. In the HOSP, we have to process n jobs in stages without preemption. Each job must be processed once in every stage, there is a set of m_k identical machines in stage k and the production flow is immaterial.

Computational experiments carried out on a set of randomly generated instances showed that the minimal idleness heuristic (MIH) priority rule outperforms the longest processing time (LPT) rule proposed in the literature and the other proposed constructive methods on most instances.

The proposed mathematical model outperformed the existing model in the literature with respect to computing time, for small-sized instances, and solution quality within a time limit, for medium- and large-sized instances. The authors’ hybrid iterated local search (ILS) improved the solutions of the MIH rule, drastically outperforming the models on large-sized instances with respect to solution quality.

The authors formalize the HOSP, as well as argue its NP-hardness, and propose a mixed integer linear programming model to solve it. The authors propose several priority rules – constructive heuristics based on priority measures – for finding feasible solutions for the problem, consisting of adaptations of classical priority rules for scheduling problems. The authors also propose a hybrid ILS for improving the priority rules solutions.