In this paper, we consider the single machine scheduling problem with inventory operations. The objective is to minimize makespan subject to the constraint that the total number of tardy jobs is minimum. We show the problem is strongly NP-hard. A polynomial (1 + 1/(
− 1))-approximation scheme for the problem is presented, where
is defined as the total job’s processing times ∑
divided by the capacity
of the storage, and an optimal algorithm for a special case of the problem, in which each job is one unit in size, is provided.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten