Solving Type 2 Simple Assembly Line Balancing Problem through a Direct Ant Colony Optimization Technique

Abstract

An assembly line consists of work stations where specific tasks are carried in such a way that last station gives the complete product. The setup of assembly lines involves high capital investment while day by day competition in market and demands of customer are increasing. Therefore, carefully designed assembly lines as a cost efficient production system are indispensable today. Assembly line balancing (ALB) is an important concept for designing & reconfiguring efficient assembly lines. Simple assembly line balancing Problem (SALBP) deals with an assembly line processing single product. It involves optimal assignment of tasks among workstations with respect to some performance objective subject to precedence constraints. SALBP-2 is a practical type of SALBP which aims to minimize cycle time for a fixed number of workstations for installed assembly lines. SALB-2 belongs to NP-hard problem category. Literature studies show the effectiveness of metaheuristics for finding optimal solution to NP-hard problems in minimum possible time. Most of existing approaches attempt to solve SALBP-2 indirectly through SALBP-1 instances by application of heuristics. In this dissertation, initially a heuristic is proposed to solve SALBP-2 directly. It is tested on a benchmark problem from literature and results proved its effectiveness. Further, to improve the results, a latest metaheuristic approach i.e. ant colony optimization is applied on the proposed heuristic. The objective is to minimize cycle time for a fixed number of workstations. The algorithm starts with pre-determined ant colonies with pre-determined number of ants. Each ant builds solution and assigns tasks to workstations while satisfying precedence constraints. In order to generate feasible solutions, a heuristic factor i.e. longest task from list of available tasks and a pseudorandom proportional rule is deployed by ants during task selection stage. On assigning task to a workstation, each ant applies a local pheromone updating rule. After construction of feasible solutions by ant colony, the quality is measured as per objective function. A global pheromone updating rule is then applied to the best ant tour. The procedure is applied to each ant colony and best so far solution is stored. For testing effectiveness of the proposed procedure, it is applied on small and medium sized problems from literature i.e. 3 data sets with 9 instances. Testing showed that optimal solutions are achieved on application of ant colony optimization. The results strongly suggest that proposed direct ant colony optimization technique is well suited for solving SALBP-2 problems.