An iterative exact algorithm for the weighted fair sequences problem

Markus Sinnl

doi:10.1016/j.cor.2022.106017

Return

An iterative exact algorithm for the weighted fair sequences problem

2022-12-01

Markus Sinnl *

DOI：10.1016/j.cor.2022.106017

Original

Save

View PDF

Abstract

En 中文

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.

Keywords:

Scheduling problem

Mixed-integer programming

Sequencing problem

Iterative algorithm

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.