Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem with availability constraint

In this paper the problem of minimizing maximum earliness on a single machine with an unavailability period $(1,h_1\parallel E_{\max })$ and also the same problem with simultaneous minimization of the two criteria of maximum earliness and number of tardy jobs $(1,h_1\parallel E_{\max },N_T)$ are studied. It is shown that the problem $1,h_1\parallel E_{\max }$ is NP‐hard. For this problem a branch and bound approach is proposed which is based on a binary search tree. Proposing a heuristic algorithm named MMST, lower bound and efficient dominance rules, results in some instances with up to 3000 jobs being solved. The purpose in the problem $1,h_1\parallel E_{\max },N_T$ is to find the set of efficient solutions, i.e. the Pareto frontier. For this reason, for each measure $E_{\max }$ and $N_T$ at first changes domain are calculated. A heuristic algorithm named PH and a branch and bound approach are developed to solve the problem. Proposing a lower bound and some dominance rules resulted in 96.4% of instances being solved optimally which proves the efficiency of the proposed method.