Application and Evaluation of Bee-Based Algorithms in Scheduling: A Case Study on Project Scheduling

Application and Evaluation of Bee-Based Algorithms in Scheduling: A Case Study on Project Scheduling

Ayse Aycim Selam (Marmara University, Turkey) and Ercan Oztemel (Marmara University, Turkey)
DOI: 10.4018/978-1-5225-2944-6.ch002
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Scheduling is a vital element of manufacturing processes and requires optimal solutions under undetermined conditions. Highly dynamic and, complex scheduling problems can be classified as np-hard problems. Finding the optimal solution for multi-variable scheduling problems with polynomial computation times is extremely hard. Scheduling problems of this nature can be solved up to some degree using traditional methodologies. However, intelligent optimization tools, like BBAs, are inspired by the food foraging behavior of honey bees and capable of locating good solutions efficiently. The experiments on some benchmark problems show that BBA outperforms other methods which are used to solve scheduling problems in terms of the speed of optimization and accuracy of the results. This chapter first highlights the use of BBA and its variants for scheduling and provides a classification of scheduling problems with BBA applications. Following this, a step by step example is provided for multi-mode project scheduling problem in order to show how a BBA algorithm can be implemented.
Chapter Preview
Top

Introduction

Scheduling, a complex optimization problem is an area of research that needs improvement using new methods and approaches. Solving this problem, which has a huge number of constraints; within acceptable levels of time and precision is a challenge. Scheduling problems can be solved up to some degree using traditional engineering models, algorithms, heuristics and meta-heuristics. Hence, methods employed by living creatures in order to solve their problems for survival in nature; are inspiring researchers in many different ways which help to develop models for solving daily life problems. Optimization is one of the prominent fields where natural systems are providing foresight to generate acceptable solutions (Pham et al., 2005; Karaboga and Akay 2010).

Various natural systems (social insect colonies) such as bees or bacteria (Escherichia coli bacteria) indicate that very simple individual organisms can create systems which are able to perform highly complex tasks by dynamically interacting with each other and adopting social foraging behavior (Teodorovic et al., 2006; Tang, Nouri, and Motlagh, 2011). In recent years, a noticeable pattern has been observed in the area of academic scheduling where many complex problems were efficiently solved using the principles of meta-heuristics (Teoh, Wibowo, and Ngadiman, 2015). For instance, as an evolutionary computational approach, Passino (2002) is inspired by the foraging behavior of Escherichia coli bacteria in human intestines. Here, the bacterium striving to maximize the energy gained per unit of foraging time is seen as an optimization process (Passino, 2002). Tang, Nouri, and Motlagh, (2011) adapted this approach to the machine cell formation problem.

A recent algorithm based on the interesting breeding behavior such as brood parasitism of certain species of cuckoos combined with the Lévy flight behavior of some birds and fruit flies, is an example of this kind (Yang and Deb, 2009). Cuckoo Search Algorithm is thought to be a new and efficient population-based heuristic evolutionary algorithm for solving optimization problems with the advantages of simple implementation and few control parameters (Nguyen, Vo, and Truong, 2014). It is applied to the problems of hybrid flow shop scheduling (Marichevlam, Prabaharan, and Yang, 2014; Dasgupta and Das, 2015), short-term hydrothermal scheduling (Nguyen, Vo, and Truong, 2014; Nguyen and Vo, 2015; Nguyen and Vo, 2016), multi-objective scheduling (Chandrasekaran and Simon, 2012; Akbari and Rashidi, 2016) and 2-machine robotic cell scheduling (Majumder and Laha, 2016).

Fireflies are creatures which have also affected researchers with their bioluminescence abilities. The flashing light of fireflies attract mating partners (communication) and potential prey, and this light is formulated in such a way that it is associated with the objective function to be optimized (Yang, 2009). The researchers idealized some of the flashing characteristics of fireflies to develop a firefly inspired algorithm to solve optimization problems (Gandomi, Yang and Alavi, 2011; Ritthipakdee et al., 2014).

In another study, by using the navigation method of moths in nature which is called transverse orientation, the moth-flame optimization method is developed (Mirjalili, 2015). This method is also called moth swarm optimization and mimics to the orientation of moths towards moonlight to solve the constrained Optimal Power Flow problem (Mohamed et al., 2017).

Key Terms in this Chapter

Ant Colony Optimization: A probabilistic method that searches for the optimal path that mimics the ants while finding the way from food source to nest.

Swarm Intelligence: The collective behavior of animal colonies who find organized solutions for their survival in nature.

Critical Path: The longest path from start node to end node in a project network. Critical path determines the shortest time that a project can be completed.

Project: A set of activities to accomplish a one-time effort that meets specifications under limited time, and budget.

Scheduling: The methods used to assign resources to a set of activities to be completed under different conditions.

Metaheuristics: A general concept of algorithms which can be applied to different types of optimization problems.

Bee Colony Optimization: A metaheuristic that mimics the food foraging bees in nature.

Complete Chapter List

Search this Book:
Reset