The efficient utilization of scarce resources, such as machines or
manpower, is major challenge within production planning in the
chemical industry. We describe solution methods for a
resource-constrained scheduling problem which arises at a production
facility at BASF AG in Ludwigshafen. We have developed and
implemented two different algorithms to solve this problem, a novel
approach which is based upon Lagrangian relaxation, as well as a
branch-and-bound procedure.
Since the Lagrangian approach is applicable for a whole variety of
resource-constrained scheduling problems, it is of interest not only
for the specific problem we describe, but is of interest also for
many other industrial applications. In this paper, we describe both
approaches, and also report on computational results, based upon
practical problem instances as well as benchmark test sets.
