A new model of task system in which the execution time of a task depen
ds on its starting time is considered. It is shown that the feasibilit
y problem on a single processor is NP-complete for a set of tasks with
identical release times and two distinct deadlines. An O(n log n)-tim
e algorithm is given for a set of tasks with identical release times a
nd deadlines. These two results give a sharp boundary delineating the
complexity of the problem.