Open AccessExact and Hybrid Metaheuristic Algorithms to Solve Bi-Objective Permutation Flow Shop Scheduling Problem
Author(s) -
Hafed M. Motair
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1818/1/012042
Subject(s) - tardiness , job shop scheduling , flow shop scheduling , variable neighborhood search , metaheuristic , mathematical optimization , simulated annealing , computer science , permutation (music) , algorithm , branch and bound , tabu search , upper and lower bounds , scheduling (production processes) , mathematics , schedule , mathematical analysis , physics , acoustics , operating system
In this paper, we consider 2-machine permutation flow shop scheduling problem with bi-objective of minimizing the makespan ( C max ) and maximum tardiness ( T max ). The aim is to minimize the two objective functions lexicographicaly, which is minimize maximum tardiness subject to that the makespan is optimal. We introduce a Branch and bound algorithm with two dominance conditions to find the optimal solution of the problem for job sequence with up to 14 jobs. For moderate and large sized problems we apply a simulated annealing algorithm to develop a metaheuristic algorithme based on the first level branch and bound and variable neighborhood search. To compare with the original algorithm, numerical experiments provided, the rusults shows the efficiency of the dominance conditions also the efficiency of proposed modification of the original metaheuristic algorithm.