An Effective Solution for Large Scale Single Machine Total Weighted Tardiness Problem using Lunar Cycle Inspired Artificial Bee Colony Algorithm

摘要

Single machine total weighted tardiness problem (SMTWTP) is one of the fundamental combinatorial optimization problems. The problem consists of a set of independent jobs with distinct processing times, weights, and due dates to be scheduled on a single machine. The goal of the problem is to minimize the total weighted tardiness. Several swarm intelligence (SI) motivated techniques have been proposed to solve SMTWTP. Still, the solution for large scale SMTWTP instances within a reasonable amount of time is a challenging task. Artificial bee colony (ABC) algorithm is one of the efficient SI based techniques to solve real world optimization problems. This article presents an effective amended ABC based strategy to solve SMTWTP. A local search (LS) approach, influenced from the lunar cycle is proposed and hybridized with ABC to escalate the exploitation capacity of the algorithm. The proposed LS approach is titled as the lunar inspired LS (LLS) approach and the proposed hybridized strategy is known as lunar inspired ABC (LuABC) algorithm. The proposed LuABC algorithm has been applied on 25 large SMTWTP instances of job size 1000. The obtained outcomes prove that the proposed algorithm obtains the optimum solutions for all the considered instances within a reasonable amount of time.