In a graph, there are points that need to be visited. For each of these points, there
is a certain time interval given by its start and end times, telling the time interval during which that point can be visited. Furthermore, for some pairs of points,
one must be visited before the other (the time precedence order of such point-pairs are given and consistent in the input).
Also given is the amount of time needed to get from one point to the other.
An example case I could think of:
There's heavy red-tape on a certain type of process, say
Process-Xthat you need to get done, and you have to get so many signatures/approvals from multiple offices, visit people sitting at their desks for one such process.They all aren't at the same place — it takes time to get from one to the other.
For some of that paperwork, you have to get it done at one place before you can get the rest of it at another.
Each office/person to process your work has office hours that are given, and you can only visit them during those hours.
The goal is to get as many
Process-Xs done as possible.
How is this problem described in literature?
It has time-precedence. However it isn't job-scheduling— job-scheduling is optimizing the time spent.
What you are describing is a subset of automated planning. You would typically describe your problem in an action language like STRIPS and then run a planner to determine whether the goal state or states can be reached. Determining whether a successful plan exists for a given problem is PSPACE-complete, but constraints such as limiting the number of steps to reach a goal can make the problem merely NP-complete and amenable to attack by SAT solvers.