Courses/CS 460/Fall 2006/Strom, Richard/Newspaper Scheduling With Choco
From CSWiki
< Courses | CS 460 | Fall 2006 | Strom, Richard
Contents |
[edit] Newspaper Scheduling With Choco
This is the newspaper puzzle without the built in ordering. So we only know what time each student wakes up, and how long they read each newspaper for. This makes this a scheduling problem, so I used choco's cumulative constraint several times to make sure that no overlaps occur.
I keep a 2D array for the start times (readTimes), end times (endTimes) and durations (studentNeeds). I wrote a little helper function to return a column of a 2D array as a 1D array. The cumulative constraints basically say for a set of start times, end times and durations, make sure the height of consumption doesn't exceed a certain amount. In this case, the heights are all set to 1 to make sure consumption of a resource (newspaper) doesn't overlap (i.e., only one student can read a given newspaper at a time).
There is a set of cumulative constraints for each newspaper to make sure they aren't consumed simultaneously. There is a second set of cumulative constraints for the individual students, to make sure they aren't consuming more than one newspaper at a time. So the cumulutive constraint is run on all the aligned rows of the 3 2D arrays, then all the columns of those arrays.
I did not add any minimization constraints, it seems that this is built in to the cumulative constraint (or, I just got lucky).
This definitely gives the optimal solution (see Digby, who decides the outcome of this problem).
By the way, choco is pretty fantastic. I did this pretty quick with it.
[edit] Problem
| Algy | Bertie | Charlie | Digby | ||||
| FT | 60 min | Guardian | 75 min | Express | 5 min | Sun | 90 min |
| Guardian | 30 min | Express | 3 min | Guardian | 15 min | FT | 1 min |
| Express | 2 min | FT | 25 min | FT | 10 min | Guardian | 1 min |
| Sun | 5 min | Sun | 10 min | Sun | 30 min | Express | 1 min |
Algy gets up at 8:30, Bertie and Charlie at 8:45 and Digby at 9:30. What is the earliest that they can all set off for college?
[edit] Code
/* ---------------------------------------------
* Newspaper Problem (with scheduling)
* Rick Strom/CS460
*
* It looks like the newspaper problem actually
* does specify the order in which the students
* read the paper. This is the same problem with
* order to be determined by the solver.
*
* So we are given the wake up times for each
* student, and the time they take to read each
* paper, and we want to find the reading schedule
* which gets them all out of the house the fastest.
* ---------------------------------------------*/
package newspaperscheduling;
import choco.*;
import choco.integer.*;
public class NewspaperScheduling {
public static Problem myProb;
public static IntVar [][] studentNeeds; // how long student reads newspaper [i = student id, j = newspaper id]
public static IntVar [][] readTimes; // what time student starts reading newspaper [i = student, j = newspaper id]
public static IntVar [][] endTimes; // what time student finishes reading newspaper [i = student, j = newspaper id]
public static IntVar [] studentWakeupTimes; // what time student wakes up [i = student id]
public static IntVar [] studentLeaveTimes; // what time student leaves [i = student id]
public static int algy, bertie, charlie, digby;
public static int guardian, ft, express, sun;
public static void main(String [] args) {
// Constants to represent students, newspapers
algy = 0;
bertie = 1;
charlie = 2;
digby = 3;
guardian = 0;
ft = 1;
express = 2;
sun = 3;
// Create the problem object
myProb = new Problem();
// Initialize the IntVar arrays
studentNeeds = new IntVar[4][4];
readTimes = new IntVar[4][4];
endTimes = new IntVar[4][4];
studentWakeupTimes = new IntVar[4];
studentLeaveTimes = new IntVar[4];
// Define problem
createVars();
createConstraints();
//Solve
if (myProb.solve() == Boolean.TRUE) {
outputSolution();
} else {
System.out.println("No solution found");
for(int i = 0; i < myProb.getNbIntVars(); i++) {
System.out.println(myProb.getIntVar(i) + " = " + ((IntDomainVar) myProb.getIntVar(i)).getVal());
}
}
}
public static void createVars() {
// Create the variables for the newspaper scheduling problem
// List of student needs
studentNeeds[algy][guardian] = myProb.makeEnumIntVar("Need_"+ algy + "-" + guardian, 30, 30);
studentNeeds[algy][ft] = myProb.makeEnumIntVar("Need_"+ algy + "-" + ft, 60, 60);
studentNeeds[algy][express] = myProb.makeEnumIntVar("Need_"+ algy + "-" + express, 2, 2);
studentNeeds[algy][sun] = myProb.makeEnumIntVar("Need_"+ algy + "-" + sun, 5, 5);
studentNeeds[bertie][guardian] = myProb.makeEnumIntVar("Need_"+ bertie + "-" + guardian, 75, 75);
studentNeeds[bertie][ft] = myProb.makeEnumIntVar("Need_"+ bertie + "-" + ft, 25, 25);
studentNeeds[bertie][express] = myProb.makeEnumIntVar("Need_"+ bertie + "-" + express, 3, 3);
studentNeeds[bertie][sun] = myProb.makeEnumIntVar("Need_"+ bertie + "-" + sun, 10, 10);
studentNeeds[charlie][guardian] = myProb.makeEnumIntVar("Need_"+ charlie + "-" + guardian, 15, 15);
studentNeeds[charlie][ft] = myProb.makeEnumIntVar("Need_"+ charlie + "-" + ft, 10, 10);
studentNeeds[charlie][express] = myProb.makeEnumIntVar("Need_"+ charlie + "-" + express, 5, 5);
studentNeeds[charlie][sun] = myProb.makeEnumIntVar("Need_"+ charlie + "-" + sun, 30, 30);
studentNeeds[digby][guardian] = myProb.makeEnumIntVar("Need_"+ digby + "-" + guardian, 1, 1);
studentNeeds[digby][ft] = myProb.makeEnumIntVar("Need_"+ digby + "-" + ft, 1, 1);
studentNeeds[digby][express] = myProb.makeEnumIntVar("Need_"+ digby + "-" + express, 1, 1);
studentNeeds[digby][sun] = myProb.makeEnumIntVar("Need_"+ digby + "-" + sun, 90, 90);
// List of student wakeup times (expressed as minutes since midnight [00:00])
studentWakeupTimes[algy] = myProb.makeEnumIntVar("Wakeup_" + algy, 510, 510);
studentWakeupTimes[bertie] = myProb.makeEnumIntVar("Wakeup_" + bertie, 525, 525);
studentWakeupTimes[charlie] = myProb.makeEnumIntVar("Wakeup_" + charlie, 525, 525);
studentWakeupTimes[digby] = myProb.makeEnumIntVar("Wakeup_" + digby, 570, 570);
// Student leave times. These are constrained in the createConstraints function
// I'm setting a much larger range than necessary, from midnight to midnight (in minutes)
for (int i = 0; i < 4; i++) {
studentLeaveTimes[i] = myProb.makeEnumIntVar("LeaveTime_" + i, 0, 1440);
}
// The values we are looking for: when each student begins reading each newspaper
// I'm setting a much larger range than necessary, from midnight to midnight (in minutes)
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
readTimes[i][j] = myProb.makeEnumIntVar("ReadTime_" + i + "-" + j, 0, 1440);
}
}
// We also need end times, for the cumulative constraint. These will be initially
// constrained (in createConstraints) to readTime[i][j] + studentNeeds[i][j] for each
// I'm setting a much larger range than necessary, from midnight to midnight (in minutes)
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
endTimes[i][j] = myProb.makeEnumIntVar("EndTime_" + i + "-" + j, 0, 1440);
}
}
}
public static void createConstraints() {
// Create the constraints for the newspaper scheduling problem
// First, make sure no student can read a newspaper while sleeping!
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
myProb.post( myProb.geq( readTimes[i][j], studentWakeupTimes[i] ) );
}
}
// Next, constrain the end times to readTime + studentNeed
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
myProb.post( myProb.eq( endTimes[i][j], myProb.plus( readTimes[i][j], studentNeeds[i][j] ) ) );
}
}
// A height array for the cumulative constraint (see below)
int [] heights = {1, 1, 1, 1};
// Consumption constraints are handled with Cumulative
// Start, end, duration are passed for each resource (newspaper), with a height cap of 1 (since it can only be read at one time)
// guardian, ft, express, sun each cannot be read at the same time
myProb.post( myProb.cumulative( getArrayColumn(readTimes, guardian), getArrayColumn(endTimes, guardian), getArrayColumn(studentNeeds, guardian), heights, 1 ) );
myProb.post( myProb.cumulative( getArrayColumn(readTimes, ft), getArrayColumn(endTimes, ft), getArrayColumn(studentNeeds, ft), heights, 1 ) );
myProb.post( myProb.cumulative( getArrayColumn(readTimes, express), getArrayColumn(endTimes, express), getArrayColumn(studentNeeds, express), heights, 1 ) );
myProb.post( myProb.cumulative( getArrayColumn(readTimes, sun), getArrayColumn(endTimes, sun), getArrayColumn(studentNeeds, sun), heights, 1 ) );
// addionally, each student can only read one newspaper at a time
myProb.post( myProb.cumulative( readTimes[algy], endTimes[algy], studentNeeds[algy], heights, 1 ) );
myProb.post( myProb.cumulative( readTimes[bertie], endTimes[bertie], studentNeeds[bertie], heights, 1 ) );
myProb.post( myProb.cumulative( readTimes[charlie], endTimes[charlie], studentNeeds[charlie], heights, 1 ) );
myProb.post( myProb.cumulative( readTimes[digby], endTimes[digby], studentNeeds[digby], heights, 1 ) );
}
public static void outputSolution() {
System.out.println("Schedule: ");
System.out.println("==========");
System.out.println("\nAlgy");
System.out.println("----------");
System.out.println("Wakes up at " + toTime( studentWakeupTimes[algy]));
System.out.println("Reads the guardian from " + toTime(readTimes[algy][guardian]) + " until " + toTime(endTimes[algy][guardian]));
System.out.println("Reads the ft from " + toTime(readTimes[algy][ft]) + " until " + toTime(endTimes[algy][ft]));
System.out.println("Reads the express from " + toTime(readTimes[algy][express]) + " until " + toTime(endTimes[algy][express]));
System.out.println("Reads the sun from " + toTime(readTimes[algy][sun]) + " until " + toTime(endTimes[algy][sun]));
System.out.println("\nBertie");
System.out.println("----------");
System.out.println("Wakes up at " + toTime( studentWakeupTimes[bertie]));
System.out.println("Reads the guardian from " + toTime(readTimes[bertie][guardian]) + " until " + toTime(endTimes[bertie][guardian]));
System.out.println("Reads the ft from " + toTime(readTimes[bertie][ft]) + " until " + toTime(endTimes[bertie][ft]));
System.out.println("Reads the express from " + toTime(readTimes[bertie][express]) + " until " + toTime(endTimes[bertie][express]));
System.out.println("Reads the sun from " + toTime(readTimes[bertie][sun]) + " until " + toTime(endTimes[bertie][sun]));
System.out.println("\nCharlie");
System.out.println("----------");
System.out.println("Wakes up at " + toTime( studentWakeupTimes[charlie]));
System.out.println("Reads the guardian from " + toTime(readTimes[charlie][guardian]) + " until " + toTime(endTimes[charlie][guardian]));
System.out.println("Reads the ft from " + toTime(readTimes[charlie][ft]) + " until " + toTime(endTimes[charlie][ft]));
System.out.println("Reads the express from " + toTime(readTimes[charlie][express]) + " until " + toTime(endTimes[charlie][express]));
System.out.println("Reads the sun from " + toTime(readTimes[charlie][sun]) + " until " + toTime(endTimes[charlie][sun]));
System.out.println("\nDigby");
System.out.println("----------");
System.out.println("Wakes up at " + toTime( studentWakeupTimes[digby]));
System.out.println("Reads the guardian from " + toTime(readTimes[digby][guardian]) + " until " + toTime(endTimes[digby][guardian]));
System.out.println("Reads the ft from " + toTime(readTimes[digby][ft]) + " until " + toTime(endTimes[digby][ft]));
System.out.println("Reads the express from " + toTime(readTimes[digby][express]) + " until " + toTime(endTimes[digby][express]));
System.out.println("Reads the sun from " + toTime(readTimes[digby][sun]) + " until " + toTime(endTimes[digby][sun]));
}
public static IntVar[] getArrayColumn(IntVar [][] array, int column) {
// A quick function to get a column of a 2D array as a 1D array
IntVar [] col = new IntVar[array.length];
for (int i = 0; i < array.length; i++) {
col[i] = array[i][column];
}
return col;
}
public static String toTime(IntVar var) {
// I haven't figure out how to just pull the value from an IntVar, so this does it using string splitting
int val;
String ret = "";;
String [] spl = var.toString().split(":");
val = Integer.parseInt(spl[1]);
int hour = val / 60;
int min = val % 60;
String Min;
if (min < 10) Min = "0" + min;
else Min = new Integer(min).toString();
ret = hour + ":" + Min;
return ret;
}
}
[edit] Output
Schedule: ========== Algy ---------- Wakes up at 8:30 Reads the guardian from 8:30 until 9:00 Reads the ft from 9:30 until 10:30 Reads the express from 9:00 until 9:02 Reads the sun from 9:25 until 9:30 Bertie ---------- Wakes up at 8:45 Reads the guardian from 9:25 until 10:40 Reads the ft from 8:45 until 9:10 Reads the express from 9:10 until 9:13 Reads the sun from 9:15 until 9:25 Charlie ---------- Wakes up at 8:45 Reads the guardian from 10:40 until 10:55 Reads the ft from 9:15 until 9:25 Reads the express from 9:25 until 9:30 Reads the sun from 8:45 until 9:15 Digby ---------- Wakes up at 9:30 Reads the guardian from 11:00 until 11:01 Reads the ft from 11:01 until 11:02 Reads the express from 11:02 until 11:03 Reads the sun from 9:30 until 11:00
