BICRITERIA SCHEDULING ON SINGLE-MACHINE WITHINVENTORY OPERATIONS

摘要

In this paper, we consider the single machine scheduling problem with inventory oper-ations. The objective is to minimize makespan subject to the constraint that the totalnumber of tardy jobs is minimum. We show the problem is strongly NP-hard. A poly-nomial 1 + rn1-approximation scheme for the problem is presented, where m is definedas the total job's processing times ER, divided by the capacity c of the storage, and anoptimal algorithm for a special case of the problem, in which each job is one unit in size.