A Bi-Criteria Hybrid Grey Wolf Approach for Parallel Machine Job Scheduling

A Bi-Criteria Hybrid Grey Wolf Approach for Parallel Machine Job Scheduling

Kawal Jeet (Department of Computer Science, D.A.V. College, Jalandhar, India) and Renu Dhir (Department of Computer Science and Engineering, Dr. B.R. Ambedkar National Institute of Technology, Jalandhar, India)
Copyright: © 2017 |Pages: 23
DOI: 10.4018/IJAMC.2017040104
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Nature-inspired algorithms are becoming popular due to their ability to solve complex optimization and engineering problems. Grey Wolf algorithm is one of the recent nature-inspired algorithms that have obtained inspiration from leadership hierarchy and hunting mechanisms of grey wolves. In this paper, four formulations of multi-objective grey wolf algorithm have been developed by using combination of weighted objectives, use of secondary storage for managing possible solutions and use of Genetic Algorithm (GA). These formulations are applied for jobs scheduling on parallel machines while taking care of bi-criteria namely maximum tardiness and weighted flow time. It has been empirically verified that GA based multi-objective Grey Wolf algorithms leads to better results as compared to their counterparts. Also the use of combination of secondary storage and GA further improves the resulting schedule. The proposed algorithms are compared to some of the existing algorithms, and empirically found to be better. The results are validated by numerical illustrations and statistical tests.
Article Preview

1. Introduction

Optimization is mathematical problem that has been encountered ever since in all engineering disciplines. Literally it is described as the process of finding the best possible solution. Wide variety of important optimization problems is faced by researchers and engineers and so it has observed inclination as an active research topic (Fister, Yang, Fister, Brest, & Fister, 2013). Real-world engineering optimization problems are observed to be challenging to solve, and most of them emerge as NP-hard problems. Meta-heuristics are the techniques that have the ability to handle such NP-hard problems (Aguiar e Oliveira Junior, 2016). The main factor for the success of any meta-heuristic is to find the appropriate balance between the diversity of the solution and the computational efforts required to find the solution. Ideally, a meta-heuristic is desired to obtain the global best solution with the maximum speed. Nature-inspired algorithms are most popular met-heuristic algorithms observed these days.

1.1. Nature-Inspired Algorithms

Nature has always been a source of inspiration for many researchers. Nowadays, solution to most of the problems is nature-inspired (Yang, 2010). The real beauty of nature-inspired algorithms lies in the fact that these algorithms inculcate their sole inspiration from nature. These algorithms have the capacity to describe and resolve complex relationships from internally very simple initial conditions and rules with little or no knowledge of the search space.

Researchers try to learn from nature by mimicking the successful characteristics of complex systems in nature. Nature-inspired algorithm is a relatively new area with a short history at this early stage of development. Even then as compared to traditional and well-established technique these have still proved their great potential, flexibility and efficiency as well as ever-increasing and wide variety of applications. The theme behind the execution of these algorithms is simple even then the results are amazing and motivating. Nature is our best teacher forever and its capabilities are enormous and mysterious. That is why the researchers these days are trying to mimic nature in technology. Nature-inspired algorithms have an enormous computational intelligence and capabilities and is observing diverse applications ranging from routing in wireless sensor networks (Karaboga et al. 2012), bi-objective turning restrictive design problem (Long et al. 2014), multistage hybrid flow shop scheduling (Marichelvam et al. 2014), GSM networks (Alba, García-Nieto, Taheri, & Zomaya, 2008), data mining (Martens, Baesens, & Fawcett, 2011), job scheduling (Agarwal, Tiwari, & Mukherjee, 2007) etc. A vast literature is available to justify the successful application of nature-inspired algorithms in solving wide variety of problems.

In this paper, scheduling of n jobs (non- preemptively) on m parallel unattended machines taking into consideration criteria namely maximum tardiness (Tmax) and Weighted Flow Time (WFT) is formulated as optimization problem that is resolved by using nature-inspired grey wolf algorithms.

The prime contributions of this research work are listed below.

Use of Grey Wolf algorithm as multi-objective optimization technique using weighted aggregation of criteria while scheduling jobs on parallel machines.

Analyzing the impact of appending Genetic Algorithm (GA) to multi-objective Grey Wolf algorithm.

Application of Grey Wolf algorithm as multi-objective optimization technique using auxiliary archive for managing Pareto front and use of this approach for scheduling jobs on parallel machines.

Comparison of hybrids of Grey wolf algorithms to that of Multi-Objective Genetic Algorithm (MOGA), Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and Multi-objective Particle Swarm Optimization (MOPSO) algorithms and hybrids of multi-objective Black Hole algorithm taking into consideration scheduling of jobs on parallel machines.

The rest of paper is organized as follows. Section 2 provides brief description of literature related to the field of application of nature-inspired algorithms to solve problem of job scheduling on parallel machines. Section 3 describes the problem formulation along with the objective criteria to be optimized. In Section 4, the proposed multi-objective Grey Wolf algorithms and its hybrids are discussed and compared to existing hybrids of Black Hole algorithm. Section 5 explains the experimental setup and criteria to be used for assessing the credibility of results. This section empirically and statistically investigates the results of scheduling of randomly generated samples. Section 6 addresses the threats to the validity of the present research work. Section 7 concludes the work by describing some future recommendations.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing