SALBLIB : challenging instances for assembly line balancing

In this paper an improved set of benchmark instances for the simple assembly line balancing problem is presented. The benchmark set currently available consists of instances with 7 to 297 tasks to be executed. Although claims made in the literature state that instances with up to 1000 tasks can be solved to optimality (less than) ten instances of these benchmark sets are still unsolved. The majority of the unsolved instances consists of 297 tasks, and the smallest unsolved instance consists of only 75 tasks. On the one hand the instance set is very heterogenous, and on the other hand, the instances are, at least partly, highly correlated through identical networks and processing times. Consequently, the available set is not suited that well to analyze the performance of heuristic and exact algorithms experimentally. This paper presents a generator that allows the systematic generation of benchmark instances, and thus the systematic evaluation of algorithmic performance. In this paper new systematically generated benchmark instances are presented. The instance generator employs some features of the well-known program package ProGen, which has been developed for the generation of benchmark instances for the resource-constrained project scheduling problem. However, for the simple assembly line balancing problem the generation of the processing times of the tasks is of particular importance. The instances generated consist of 50, 75, and 100 tasks. The computational results obtained by one of the most efficient exact solution procedures are reported. The study reveals that even instances with 50 tasks cannot be solved to optimality within a reasonable amount of time. The instances as well as the lower and the upper bounds can be loaded from our web-server. Moreover, improved solutions can be submitted via e-mail. The solutions are checked and the library is updated accordingly. Depending on the progress made in the development of exact and heuristic solution procedures the library is enhanced and new benchmark instances are added.