Marriage in Honeybee Optimization to Scheduling Problems

Marriage in Honeybee Optimization to Scheduling Problems

Pedro Palominos (University of Santiago of Chile, Chile), Victor Parada (University of Santiago of Chile, Chile), Gustavo Gatica (University of Santiago of Chile, Chile) and Andrés Véjar (Université de Nancy, France)
DOI: 10.4018/978-1-61350-086-6.ch008
OnDemand PDF Download:
$37.50

Abstract

The biological inspired optimization techniques have proven to be powerful tools for solving scheduling problems. Marriage in Honeybee Optimization is a recent biological technique that attempts to emulate the social behavior in a bee colony and although has been applied to only a limited number of problems, it has delivered promising results. By means of this technique in this chapter the authors explore the solution space of scheduling problems by identifying an appropriate representation for each studied case. Two cases were considered: the minimization of earliness-tardiness penalties in a single machine scheduling and the permutation flow shop problem. The performance was evaluated for the first case with 280 instances from the literature. The technique performed quite well for a wide range of instances and achieved an average improvement of 1.4% for all instances. They obtained better solutions than the available upper bound for 141 instances. In the second case, they achieved an average error of 3.5% for the set of 120 test instances.
Chapter Preview
Top

Introduction

Methods for solving optimization problems related to productive, administrative, or logistic processes have become particularly important in the globalized world, where intensified competition has made optimization necessary for the survival of all types of organizations. Modeling the scheduling problems that arise in production and logistics management can be quite complex. For example, a manufacturing company may need to determine the order in which machines should process jobs. Assuming that the Master Production Schedule already exits, the start and end times for the production operations must be set based on the available capacity. These kinds of problems belong to the NP-hard class (Garey & Johnson, 1979) and have been studied extensively by Pinedo(2008).

Swarm Intelligence (SI) is an area of artificial intelligence that focuses on modeling the behaviors of social insects like ants and bees (Bonabeau, Dorigo, & Theraulaz, 1999). Ant Colony Optimization (ACO) is a well-known SI Metaheuristic (MH) in which optimization algorithms are inspired by the decentralized, collective behavior of ant colonies (Dorigo & Gambardella, 1997; Dorigo & Caro, 1999). Another SI MH is Marriage in Honeybee Optimization (MBO), which analyzes the mating flight of honey-making bees; MBO was originally proposed by H. Abbass (Abbass, 2001a, 2001b, 2001c) to solve the SAT problem (Garey & Johnson, 1979).

The original MBO algorithm is a hybrid MH based on Simulated Annealing (SA) (Kirkpatrick, Gelatt, & Vecchi, 1983), Genetic Algorithms (GA) (Goldberg, 1989), and Local Search (LS) (Talbi, 2009). It incorporates a mating function similar to SA and provides the advantages of GA and LS for generating and improving the broods by the worker bees. However, MBO also has a large number of distinguishing characteristics.

The literature includes two approaches based on the mating behavior of bees: MBO and Honeybee Mating Optimization (HBMO), the second is a modified version of MBO that considers bee populations. Chang (2006) demonstrated the theoretical capacity of MBO for solving combinatorial optimization problems and pointed out that the algorithm converges. A. Baykasoğlu et al. (2007) reviewed the literature on bee MH approaches. Both methods have been applied to a variety of problems, including SAT, data mining (Amiri & Fathian, 2007; Benatchba, Admane, & Koudil, 2005; Fathian, Amiri, & Maroosi, 2007), water resource management (A. Afshar, Bozorg Haddad, Marino, & Adams, 2007; Bozorg Haddad & A. Afshar, 2004; Bozorg Haddad, Abbas Afshar, & Mariño, 2006), constrained and unconstrained nonlinear optimization (Bozorg Haddad et al., 2006), the traveling salesman (C. Yang, Tu, & Chen, 2007), the traveling salesman with vehicle routing (Marinakis, Marinaki, & Dounias, 2007, 2008), dynamic stochastic scheduling (Bozorg Haddad et al., 2006), the reconfiguration of a radial energy distribution system (Niknam, 2009; Niknam, Olamaie, & Khorshidi, 2008), state estimation of a power distribution network system (Niknam, 2008), and the sales forecast problem (Pai, S. Yang, & P. Chang, 2009).

Complete Chapter List

Search this Book:
Reset