Meta-Heuristic Algorithms to Solve Bi-Criteria Parallel Machines Scheduling Problem

Parallel machine scheduling problems are classified as NP-hard problems. The direct solutions for these problems are not available and meta-heuristic algorithms are required to be used to find near-optimal solutions. In this paper, the formulations of multi-objective Artificial Bee Colony algorithm by using combination of weighted objectives, secondary storage for managing possible solutions and Genetic algorithm have been developed and applied to schedule jobs on parallel machines optimizing bi-criteria namely maximum tardiness and weighted flow time. The results obtained indicate that proposed algorithm outperforms other multi-objective algorithms in optimizing bi-criteria scheduling problems on parallel machines. Further, the sequential optimization of bi-criteria using Early Due Date (EDD) followed by Genetic Algorithm (GA) has also been investigated. The efficiencies of the proposed algorithms have been verified by numerical illustrations and statistical tests.