Job Scheduling as a CSP:
A Constraint Satisfaction Problem consists of
Initial States: unassigned variables
Successor Function: value to assign to a variable, not conflicting with previous assignments
Goal Test: all variables assignment complete
Path Cost: constant: 1 per step.
M: number of machines
J: a number of random jobs, containing 1-j subjobs
j : maximum number of subjobs
Constraints:
--cannot perform subjob n before subjob n-1
--if a machine can be assigned a job, it will not sit idle
--all subjobs must be completed to complete a job
Goal: all jobs completed.
In Forward State Search all possible actions at each time step are considered. Obviously, this is a large problem, but finite in this Job Scheduling scenario. An admissible heuristic is necessary to make this efficient. In my project, I will do the brute force, inefficient method of enumerating all possibilities.
This will create linear plans for the assignment of jobs to subjobs. I choose to perform breadth-first search so that the first plan completed and returned will be a shortest plan. Even if other paths are equally short, the first shortest plan will be the same length in terms of cost.
If looking for average job completion time, all shortest path problems would need to be considered. This is a possible further extension of this problem.
In Backward State Search, another brute-force approach, we start at the Goal state, all jobs have been finished. Then we assign the subjobs in reverse order to the machines and find the shortest time to setting all jobs to not done state.
In the code, there are several classes: Scheduler (the main class), randomjob, subjob, and planNode. The scheduler has the methods forwardStateSearch() and backwardStateSearch(). These methods first find all possible initial plans, then expands each of those into the next possible states one level at a time, using BFS.