Hybrid metaheuristic approaches for the single machine total stepwise tardiness problem with release dates

This paper presents two hybrid metaheuristic approaches, viz. a hybrid genetic algorithm and a hybrid artificial bee colony algorithm for a single machine scheduling problem where tardiness cost of a job increases stepwise with various due dates and the objective is to minimize the total tardiness cost. This kind of tardiness cost occurs in several real life scenarios particularly in transportation. Two versions of the scheduling problem are considered. In the first version, all jobs are assumed to be available for processing at the beginning, whereas in the latter version jobs have release dates. For both versions, we have employed a local search to further improve the solutions obtained through our metaheuristic approaches. To the best of our knowledge, our approaches are the first metaheuristic approaches for the latter version of the problem. For the first version, we have compared our approaches with the state-of-the-art approaches available in the literature. Computational results show the superiority of our approaches over previous approaches in terms of solution quality and running time both. For the latter version, hybrid artificial bee colony algorithm based approach outperformed the hybrid genetic algorithm based approach in terms of solution quality and running time both.