Abstract:

In this work, we present a new iterative exact solution algorithm for a recently introduced NP-hard sequencing problem. In the problem we are given an upper bound on the allowed solution sequence length and a list of symbols. For each symbol, there is a positive weight and a number, which gives the minimum amount of times the symbol has to occur in a feasible solution sequence. The goal is to find a feasible sequence, which minimizes the maximum weight-distance product, which is calculated for each consecutive appearance of each symbol in the sequence, including the last and first appearance in the sequence, i.e., the sequence is considered to be circular for the calculation of the objective function.

Our proposed solution algorithm is based on a new mixed-integer programming model for the problem with a fixed sequence length. We also present various enhancements for our algorithm. We conduct a computational study on the instances from literature to assess the efficiency of our newly proposed solution approach. Our approach solves 404 of 440 instances to optimality within the given time limit, most of them within five minutes. The previous best existing solution approach for the problem only solves 229 of these instances and its exactness depends on an unproven conjecture. Moreover, our approach is up to two orders of magnitude faster compared to this best existing solution approach.