K.U.Leuven - Departement toegepaste economische wetenschappen
DTEW Research Report 09505 pages:1-32
Numerous optimal and suboptimal procedures have been developed for solving the simple assembly line balancing problem (SALBP). The similarity between the SALBP and the problem of scheduling project network activities under renewable resource constraints has been noted in many writings. In this paper we exploit the similarity between the SALBP and the generalized resource-constrained project scheduling problem (GRCPSP) by studying two GRCPSP-based formulations for the SALBP. Both formulations assume a single renewable resource. The first formulation assumes finish-start precedence constraints, unit resource requirements and varying resource availability. The second formulation assumes start-start precedence relations, unit activity durations and constant resource availability. The possibility of optimally solving the SALBP is explored by comparing the performance of a branch-and-bound procedure for the GRCPSP for both problem settings with the performance of dedicated SALBP procedures on an extensive set of problem instances. Extensive conclusions are obtained on the potential of various complexity measures for explaining variations in the CPU time required for solving SALBP instances.