Scheduling of jobs in the presence of constraints in Java
- by Asgard
I want to know how to implement a solution to this problem:
A task is performed by running, by more people, some basic jobs with known duration in time units (days, months, etc..). The execution of the jobs could lead to the existence of time constraints: a job, for example, can not start if it is not over another (or others) and so on. I want to design and build an application to check the correctness of jobs activities and to propose a schedule of jobs, if any, which is respectful of the constraints. Input must provide the jobs and associated constraints. The expected output is the scheduling of jobs.
The specification of an elementary job consists of the pair
<jobs-id, duration>
A constraint is expressed by means of a quintuple of the type
<S/E, id-job1, B/A, S/E, id-job2>
the beginning (S) or the end (E) of a jobs Id-job1, must take place before (B) / after (A) of the beginning (S) / end (E) of the Id-job2. If there are no dependencies between some jobs, then jobs can be done before, in parallel.
As a simple example, consider the input:
jobs
jobs(0, 3)
jobs(1, 4)
jobs(2, 5)
jobs(3, 3)
jobs(4, 3)
constraints
constraints(S, 1, A, E, 0)
constraints(S, 4, A, E, 2)
Possible output:
t 0 1 2 3 4
0 * - * * -
1 * - * * -
2 * - * * -
3 * - * * -
4 - * * - -
5 - * * - -
6 - * - - *
7 - * - - *
8 - * - - *
9 - - - - *
How to code an efficient java scheduler(avoiding the intense backtracking if is possible) to manage the jobs with these constraints, as described???
I have seen a discussion on a thread in a forum where an user seems has solved the problem easily, but He haven't given enough details to the users to compile a working project(I'm noob), and I'm interested to know an effective implementation of the solution (without using external libraries).
If someone help me, I'll give to him a very good feedback ;)
