Scheduling Problems With Generalized Due Dates

Abstract

We define a new class of scheduling problems, for which due dates are specified in terms of the position in which a job appears in an ordered sequence, rather than by that job's identity. This problem class appears rich both in applications and in theoretical issues. For many traditional scheduling problems there exists an equivalent problem within the new class. We examine the algorithmic complexity of several of these problems, and attempt to provide an efficient solution technique, or alternatively to demonstrate that such a technique is highly unlikely to exist. In two cases, the complexity of the problem being discussed remains open.