Multiprocessor Scheduling Based on Evolutionary Technique for Solving Permutation Flow Shop Problem

Abstract

Multiprocessor scheduling is one of the thrust areas in the field of computational science. There are various traditional scheduling techniques exist for the allocation and processing of jobs. But the performance of these techniques reduce in terms of makespan and waiting time when a large number of jobs are allocated to multiprocessors. In this paper, a new stochastic evolutionary technique is proposed based on the Genetic Algorithm and Pareto optimality. The new technique is implemented in a high-performance computing (HPC) environment using a Message passing interface (MPI) to resolve the permutation flow shop scheduling problem. Pareto optimality technique is used for sample distribution and the basis of the decision to select the lower bound of the makespan, instead of selecting the makespan directly for the best solution. The performance and quality evaluation of proposed techniques (GA_PO_MPI, GA) are compared with traditional techniques (FCFS, FCFS_MPI, TSAB, TSGP, TSGW) on the basis of Relative Percentage Deviation (RPD), Computational Time (CT) and Average Waiting Time and found satisfactory.

Keywords

• Average relative percentage deviation (RPD)
• computational time (CT)
• flowshop
• GA_PO_MPI
• HPC
• MPI