Title: An adaptation of the galaxy-based search algorithm for solving the single machine total weighted tardiness problem

Authors: Mohamed Habib Zahmani

Addresses: Mathematics and Computer Science Department, University Abdelhamid Ibn Badis – Mostaganem, Algeria; Equipe AIR, Laboratoire d'Informatique d'Oran, University of Oran 1 Ahmed Benbella, Algeria

Abstract: The single machine total weighted tardiness (SMTWT) problem (referred to as 1//Σw_iT_i) requires a given set of jobs to be sequenced on a single machine while minimising the sum of weighted tardiness, where the tardiness of a job is zero if it is completed before its due date and is equal to completion time minus its due date otherwise. In this article, the 'galaxy-based search algorithm' (GbSA) is adapted to solve the SMTWT benchmark problems and its results are compared with the best-known reported solutions. The GbSA is a newly developed optimisation tool and is considered a metaheuristic technique inspired by the dynamics of galactic arm spirals. It is robust, capable of avoiding being trapped in a local optimum, has a relative fast convergence, and is easily implementable. The experiments results show that the proposed adaptation of the GbSA is effective and obtains high-quality solutions within reasonable computation times. [Submitted 4 March 2019; Accepted 26 February 2020]

Keywords: galaxy-based search algorithm; GbSA; local search; single machine scheduling; total weighted tardiness; TWT; dispatching rules.

DOI: 10.1504/IJMR.2021.119640

International Journal of Manufacturing Research, 2021 Vol.16 No.4, pp.399 - 413

Received: 04 Mar 2019
Accepted: 26 Feb 2020
Published online: 13 Dec 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article