Minimizing the Sum of Maximum Earliness and Tardiness on a Single Machine with multiple Unavailability Period

This paper considers a single machine scheduling problem with multiple Unavailability Period that minimizes the sum of maximum earliness and tardiness. We prove problem is NP-hard in the strong sense. To solve this strongly NP-hard problem we use cuckoo optimization algorithm which rarely applied in scheduling problem. For the evaluation of the proposed COA, problem data was generated to compare it against a PSO. The results of computational experiments show the good performance of the proposed algorithm.

Keywords:

Scheduling , single machine , availability constraint , cuckoo optimization algorithm (COA) , sum of maximum earliness and tardiness