Modeling and solving a simple problem: house building

Step 1: Describe the problem

The first step in modeling and solving the problem is to write a natural language description of the problem, identifying the decision variables and the constraints on these variables.

Write a natural language description of this problem. Answer these questions:

• What is the known information in this problem?

• What are the decision variables or unknowns in this problem?

• What are the constraints on these variables?

• What is the objective?

Discussion

What is the known information in this problem?

• There are ten house building tasks, each with a given duration. For each task, there is a list of tasks that must be completed before the task can start. Some tasks also have costs associated with an early start date or late end date.

What are the decision variables or unknowns in this problem?

• The unknowns are the date that each task will start. The cost is determined by the assigned start dates.

What are the constraints on these variables?

• In this case, each constraint specifies that a particular task may not begin until one or more given tasks have been completed.

What is the objective?

• The objective is to minimize the cost incurred through earliness and tardiness costs.

Step 2: Open the example file

• Still working with the scheduling_tutorial project, open the sched_time.mod file in the IDE editing area.

This file is an OPL model that is only partially completed. You will add the missing code in each step of this lesson. At the end, you will have completed the OPL model. IBM ILOG OPL gives you the means to represent the unknowns in this problem, the interval in which each task will occur, as interval variables.

In your model, you first declare the interval variables, one for each task. Each variable represents the unknown information, the scheduled interval for each activity. After the model is executed, the values assigned to these interval variables will represent the solution to the problem.

For example, to create an interval with size 35 in OPL:

  dvar interval masonry size 35;

Step 3: Declare the interval variables

Add the following code after the comment //Declare the interval variables:

dvar interval masonry    size 35;
dvar interval carpentry  size 15;
dvar interval plumbing   size 40;
dvar interval ceiling    size 15;
dvar interval roofing    size 5;
dvar interval painting   size 10;
dvar interval windows    size 5;
dvar interval facade     size 10;
dvar interval garden     size 5;
dvar interval moving     size 5;

In this example, certain tasks can start only after other tasks have been completed. IBM ILOG OPL allows you to express constraints involving temporal relationships between pairs of interval variables using precedence constraints.

Step 4: Add the precedence constraints

Add the following code after the comment //Add the precedence constraints:

  endBeforeStart(masonry,   carpentry);
  endBeforeStart(masonry,   plumbing);
  endBeforeStart(masonry,   ceiling);
  endBeforeStart(carpentry, roofing);
  endBeforeStart(ceiling,   painting);
  endBeforeStart(roofing,   windows);
  endBeforeStart(roofing,   facade);
  endBeforeStart(plumbing,  facade);
  endBeforeStart(roofing,   garden);
  endBeforeStart(plumbing,  garden);
  endBeforeStart(windows,   moving);
  endBeforeStart(facade,    moving);
  endBeforeStart(garden,    moving);
  endBeforeStart(painting,  moving);

To model the cost for starting a task earlier than the preferred starting date, you use the expression startOf that represents the start time of an interval variable as an integer expression.

For each task that has an earliest preferred start date, you determine how many days before the preferred date it is scheduled to start using the expression startOf; this expression can be negative if the task starts after the preferred date. By taking the maximum of this value and 0 using maxl, you determine how many days early the task is scheduled to start. Weighting this value with the cost per day of starting early, you determine the cost associated with the task.

The cost for ending a task later than the preferred date is modeled in a similar manner using the expression endOf. The earliness and lateness costs can be summed to determine the total cost.

Step 5: Add the objective

Add the following code after the comment //Add the objective:

minimize 400 * maxl(endOf(moving) - 100, 0)     +
         200 * maxl(25 - startOf(masonry), 0)   +
         300 * maxl(75 - startOf(carpentry), 0) +
         100 * maxl(75 - startOf(ceiling), 0);

Step 6: Execute and display the solution

After a solution has been found, you can use the start and end properties of the interval variables to access the assigned intervals. The code for displaying the solution has been provided for you:

execute {
  writeln("Masonry  : " + masonry.start   + ".." + masonry.end);
  writeln("Carpentry: " + carpentry.start + ".." + carpentry.end);
  writeln("Plumbing : " + plumbing.start  + ".." + plumbing.end);
  writeln("Ceiling  : " + ceiling.start   + ".." + ceiling.end);
  writeln("Roofing  : " + roofing.start   + ".." + roofing.end);
  writeln("Painting : " + painting.start  + ".." + painting.end);
  writeln("Windows  : " + windows.start   + ".." + windows.end);
  writeln("Facade   : " + facade.start    + ".." + facade.end);
  writeln("Garden   : " + garden.start    + ".." + garden.end);
  writeln("Moving   : " + moving.start    + ".." + moving.end);
}

Step 7: Run the model

Run the model. You should get the following results:

OBJECTIVE: 5000
Masonry  : 20..55
Carpentry: 75..90
Plumbing : 55..95
Ceiling  : 75..90
Roofing  : 90..95
Painting : 90..100
Windows  : 95..100
Facade   : 95..105
Garden   : 95..100
Moving   : 105..110

As you can see, the overall cost is 5000 and moving will be completed by day 110.

You can also view the complete program online in the <Install_dir>/opl/examples/opl/sched_time/sched_time.mod file.