The objective of this assigment is to give you more experience with graph structures, and to demonstrate the usefulness of the constraint propogation technique. Constraint propogation techniques can vastly reduce the amount of searching needed to identify a satisfactory assignment of values to states.
Your task in this assignment will be to implement the classic constraint satisfaction problem of job shop scheduling. In job shop scheduling, you are trying to create a schedule for a manufacturing operation. In this manufacturing operation, you have a set of jobs that need to be done, a set of resources that are available, and (in the second part of the assignment) an ordering that the jobs need to occur in.
To clarify, we can go through a small example. Lets say that you are in charge of scheduling a cookie manufacturing operation. To fulfill your current orders, you need one batch of fancy cookies and one batch of plain cookies. You can break this down into the following jobs and their constraints:
Job# Description Duration Resource
Job0 Making Plain Dough 1 R0 (mixer)
Job1 Making Fancy Dough 2 R1 (mixer)
Job2 Cook Plain Cookies 1 R2 (oven)
Job3 Cook Fancy Cookies 2 R2 (oven)
Job4 Fabricate Tin 4 R3 (tin machine)
Job5 Put Cookies in Tin 1 R4 (packager)
Global Constraints: Job0 Before Job2 Job1 Before Job3 Job4 Before Job5 Maximum Time Available: 5 units
Given these constraints, you can generate all the possible assignments of starting times and resources for these jobs (Syntax StartTime::Resource):
Job0: 0::R0, 1::R0, 2::R0, 3::R0 Job1: 0::R1, 1::R1 Job2: 1::R2, 2::R2, 3::R2, 4::R2 Job3: 2::R2, 3::R2 Job4: 0::R3 Job5: 4::R4
Convince yourself that these are the only possible schedule assignments for the jobs that satisfy the constraints above (Resource, Duration, and Ordering). The constraints have fixed the scheduling assignment for Job4 and Job5 (there is only one possible scheduling given the constraints). However, there is still uncertainty about the schedule for the first 4 jobs. We will resolve this uncertainty through a specialized depth first search. We will choose a schedule assignment for an uncertain job, and then recursively see if it is possible to satisfy the constraints given that choice. Rather than randomly choose which uncertain job to assign a schedule, we will choose the job that is most constrained (the job with the fewest possibile schedule assignments). In addition rather than randomly choosing which possible schedule assignment to choose for the most constrained job, we will always choose the assignment with the earliest starting time. If we make a choice of schedule assignment that makes the constraints unsatisfiable, we will backtrack (through the depth-first search recursion and make another choice). If all of our possible choices make the constraints unsatisfiable, then the scheduling problem has no solution. If we ran this depth first search on our example, we would choose to assign Job1 to 0::R1 and then propagate the effects of that commitment given the constraints (in this case there are no effects on other jobs). Then recursively we would assign Job3 to 2::R2 and then propogate the effects (we would have to remove 2::R2 and 3::R2 from Job2's possible assignments). Continuing, we would assign Job2 (which now only has two possibilities) to 1::R2 and propogate the effects (we would have to fix Job0 to 0::R0). At this point, we have found a schedule that satisfies the constraints:
Job0: 0::R0 Job1: 0::R1 Job2: 1::R2 Job3: 2::R2 Job4: 0::R3 Job5: 4::R4
In this assignment, you will implement this process in Java. In the supporting code, I have given you a template for a Vertex_Job class and the Schedule_Graph class. In addition, the supporting code will read in a set of jobs and constraints into the data structures. By generating possible schedule assignments given the constraints, and doing a depth first search (and propogating) as described above you should be able to generate schedules that satisfy the constraints. Upon generating a satisfactory schedule, you sould print it out in the form given above.
You may implement this in two stages. In stage #1, you can ignore the global constraints placed on the schedule (ordering doesn't matter). In stage #2, you need to enhance your stage #1 code so that it adheres to the global constraints. See the grading page for important information.
The program can be run using the following syntax:
java Assign5 [filename] [MAX_TIME]
Good luck on the Assignment!
Revised on Thursday, November 20, 1997