A branch-and-bound and heuristic algorithm for the single-machine time-dependent scheduling problem

The time-dependent scheduling problems have received considerable attention recently. However, machine availability, an important and practical consideration, is usually neglected. Motivated by this observation, we introduce a single-machine scheduling problem where deteriorating jobs and an availability constraint are considered. Our objective is to minimize the total completion time. In this paper, we derived optimal and near-optimal solutions for the problem, and we also gave a simulation study to show that our algorithm successfully yields the optimal solution for instances with less than 20 jobs in less than a minute. Our computational experiment also showed that the mean error percentage of the proposed heuristic algorithm for all test instances is less than 1.3% and drops to zero as the number of jobs increases.