Abstract

Most of the real world scheduling problems incorporates Just-In-Time production philosophy which leads to a growing interest in the development of various nature inspired metaheuristic algorithms. Single Machine Early Tardy scheduling problem (SMETP) is one such problem in which jobs have to be scheduled on a single machine against a restrictive common due date parameter and this problem is strongly a NP-hard combinatorial optimization problem. As job sizes vary from 10 to 1000, problems of larger job sizes cannot be solved by exact algorithms. Hence in this research study, we propose genetic algorithm with variations in local search to find an optimal schedule which jointly minimizes the summation of earliness and tardiness cost penalties of 'n' jobs from a common due date by satisfying the three SMETP scheduling properties. The performance of this evolutionary algorithm is validated on the 280 benchmark instances proposed by Biskup and Feldmann for various job sizes and the results show that genetic algorithm works well for smaller job sizes.

Keywords:

Common due date, genetic algorithm, heuristics, local search, single machine scheduling,

References

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.