CIRL has developed a scheduler that produces the best known results on this problem. We have also converted several other benchmark problems to the same format and solved them successfully.
The aircraft assembly problem has these features:
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).
