Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing
Recently, the importance of correctly designed computational experiments for testing algorithms has been a subject of extended discussions. Whenever real-world data is lacking, generated data sets provide a substantive methodological tool for experiments. Focused research questions need to base on specialized, randomized and sufficiently large data sets, which are sampled from the population of interest. We integrate the generation of data sets into the process of scientific testing. Until now, no appropriate generators or systematic data sets have been available for the assembly line balancing problem (ALBP). Computational experiments were mostly based on very limited data sets unsystematically collected from the literature and from some real-world cases. As a consequence, former performance analyses often come to contradictory conclusions and lack on statistical evidence. We introduce SALBPGen, a new instance generator for the simple ALBP which can be applied and extended to any generalized ALBP, too. Unlike most generators, SALBPGen takes into account usual properties of precedence graphs in manufacturing. It is very flexible and able to create instances with very diverse structures under full control of the experiments designer. We also propose new challenging data sets, as shown with the new direct measure of instances hardness called trickiness. By two exemplary computational experiments, we illustrate how important insights can be gained with the help of the systematically generated data sets.
assembly line balancing precedence graph scheduling benchmark data set structure analysis complexity measures