Due Date: December 5th, 2005 at 6 PM
To understand Constraint Satisfaction Problems (CSP). To implement a
program that solves a constraint satisfaction problem. To understand how
to create a constraint network and to use binary constraint matrices.
The following is a generic scheduling problem.
We need to execute n tasks using m processors
under certain constraints. It may help to think about these tasks as computer
processes, and processors as CPUs, but this could just as easily apply to
construction workers and jobs, or a software engineering management
problem. For simplicity, we'll use the following notation:
- Tasks: The n tasks will be denoted by n upper case letters (e.g. A,
T, E, G, .....);
- The "length" of each task is given. The length corresponds to the
number of seconds that it takes a processor to perform the task.
- Processors: The m processors will be denoted by m lower case letters
(e.g. p, w, f, s, ...).
Each of the processors performs the tasks assigned to it in a sequential manner.
Processors are independent from each other. There is no ordering of
tasks assigned to a processor, that is, you should not care in what order
tasks will be executed, only which processors execute them.
- Constraints: The constraints are of the following sort:
- Deadline: A deadline d, given in seconds, is specified as a
constraint. All tasks must be executed before the deadline.
That is, each of the processors must be able to sequentially execute
all tasks assigned to it before the deadline.
All processors start executing the processes assigned to them at
time t = 0.
- Unary constraints (involving one variable):
- A task can only be assigned to one of a subgroup of processors.
For instance, the user may specify that task R can be performed by one of the following processors:
g, r, e.
- A task cannot be assigned to any in a given group of processors.
Example: task W can be assigned to neither f nor j.
- Binary constraints (involving two variables):
- Two given tasks need to be performed on the same processor.
- Two given tasks cannot be assigned to the same processor.
- Two given tasks cannot be simultaneously assigned to a given
pair of processors. For instance, the user can specify that
task D cannot be assigned to processor p if task E is assigned
to processor u. To be more specific, this constraint is regardless of
time, that is, all assignments take place before any tasks have been executed,
at time t = 0. If D is assigned to p, then E can not be assigned to u, even if the two tasks could be executed at different times.
Your program (or a script accompanying your program) must accept a
filename as a one command-line argument. For example, you might run
your program by typing "java Project3 filename.txt" or
"runProject3 filename.txt". The file specified by the
argument has a specific format:
The output of the system should be either:
- An assignment of processors to tasks such that all constraints are
satisfied (including the deadline constraint).
- The total length of tasks assigned to each processor.
- The total length of all tasks.
OR
- A message stating that NO such assignment is possible, IF that's
the case.
Design and implement a constraint satisfaction system that
produces an assignment of processors to tasks which satisfies all
constraints (including the deadline constraint), if such an assignment exists.
Your system must satisfy the following requirements:
- The internal representation of the problem should use a constraint net.
Note that the variables in this problem are the tasks
and the domain of each of the variables is the set of all processors.
- Binary constraints should be represented using constraint matrices.
Each constraint matrix is an m-by-m matrix.
- The problem solving strategy should be an implementation of the CSP strategies and methods discussed in class and in the textbook:
- Arc consistency checking (use the AC-3 or the AC-4 algorithms),
- an effective search method,
- a sound heuristic to select the order in which the variables are expanded, and
- a sound heuristic to select the order in which the values are considered.
- You MUST write YOUR OWN code in any high level programming language.
You MUST include a short user's manual with your submission so that I
know how to run you system.
- Your program must adhere to the input and output specifications.
Along with your code, you must also submit a written report.
- Program.
- Email me the source code for your program
and ancillary files that your program requires, such as a script
to run a language interpreter, IF ANY, before the project deadline.
Your code should be fully documented and easy to read.
- Written Report
- your name
- instructions on compiling and running your program
- detailed description of your approach. That is, what search method
and what heuristics were used, how was AC employed, etc.
Please try to describe your approach in an algorithmic manner (i.e.,
include pseudo-code of the overall approach).
- results:
- describe which tests you ran to try out your program. How did your
program perform?
- describe the strengths and the weaknesses of your program.
- Remember, you should have sufficient, clear documentation, both external
to your program and internal to your program. This can do nothing
but help your grade. If no one can understand your code, and
something doesn't work, one can only assume that you did not understand
the problem well enough to code it clearly.
Each student will have up to 8 minutes to discuss his/her project in class.
Prepare slides for your presentation. Try to highlight the most important
and novel parts of your work (a maximum limit of 8 minutes per presentation
will be enforced).
We'll have project presentations on Dec. 5th and Dec. 12th.
The order in which the students will present will be selected at random
during those classes.
Your presentation will count for 10% of your project grade.
Let's extend the specification of the constraint satisfaction problem of this
project.
Your program now accepts a second filename specified by a second command-line
argument. This file contains costs associated with using each of the processors. The cost
will represent the amount of dollars charged for using the processor during one second. That is, if a task
W uses the processor d for 12 seconds and the cost of using d is $10/sec then the total charge
for task W will be
$120.
The file format is simply pairs of a lower case letter (processors, values in
the domain of the variables) and a non-negative integer, as shown:
x 34
y 22
z 10
p 0
q 2
r 12
Extend the constraint satisfaction system that you constructed to
output an optimal assignment of processors
to tasks, that is an assignment that satisfies all constrains and that
minimizes the total cost of executing the tasks. Your program should also
display what the total cost is. Include the description of this code in your
written report and also include the code in your project submission.