Minimizing the number of tardy jobs with controllable processing times Academic Article uri icon


  • Abstract This research basically extends the boundaries of the minimization of the number of tardy jobs (N^ sub T^) problem to where processing times are controllable by allocating a common, continuous, and non-renewable resource. Most of the research on scheduling with controllable resource-dependent processing times assumed either a linear resource consumption function, that does not obey the law of diminishing returns or a speci? c convex consumption function, that applies only to a limited number of problems. We, on the other hand, assume a general consumption function, which guarantees a very robust solution that can be applied for a very wide range of problems and is appropriate for real life situations. We established the computational complexity for the N^ sub T^ problem with controllable resource dependent processing times, proving it to be NP-hard. We present a polynomial …

publication date

  • January 1, 2006