Hybrid Genetic Bees Algorithm applied to Single Machine Scheduling with Earliness and Tardiness Penalties

Baris Yuce, Fabio Fruggiero, Michael S Packianather, Duc Truong Pham, Ernesto Mastrocinque, Alfredo Lambiase, Marcello Fera

Research output: Contribution to journalArticle

15 Citations (Scopus)
31 Downloads (Pure)

Abstract

This paper presents a hybrid Genetic-Bees Algorithm based optimised solution for the single machine scheduling problem. The enhancement of the Bees Algorithm (BA) is conducted using the Genetic Algorithm’s (GA’s) operators during the global search stage. The proposed enhancement aims to increase the global search capability of the BA gradually with new additions. Although the BA has very successful implementations on various type of optimisation problems, it has found that the algorithm suffers from weak global search ability which increases the computational complexities on NP-hard type optimisation problems e.g. combinatorial/permutational type optimisation problems. This weakness occurs due to using a simple global random search operation during the search process. To reinforce the global search process in the BA, the proposed enhancement is utilised to increase exploration capability by expanding the number of fittest solutions through the genetical variations of promising solutions. The hybridisation process is realised by including two strategies into the basic BA, named as “reinforced global search” and “jumping function” strategies. The reinforced global search strategy is the first stage of the hybridisation process and contains the mutation operator of the GA. The second strategy, jumping function strategy, consists of four GA operators as single point crossover, multipoint crossover, mutation and randomisation. To demonstrate the strength of the proposed solution, several experiments were carried out on 280 well-known single machine benchmark instances, and the results are presented by comparing to other well-known heuristic algorithms. According to the experiments, the proposed enhancements provides better capability to basic BA to jump from local minima, and GBA performed better compared to BA in terms of convergence and the quality of results. The convergence time reduced about 60% with about 30% better results for highly constrained jobs. Publisher Statement: NOTICE: this is the author’s version of a work that was accepted for publication in Computers & Industrial Engineering. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Computers & Industrial Engineering, [(in press) (2017)] DOI: 10.1016/j.cie.2017.07.018 © 2017, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/
Original languageEnglish
Pages (from-to)842-858
Number of pages17
JournalComputers & Industrial Engineering
Volume113
Early online date22 Jul 2017
DOIs
Publication statusPublished - Nov 2017

Keywords

  • Swarm-based optimisation
  • Bees Algorithm (BA)
  • Genetic Bees Algorithm (GBA)
  • Single Machine Scheduling Problem (SMSP)

Fingerprint Dive into the research topics of 'Hybrid Genetic Bees Algorithm applied to Single Machine Scheduling with Earliness and Tardiness Penalties'. Together they form a unique fingerprint.

  • Cite this