On the Two Machine Permutation Flowshop Scheduling Problems Using Variable Neighborhood Search Algorithms

Muthanna Journal of Pure Sciences – MJPS

VOL.(5), NO.(1), 2018

T. S. Abdul – Razaq1, H. M. Motair2*

1Dept. of Mathematics, College of Science, University of Al-Mustansiriya
2 Dep. of Mathematics, Open Educational College, Al- Qadisiya, Ministry of Education

DOI: 10.52113/2/05.01.2018/36-47

Abstract

This paper considers the two machine permutation flow shop scheduling problem PFSSP. We study
some special cases of the problem 2||( , Σ , , Σ ) (P). In the first one, the special cases to find the exact non dominated solutions for problem () are based on the relation between processing times , and the due dates on machine A and machine B, ( = 1,2, … , ). In the second one, the special cases are based on the lexicographical order minimization to solve three problems, in each one the primary objective function is maximum completion time ( ), while the secondary objective function is one of the objective functions: total completion times (Σ ), maximum tardiness ( ) and total tardiness (Σ ), the resulting problems are (P1), (P2), (P3). We propose three algorithms: Variable neighborhood simulated annealing(VNSA), Variable neighborhood descent method(VNDM) and Variable neighborhood with modefied NEH algorithm(VNMNEH).
The comparison results show the efficiency of the proposed algorithms. All algorithmes were coded in Matlab programe.

Keywords: Permutation flow shop, non-dominated solutions, lexicographical order, variable neighborhood, simulated annealing, descend method.