|
Research > Scheduling > Aircraft Assembly
Aircraft
Assembly
An employee of a well known manufacturing company has made
a large scheduling problem available over the net in order
to encourage academic researchers to demonstrate the applicability
of their techniques on realistic scheduling problems. This
particular problem is relevant to large scale assembly and
is an instance of a class of problems known as resource constrained
project scheduling (RCPS).
CIRL has developed a scheduler that produces the best known
results on this problem. On Time Systems has extended this
scheduler to handle more general aircraft manufacturing
problems involving more complicated resource types and constraints.
We have also converted several other benchmark problems
to the same format and solved them successfully.
The
basic aircraft assembly problem has these features:
- Zone
resources. A zone is an area of the aircraft in which
work can be done. Zone resources specify the maximum number
of people that can work in that zone at the same time.
- Labor
resources. These specify how many laborers are available
with a particular skill set.
- Shifts.
The availability of labor resources varies over time,
with more being available during the day.
- Tasks.
Tasks have a specified duration and set of zone and labor
resources that are needed to perform the task.
- Precedences.
These specify which tasks must be completed before other
tasks can begin.
The program uses limited discrepancy search (LDS) and schedule
packing (also known as doubleback optimization) to generate
solutions. LDS and schedule packing can be used in isolation
or in combination with each other. The best results are
generally produced using LDS with schedule packing or schedule
packing on its own. When used in combination, multiple seed
schedules generated with LDS are fed to schedule packing.
In the figures below, the top part indicates resource usage
over time. There is one horizontal bar for each of the 17
resources in this problem. Red indicates a resource is fully
utilized, and green indicates it is unused. The boxes in
the bottom part of the figures represent the tasks. The
width of a box represents the duration of a task, and the
height is an indicator of how many resources a task requires.
A task's color indicates where the task starts in the PERT
schedule for this problem. The alternating gray and black
vertical bars in the background represent the day and night
shifts.
This figure shows the PERT schedule for the problem. In
PERT schedules, precedences are honored, but resource constraints
are not. Each blue rectangle in the top area of this solution
indicates an overallocated resource for that period of time.
This PERT schedule ends after 37 days, 2 hours and 58 minutes,
and is a loose lower bound on the minimum length any solution
to this problem can have.
The next figure shows a typical best solution that is found
within the first 400 iterations of schedule packing. It
ends after 40 days, 7 hours and 13 minutes. This schedule
has no overallocated resources and all of the blue areas
in the PERT schedule have disappeared. Also note that many
of the tasks that were early in the PERT schedule (yellow
tasks) have shifted over to much later in the schedule.
These tasks are relatively unconstrained in their precedence
relationships with other tasks.
The last figure shows a solution that we believe is optimal
for this problem. This ends after 39 days, 5 hours and 5
minutes. Solutions of this length are produced by about
10% of schedule packing runs that are allowed to run for
200,000 iterations (about 45 minutes on a 333 MHz Pentium
II).
|
