An investigation on the application of metaheuristics to job shop scheduling problems with multiple objectives

Abstract

Keywords: Job Shop Scheduling, Flow Shop Scheduling, Multi-Objective Scheduling, Multi-Objective Metaheuristics, Pareto Optimization, Makespan and Mean Flow Time. Real life scheduling problems are multi-objective in nature. Job shop scheduling problem is NP hard and is one of the least tractable. In spite of large number of publications available for the job shop scheduling problems with single objective measure, very little research work has been done to solve multi-objective JSSPs. This research aims at identifying non-dominated fronts for job shop scheduling problems with simultaneous consideration of minimizing the makespan and the mean flow time. Simultaneous consideration of minimizing the makespan and the mean flow time effectively reduces the scheduling cost. The original intention of this research was to develop a multi-objective metaheuristic for job-shop-schedule optimization. This study has converged towards development of two different types of metaheuristics. They are: Pareto local search genetic algorithm (PLSGA) and Pareto archived simulated annealing (PASA) algorithm. Investigation on the application of metaheuristics, by combining intelligently different concepts for exploring and exploiting the solution space, to solve JSSPs with multiple objectives is carried out in this research. In developing PLSGA, a new non-domination ranking procedure is used to assign non-domination rank to individuals in the population, and a crowding comparison operator is proposed to maintain diversity among the members of non-dominated front. In PASA, Pareto dominance and a simple aggregating 'function are used to accept the candidate solution. Segment random insertion (SRI) perturbation scheme is used to generate a set of neighbourhood solutions to the current solution. Implementations of re-annealing and re-start procedures have also been employed for better search. The proposed PLSGA and PASA frameworks are general purpose optimization algorithms useful to solve other scheduling problems also with less effort. The flexibility of the PASA algorithm is demonstrated by solving popular benchmark flow shop scheduling problems (FSPs). Performance assessment in multi-objective optimization is very difficult because quality is not represented by one single best solution, but rather by a set of nondominated solutions. In this research, two simple quality measures are used to assess the performance of multi-objective approaches. Performance assessment of the proposed multi-objective algorithms is done by solving a set of benchmark JSSPs proposed in the literature. Proposed algorithms are also evaluated by comparing their performance with existing multi-objective optimization algorithms. The Pareto archived simulated annealing algorithm has emerged as a better search model.