2019 | vol. 67 | nr. 2 | art. 14

A Makespan Minimization API Algorithm for Flow Shop Scheduling

Fatima Zohra BOUMEDIENE, Yamina HOUBAD, Hakim Nadhir BESSENOUCI, Ahmed HASSAM, Latéfa GHOMRI
Abstract
This paper presents and describes the adaptation and the implementation of the Pachycondyla apicalis based metaheuristic to solve the Flow Shop Scheduling Problem which is among the most important well known combinatorial optimization problems in order to minimize as an objective function the makespan. The considered optimization metaheuristic proposed to solve the problem at hand is an ant based metaheuristic inspired from the foraging behaviour of a population of primitive ants named the Pachycondyla apicalis. The powerfulness of the Pachycondyla apicalis based algorithm is that it can be easily designed, described and implemented. In this paper, a number of experiments and simulations are carried out on a set of classes generated on a production system containing thirty machines and different numbers of jobs with five instances and different processing time in each class. Since the metaheuristics effectiveness could strongly depend on the choice of its parameters, a sensitivity analysis is proposed to improve the quality of obtained results. The sensitivity analysis is performed according to two parameters of the algorithm which are the number of hunting sites and the number of consecutive failures encountered on the same explored hunting site. This analysis is judged by the makespan obtained values. Computational results show that the considered algorithm is sensitive to the variation of the number of hunting sites and the number of consecutive failures encountered on the same hunting site variations. Consequently, the algorithm is able to provide competitive results in terms of solutions quality if a good choice of its parameters is done.
Keywords: Scheduling, Flow Shop, Pachycondyla apicalis based algorithm, Ant system, optimization, metaheuristic
To cite this article: BOUMEDIENE F.Z., HOUBAD Y., BESSENOUCI H. N., HASSAM A., GHOMRI L., “A Makespan Minimization API Algorithm for Flow Shop Scheduling”, in Electrotehnica, Electronica, Automatica (EEA), 2019, vol. 67, no. 2, pp. 123-129, ISSN 1582-5175.

 

Download