Journal of Applied Mathematics · 2020 · 41 citations · 46 references
Natural SciencesComputer ScienceIndustrial EngineeringAlgorithmsOptimizationSchedulingCombinatorial OptimizationFlow Shop SchedulingHeuristic SearchInteger ProgrammingMakespan MinimizationMetaheuristic OptimizationFlow ShopGreedy HeuristicsHeuristic AlgorithmsHeuristic ApproachInteger Linear ProgrammingLocal SearchMixed-integer Linear ProgrammingMixed-integer Programming
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.
46
The Complexity of Flowshop and Jobshop Scheduling
M. R. Garey, David Johnson, Ravi Sethi · Mathematics of Operations Research · 1976 · 2.6K citations
A genetic algorithm for flowshop sequencing
Colin R. Reeves · Computers & Operations Research · 1995 · 872 citations