A Discrete Chimp Optimization Algorithm for Minimizing Tardy/Lost Penalties on a Single Machine Scheduling Problem

Abstract

The Tardy/Lost (TL) penalties scheduling is a discrete optimization problem. TL scheduling problem is an NP-hard problem. As a result, proposing an optimization algorithm to handle this problem is critical. In a TL problem, a given set of jobs is scheduled on a single machine with common due dates to minimize the total penalties for tardiness jobs. The job will be lost and a certain penalty will be imposed if the tardiness of it exceeds a specific value. This paper proposes a novel improved version of the newly proposed chimp optimization algorithm (ChOA) for not only the TL problem but also, other discrete optimization problems. The proposed algorithm is named a discrete chimp optimization algorithm (DChOA). As far as we know, this is the first paper to solve the TL scheduling problem with a meta-heuristic algorithm. In DChOA, the original parameters and operators are modified and improved, and also a new swap operator is invoked to solve the TL problem. We compare the proposed DChOA with various well-known meta-heuristic algorithms as the genetic algorithm (GA), particle swarm optimization (PSO), grey wolf optimization (GWO), and crow search algorithm (CSA). Moreover, it compared against the MTLR (Minimum Tardy/Lost Ratio) heuristic algorithm in the literatures to verify its efficiency. Based on the experimental results, the DChOA outperformed the other algorithms and proved its superiority in obtaining near optimal solutions in most instance sizes of jobs.

Keywords

• Chimp optimization algorithm (ChOA)
• scheduling problems
• Tardy/Lost penalty
• meta-heuristic algorithms
• swap operator