Scheduling job shop associated with multiple routings with genetic and ant colony heuristics

The general job shop problem is one of the well known machine scheduling problems, in which the operation sequence of jobs are fixed that correspond to their optimal process plans and/or resource availability. Scheduling and sequencing problems, in general, are very difficult to solve to optimality and are well known as combinatorial optimisation problems. The existence of multiple job routings makes such problems more cumbersome and complicated. This paper addresses a job shop scheduling problem associated with multiple job routings, which belongs to the class of NP hard problems. To solve such NP-hard problems, metaheuristics have emerged as a promising alternative to the traditional mathematical approaches. Two metaheuristic approaches, a genetic algorithm and an ant colony algorithm are proposed for the optimal allocation of operations to the machines for minimum makespan time criterion. ILOG Solver, a scheduler package, is used to evaluate the performance of the proposed algorithms. The comparison reveals that both the algorithms are capable of providing solutions better than the solution obtained with ILOG Solver.