Application of Heuristics for Parallel Flow Line Scheduling Problem

Abstract

The flowshop scheduling problems are solved by heuristic methods in view of the NP-hardness. This paper proposes to explore the near optimal sequences based on heuristic algorithms with the objective to minimize Makespan. Metaheuristic based methods are used in scheduling problems where exact methods are not sufficient to provide a solution. Swarm intelligence systems are generally made up of a population of naturally existing phenomena or agents and in this paper the consideration is the foraging behavior of honey bees. Such swarm based algorithms are used to duplicate the methods of nature to conduct a search towards the near optimal solution. This paper presents an application of parallel flow line scheduling using metaheuristic method of swarm intelligence based on bee colony algorithm. The algorithm used is to minimize the Makespan, which is one of the important requirements to reduce the overall lead time in manufacturing. The results of this algorithm has been compared with the results of other comparable research algorithms and verified. Computational results show that GA based algorithm outperforms ABC in all instances of the chosen problem sets. In order to measure the efficiency of the solution methods, the execution time (sec) taken by each solution method to obtain solution to an instance of a problem was computed. The mean value of execution time over the hundred problem instances solved under various metaheuristics shows that for the small size problems the computation time is same for all the three algorithms and when the problem size increases the computation time of algorithms also increases and vary exponentially and from the experiments it is inferred that the GA algorithm is faster than ABC. The application of this algorithm discussed can be applied over a number of applications related to manufacturing in parallel assembly lines like packaging industry, manufacturing industry like paper industry, plastics injection molding industry etc.