Robust meta-heuristics implementation for unrelated parallel machines scheduling problem with rework processes and machine eligibility restrictions

• We studied scheduling unrelated parallel machines with makespan criterion.
• The job release dates, rework processes and machine eligibility are considered.
• We developed a new optimization model to formulate the problem.
• Robust meta-heuristic algorithms are implemented to obtain optimal solutions.

This paper dealt with an unrelated parallel machines scheduling problem with machine eligibility restrictions, sequence and machine dependent setup times and possibility of producing imperfect items. Rework processes are considered to improve and regain defective items to an acceptable quality level. In order to formulate this problem, a new optimization model is developed and makespan is employed as the objective function. Since the problem is strongly NP-hard, exact algorithms are inefficient for medium and large-sized problems. Thus, some meta-heuristic algorithms including genetic algorithm (GA) and bees algorithms (BA1 and BA2) are implemented to find optimal/near optimal solutions. To achieve better robustness of algorithms, parameter setting process is performed for all three mentioned algorithms in each one of small, medium and large scales, separately. For small size yet complex problems, the results from these algorithms are compared to the optimal solutions. The result obtained in all of these problems is that the algorithms can find solutions as good as exact algorithms but in drastically shorter computational time.