An efficient scatter search algorithm for minimizing earliness and tardiness penalties in a single-machine scheduling problem with a common due date

Since the just-in-time (JIT) problems have special importance in the real world, various methods have been developed by researchers to solve this kind of problem more precisely and in a minimal possible time. Most of JIT problems are NP-hard, thus many of these methods have been created based on metaheuristics. In this paper the single-machine scheduling problem with a common due date is considered in which performance is measured by the minimization of the sum of earliness and tardiness penalties of the jobs. Here we use a solving method based on scatter search metaheuristic in which the features of optimal solution of single machine minimization are utilized appropriately. The proposed approach is examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs. In addition to having a good solution time, we got new upper bounds in our numerical examples using proposed method.