An Improved Marriage in Honey-Bee Optimization Algorithm for Minimizing Earliness/Tardiness Penalties in Single-Machine Scheduling with a Restrictive Common Due Date

This study evaluates the efficiency of a swarm intelligence algorithm called marriage in honey-bee optimization (MBO) in solving the single-machine weighted earliness/tardiness problem, a type of NP-hard combinatorial optimization problem. The goal is to find the optimal sequence for completing a set of tasks on a single machine, minimizing the total penalty incurred for tasks being completed too early or too late compared to their deadlines. To achieve this goal, the study adapts the MBO metaheuristic by introducing modifications to optimize the objective function and produce high-quality solutions within reasonable execution times. The novelty of this work lies in the application of MBO to the single-machine weighted earliness/tardiness problem, an approach previously unexplored in this context. MBO was evaluated using the test problem set from Biskup and Feldmann. It achieved an average improvement of 1.03% across 280 problems, surpassing upper bounds in 141 cases (50.35%) and matching or exceeding them in 193 cases (68.93%). In the most constrained problems ( h = 0.2 and h = 0.4), the method achieved an average improvement of 3.77%, while for h = 0.6 and h = 0.8, the average error was 1.72%. Compared to other metaheuristics, MBO demonstrated competitiveness, with a maximum error of 1.12%. Overall, MBO exhibited strong competitiveness, delivering significant improvements and high efficiency in the problems studied.