The counting complexity of a simple scheduling problem

The counting complexity of a simple scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20102991
Volume: 37
Issue: 5
Start Page Number: 365
End Page Number: 367
Publication Date: Sep 2009
Journal: Operations Research Letters
Authors:
Abstract:

Let T be a set of tasks. Each task has a non-negative processing time and a deadline. The problem of determining whether or not there is a schedule of the tasks in T such that a single machine can finish processing each of them before its deadline is polynomially solvable. We prove that counting the number of schedules satisfying this condition is NP-complete.

Reviews

Required fields are marked *. Your email address will not be published.