Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time

In this paper, we study the resolution of a permutation flow shop problem with sequence-independent setup time. The objective is to minimize the maximum of job completion time, also called the makespan. In this contribution, we propose three methods of resolution, a mixed-integer linear programming...

Full description

Saved in:
Bibliographic Details
Published in:Journal of applied mathematics 2020, Vol.2020 (2020), p.1-11
Main Authors: Belabid, Jabrane, Allali, Karam, Aqil, Said
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Comparative studies
Completion time
Computer simulation
Greedy algorithms
Heuristic
Heuristic methods
Integer programming
Iterative methods
Job shop scheduling
Job shops
Linear programming
Neighborhoods
Optimization algorithms
Permutations
Production scheduling
Researchers
Search algorithms
Sequential scheduling
Setup times
Water waves
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we study the resolution of a permutation flow shop problem with sequence-independent setup time. The objective is to minimize the maximum of job completion time, also called the makespan. In this contribution, we propose three methods of resolution, a mixed-integer linear programming (MILP) model; two heuristics, the first based on Johnson’s rule and the second based on the NEH algorithm; and finally two metaheuristics, the iterative local search algorithm and the iterated greedy algorithm. A set of test problems is simulated numerically to validate the effectiveness of our resolution approaches. For relatively small-size problems, it has been revealed that the adapted NEH heuristic has the best performance than that of the Johnson-based heuristic. For the relatively medium and large problems, the comparative study between the two metaheuristics based on the exploration of the neighborhood shows that the iterated greedy algorithm records the best performances.
ISSN:1110-757X
1687-0042
DOI:10.1155/2020/7132469