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,h1∥Emax) and also the same problem with simultaneous minimization of the two criteria of maximum earliness and number of tardy jobs (1,h1∥Emax,NT) are studied. It is shown that the problem 1,h1∥Emax 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,h1∥Emax,NT is to find the set of efficient solutions, i.e. the Pareto frontier. For this reason, for each measure Emax and NTNT 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.