Describe
The first stage in finding a solution to the house building with worker allocation problem is to describe the problem using natural language.
The problem consists of assigning start dates to a set of tasks in such a way that the schedule satisfies temporal constraints and minimizes an expression. The objective for this problem is to maximize the task associated skill levels of the workers assigned to the tasks.
For each task type in the house building project, the following table shows the duration of the task in days along with the tasks that must be finished before the task can start. A worker can only work on one task at a time; each task, once started, may not be interrupted.
| Task | Duration | Preceding tasks |
|---|---|---|
| masonry | 35 | |
| carpentry | 15 | masonry |
| plumbing | 40 | masonry |
| ceiling | 15 | masonry |
| roofing | 5 | carpentry |
| painting | 10 | ceiling |
| windows | 5 | roofing |
| facade | 10 | roofing, plumbing |
| garden | 5 | roofing, plumbing |
| moving | 5 | windows, facade, garden, painting |
All of the houses must be completed by a deadline of day 318. There are three workers with varying skill levels in regard to the ten tasks. If a worker has a skill level of zero for a task, he may not be assigned to that type of task.
| Task | Joe | Jack | Jim |
|---|---|---|---|
| masonry | 9 | 5 | 0 |
| carpentry | 7 | 0 | 5 |
| plumbing | 0 | 7 | 0 |
| ceiling | 5 | 8 | 0 |
| roofing | 6 | 7 | 0 |
| painting | 0 | 9 | 6 |
| windows | 8 | 0 | 5 |
| facade | 5 | 5 | 0 |
| garden | 5 | 5 | 9 |
| moving | 6 | 0 | 8 |
For Jack, if he performs roofing or facade on a house, then he must perform the other on that house. For Jim, if he performs garden or moving on a house, then he must perform the other on that house. For Joe, if he performs masonry or carpentry on a house, then he must perform the other on that house. Also, if Joe performs carpentry or roofing on a house, then he must perform the other on that house.
Solving the problem consists of determining starting dates for the tasks and assigning a worker to each task such that sum of the skill levels used for the tasks is maximized.
Step 1: Describe the problem
The first step in modeling and solving a 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 five houses to be built by three workers. For each house, there are ten house building tasks, each with a given size. For each task, there is a list of tasks that must be completed before the task can start. Each worker has a skill level associated with each task. There is an overall deadline for the work to be completed on the five houses.
What are the decision variables or unknowns in this problem?
The unknowns are the dates that the tasks will start. Also, unknown is which worker will be assigned to each task.
What are the constraints on these variables?
There are constraints that specify that a particular task may not begin until one or more given tasks have been completed. In addition, there are constraints that specify that each task must have one worker assigned to it, that a worker can be assigned to only one task at a time and that a worker can be assigned only to tasks for which he has some level of skill. There are pairs of tasks that if one for a house is done by a particular worker, then the other for that house must be done by the same worker.
What is the objective?
The objective is to maximize the skill levels used.