IEEE/ACM Trans Comput Biol Bioinform. 2020 Sep-Oct;17(5):1573-1581. doi: 10.1109/TCBB.2019.2897302. Epub 2019 Feb 4.
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.
单机总加权 tardiness 问题 (SMTWTP) 是基本组合优化问题之一。该问题由一组具有不同处理时间、权重和截止日期的独立作业组成，需要在一台机器上进行调度。该问题的目标是最小化总加权 tardiness。已经提出了几种基于群体智能 (SI) 的技术来解决 SMTWTP。然而，在合理的时间内解决大规模 SMTWTP 实例仍然是一项具有挑战性的任务。人工蜂群 (ABC) 算法是解决实际优化问题的一种有效的基于 SI 的技术。本文提出了一种有效的基于改进的 ABC 算法来解决 SMTWTP。受到月球周期影响的局部搜索 (LS) 方法被提出并与 ABC 混合，以提高算法的开发能力。所提出的 LS 方法被命名为月球启发式 LS (LLS) 方法，所提出的混合策略被称为月球启发式 ABC (LuABC) 算法。所提出的 LuABC 算法已应用于 25 个作业规模为 1000 的大型 SMTWTP 实例。获得的结果证明，所提出的算法在合理的时间内为所有考虑的实例获得了最优解。
