Article Preview
Top1. Introduction
The parallel machine scheduling problem (PMSP) is normally classified as a complex combinatorial optimization problem, in which a set of n jobs (1,2,3,….,n) are to be processed on m available parallel machines (1,2,3,….,m). It is a generalization of single machine problem. In many engineering and manufacturing systems, jobs go through a number of stages in each of which there are several machines working in parallel. In recent years, research has been undertaken on the concept of bi-criteria; a subset of multi-objective optimization on parallel machines scheduling problems in developing various optimization and approximation algorithms. Multi-objective optimization is very important not only because of a multi-objective nature of most real world problems, but also because there are still many open questions in this area. In real life situations, we often find jobs with different processing time, due date, weightage, and tardiness. Therefore, an objective of minimizing weighted flow time (WFT) and maximum tardiness (Tmax) is significant with respect to real life situations in manufacturing and engineering world.
One of the recent works in this field is based on heuristic that first optimizes maximum tardiness (Tmax) and then weighted flow time (WFT) without violating primary criteria of Tmax (Nailwal, Gupta, Sharma, & Wu, 2015; Sharma, Gupta, & Sharma, 2013). But with the increase in problem size, the heuristic gets compromised. In past few years, researchers have been fascinated by meta-heuristic algorithms to solve complex combinatorial problems (Blum & Roli, 2003). Two major components of any meta-heuristic algorithms are: Intensification and diversification. The good combination of these two major components ensures the getting of global optimality. For scheduling problems, the spectacular increase in the size of a search space and the need of real-time solutions motivate the research ideas to solve scheduling problems using nature-inspired Meta-heuristic techniques.
Nature has always been a source of inspirations for all of us. Inspired by social insects like ants, bees or termite etc, research in the past decade has led to some captivating progress in the field of a natural algorithm. Still being young with very amazing results; nature-inspired algorithm has explored new areas of applications with more opportunities in computing. Many engineering optimization problems such as selection of partner in green supply chain problem (Yeh & Chuang, 2011) and design optimization of composite structures (Omkar, Senthilnath, Khandelwal, Naik, & Gopalakrishnan, 2011) are solved by nature-inspired algorithms. Motivated by these examples, various formulations of Multi-Objective Artificial Bee Colony algorithms have been used for optimizing the problem under consideration.
The first algorithm is based on sequential application of heuristic to find maximum tardiness (Tmax) followed by Genetic Algorithm (GA) to find minimum Weighted Flow Time (WFT) without violating maximum tardiness (Tmax). GA is based on Darwin’s theory of survival of fittest (Golberg, 1989). It is very helpful in solving problems having search spaces with gaps and noise. In case of job scheduling, all combinations of Tmax and WFT are not optimized and there are gaps in the solution space. To overcome these gaps in the solution space, GA is very much applicable here.
In second algorithm, Multi-objective Artificial Bee Colony algorithm (MOABC) has been used by taking weighted sum of bi-criteria namely Tmax and WFT.
The algorithms discussed above have a serious shortcoming. They return the single objective and are highly dependent on the weights. At the same time allocation of weights to the individual objective is difficult. In case of random selection of weights, the output is highly unpredictable. So, the use of Pareto optimization (K Deb, 2014) (resulting in solutions in the form of Pareto front) for optimization of job schedule using ABC has been investigated in third algorithm. In order to store this Pareto front, an auxiliary archive and hyper-cubes are used to maintain and select best solutions required for each iterations of the algorithm. The algorithm is further appended with GA to improve its efficiency. The resulting algorithm is named MOABCGA.