Single machine scheduling with delivery dates and cumulative payoffs

Yasmina Seddik (LIP6, Paris)

We address a scheduling problem with a new criterion and unequal
release dates. This new criterion results from a practical situation in
the domain of book digitization. Given a set of job-independent delivery
dates, the goal is to maximize the cumulative number of jobs processed
before each delivery date. We establish the complexity of the general
problem. In addition, we provide a pseudopolynomial time algorithm for the
two delivery dates case based on dynamic programming, and we discuss some
polynomial cases. Finally, a branch-and-bound method was designed to solve
the general problem.