# An iterative exact algorithm for the weighted fair sequences problem

Markus Sinnl<EMAIL_ADDRESS>Institute of Production and Logistics
Management/JKU Business School, Johannes Kepler University Linz, Linz, Austria

###### Abstract

In this work, we present a new iterative exact solution algorithm for the
weighted fair sequences problem, which is a recently introduced NP-hard
sequencing problem with applications in diverse areas such as TV advertisement
scheduling, periodic machine maintenance and real-time scheduling. In the
problem we are given an upper bound on the allowed solution sequence length
and a list of symbols. For each symbols, there is a positive weight and a
number, which gives the minimum 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 for a fixed sequence length. The model is enhanced with
valid inequalities and variable fixings. We also develop an extended model,
which allows the definition of an additional set of valid inequalities and
present additional results which can allow us to skip the solution of the
mixed-integer program for some sequence lengths.

We conduct a computational study on the instances from literature to assess
the efficiency of our newly proposed solution approach. Our approach manages
to solve 404 of 440 instances to optimality within the given timelimit, most
of them within five minutes. The previous best existing solution approach for
the problem only managed to solve 229 of these instances, and its exactness
depends on an unproven conjecture. Moreover, our approach is up to two
magnitudes faster compared to this best existing solution approach.

##  1 Introduction and motivation

Scheduling and sequencing problem are amongst the most important and well-
studied problems in Operations Research. In such problems, we are typically
given a set of tasks, which use up resources, and one or more machines, and we
have to allocate the tasks to the machine(s), while fulfilling constraints on
the allowed allocations (e.g., starting times, conflicts or dependencies
between tasks, …) and considering some objective function (e.g., minimize the
finishing time of the last task, …). For a general introduction to scheduling
and sequencing, we refer to the book (Brucker, 2004) and the recent surveys
(Allahverdi et al., 2008; Levner et al., 2010; Jiménez, 2013). In this paper,
we study the recently introduced _weighted fair sequences problem (WFS)_
(Pessoa et al., 2018), which is defined as follows.

Let $A=\\{a_{1},a_{2},\ldots a_{n}\\}$ be a set of $n$ symbols with a weight
function $w:A\rightarrow\mathbb{Z}^{+}$. Let $T$ be the maximum length of the
solution sequence and let $f_{i}$, $a_{i}\in A$ be minimum number of times
symbol $a_{i}$ must occur in the solution sequence. A feasible solution to the
WFS consists of a sequence $S=s_{1},s_{2},\ldots,s_{T^{\prime}}$ with
$T^{\prime}\leq T$ and $s_{i}\in A$, such that each symbol $a_{i}$ occurs at
least $f_{i}$ times in $S$. The objective function value is based on a
circular distance function. Let
$a_{i}(S)=(p^{1}_{a_{i}},p^{2}_{a_{i}},\ldots,p^{k}_{a_{i}})$ be the ordered
list of positions in sequence $S$, where symbol $a_{i}$ occurs. For each
consecutive pair of entries $p^{\ell}_{a_{i}},p^{\ell+1}_{a_{i}}$, the
distance
$dist(p^{\ell}_{a_{i}},p^{\ell+1}_{a_{i}})=p^{\ell+1}_{a_{i}}-p^{\ell}_{a_{i}}$
is calculated, moreover, the distance
$dist(p^{k}_{a_{i}},p^{1}_{a_{i}})=T^{\prime}+p^{1}_{a_{i}}-p^{k}_{a_{i}}$ is
also calculated. Note that this last distance-calculation can also be seen as
calculation between consecutive pairs in $a_{i}(S)$ by considering the
sequence $S$ to be circular. Let $D_{i}$ be the maximum of these distances for
$a_{i}\in A$. The goal is to find a sequence $S^{*}$ which minimizes
$w(a_{i})D_{i}$, $a_{i}\in A$ (i.e., the weight-distance-product).

Figure 1 shows two solutions of an instance of the WFS. The solution sequences
are displayed in a circular fashion to give an easy illustration of the
circular objective function. The figure shows how placing a symbol $a_{i}$ in
a sequence in a larger number than required by $f_{i}$ can improve the
objective function value.

$a_{2}$$a_{1}$$a_{5}$$a_{4}$$a_{3}$[1,2],$a_{2}$,$a_{1}$,$a_{5}$,$a_{4}$,$a_{3}$,,,[2,3],$a_{2}$,$a_{1}$,$a_{5}$,$a_{4}$,$a_{3}$,,,
(a) Solution with objective value $50$ (due to $w(a_{1})D_{1}$ and
$w(a_{2})D_{2}$)

$a_{2}$$a_{1}$$a_{3}$$a_{5}$$a_{2}$$a_{1}$$a_{4}$$a_{3}$[1,2],$a_{2}$,$a_{1}$,$a_{3}$,$a_{5}$,$a_{2}$,$a_{1}$,$a_{4}$,$a_{3}$,,,[2,3],$a_{2}$,$a_{1}$,$a_{3}$,$a_{5}$,$a_{2}$,$a_{1}$,$a_{4}$,$a_{3}$,,,
(b) Optimal solution, objective value $48$ (due to $w(a_{4})D_{4}$)

Figure 1: Two solutions for an instance of the WFS with
$A=\\{a_{1},a_{2},a_{3},a_{4},a_{5}\\}$, $T=10$, $f_{i}=1,a_{i}\in A$ and
$w(a_{1})=10$, $w(a_{2})=10$, $w(a_{3})=7$, $w(a_{4})=6$, $w(a_{5})=3$.

The WFS is NP-hard (Pessoa et al., 2018) and falls within the class of
scheduling problems, which are concerned with the proportional sharing of
resources over time. In these so-called _fair sequencing problems_ (Kubiak,
2004), the same tasks are executed successively, and the goal is to obtain a
schedule fulfilling certain _fairness criteria_ , e.g., the (temporal)
distance of successive executions of the same tasks should be similar for all
type of considered tasks. They play an important role in Just-In-Time
manufacturing systems such as the ones used by Toyota, who were among the
first to realize the potential of fair sequences in a production context, as
it helped to ”smooth out” the usage rate of all parts of their assembly line
(Kubiak, 2004; Monden, 2011). Moreover, the concept of _fair sequences_ also
has interesting applications in the area of political representation
(Tijdeman, 1980) and resource allocation in computer operating systems
(Waldspurger and Weihl W., 1995). Additional applications of the WFS discussed
in (Pessoa et al., 2018) include TV advertising (Bar-Noy and Ladner, 2003;
García-Villoria and Salhi, 2015) and periodic machine maintenance (Anily et
al., 1998; Bar-Noy et al., 2002).

###  1.1 Contribution and outline

In this paper, we introduce a new iterative exact algorithm for the WFS. The
algorithm is based on a new mixed-integer programming (MIP) model for the WFS
for sequences which have exactly length $\mathcal{T}$. In Section 2 we
describe our solution algorithm, including the MIP model, and also present
valid inequalities and variable fixing procedures for the MIP model. An
extended MIP model using additional variables is also developed and additional
algorithmic enhancements are discussed. In Section 3 we present a
computational study using the instances from Pessoa et al. (2018). The results
show that our algorithm outperforms the algorithm from Pessoa et al. (2018) by
up two orders of magnitude. We are able to solve 404 of 440 instances from
literature to proven optimality, most of them within fives minutes. Section 4
concludes the paper. In the remainder of this section, we give a short
overview of the model and algorithms for the WFS proposed in Pessoa et al.
(2018).

###  1.2 The solution approach of Pessoa et al. (2018)

In Pessoa et al. (2018) a MIP model for the problem is introduced. As the
model has a very large number of variables and constraints the authors also
propose an alternative solution approach, in which a reduced version of their
MIP model is solved iteratively.

Their MIP model has nine different sets of variables and can be viewed as a
combination of a model calculating the distances within the same cycle, and a
model calculating the distances between different cycles. The first part
consists of nine different set of constraints, and the second part consists of
seven different sets of constraints, not counting binary constraints on
variables. To reduce the size of the model, the authors introduce a nonlinear
MIP model which can provide an upper bound on the number of copies for each
symbol in the optimal solution. This upper bound can be used to reduce the
number of variables in their model. However, their MIP model for the WFS after
applying the variable-reduction is still too large to be effective in
computations, even after adding some valid inequalities proposed by the
authors. Thus they also develop an iterative solution approach, which is based
on an estimated upper bound for the optimal solution value. With this
estimated upper bound, the number of variables can be further reduced in
combination with their nonlinear MIP model. The iterative algorithm starts
with an initial upper bound, and then tries to solve their MIP model with this
estimated upper bound set as cutoff for the objective function value. If the
problem with the cutoff is feasible, the optimal solution will be the optimal
solution for the WFS problem. If not, the estimated upper bound is increased,
and the procedure repeated. This is done iteratively until either the optimal
solution is found at some point, or a given iteration limit is reached. We
note that in the main computations in Pessoa et al. (2018), the used MIP model
contains a set of inequalities for which the authors only conjectured
validity, but did not prove it. Thus the reported results of Pessoa et al.
(2018) can only be considered heuristic in nature until validity of this
inequality is proven.

##  2 Solution algorithm

Our solution algorithm is described in Algorithm 1.

1 $z^{*}\leftarrow\infty$

2 for  _$\sum_{a_{i}\in A}f_{i}\leq\mathcal{T}\leq T$_ do

3 $z^{\prime}\leftarrow$ optimal value for WFS with fixed sequence length
$\mathcal{T}$

4 if  _$z^{\prime} <z^{*}$_ then

5 $z^{*}\leftarrow z^{\prime}$

6

Algorithm 1 Iterative solution algorithm for the WFS.

The algorithm iteratively solves the WFS for a fixed sequence length
$\mathcal{T}$, and iterates over all possible $\mathcal{T}$, i.e.,
$\sum_{a_{i}\in A}f_{i}\leq\mathcal{T}\leq T$. To do so, the MIP model
described in Section 2.1 is used. The model can be strengthened throughout the
algorithm by information from previous iterations, this is discussed, among
other possible strengthenings of the model, in Section 2.2. Moreover, we also
present some results in Section 2.2 which allow us to skip solving the WFS for
some $\mathcal{T}$.

By considering a fixed $\mathcal{T}$ the modeling of the problem can be
simplified, allowing for a model with a much smaller number of variables and
constraints compared to the model used in Pessoa et al. (2018) (including
their reduced variant they use in their iterative algorithm). We note that
there also exist other problems where fixing a certain dimension of the
problem and then reformulating the problem and solving the reformulated
problem in an iterative fashion leads to a more effective solution approach
compared to directly solving the problem, see, e.g., Chen and Chen (2009);
Contardo et al. (2019); Sinnl (2020).

###  2.1 MIP model for a fixed sequence length $\mathcal{T}$

Let binary variables $x_{i}^{t}$, $a_{i}\in A,t=1,\ldots,\mathcal{T}$ indicate
if symbol $a_{i}$ gets placed at position $t$ in the sequence. Let binary
variables $s_{i}^{t,t^{\prime}}$, $a_{i}\in A$, $1\leq
t,t^{\prime}\leq\mathcal{T}$ indicate that if symbol $a_{i}$ gets placed at
position $t$, the next occurrence of symbol $a_{i}$ is at position
$t^{\prime}$, considering a circular sequence. Let binary variables
$p_{i}^{t,t^{\prime}}$, $a_{i}\in A$, $1\leq t,t^{\prime}\leq\mathcal{T}$
indicate that if symbol $i$ gets placed at position $t$, the last occurrence
of symbol $i$ before $t$ is at position $t^{\prime}$, considering a circular
sequence. Note that these variables actually encode a relaxed version of the
described indications in our model, i.e., for some combinations of
$i,t,t^{\prime}$, $s$-variables or $p$-variables which do not correspond to
the next/last occurrence given the solution encoded by $x$ can be selected.
This does not matter, as these variables are used for measuring the objective
function value, and our objective function has a min/max-structure, thus only
certain $i,t,t^{\prime}$ need to be selected correctly (i.e., the ones
corresponding to symbols $a_{i}$ and positions $t,t^{\prime}$ causing the
maximum weight-distance-product for the sequence encoded by the
$x$-variables). More details on this is given below after the MIP model. Let
integer variable $\theta$ measure the objective function value. Let

$dist(t,t^{\prime})=\begin{cases}t-t^{\prime}&if\ t>t^{\prime}\\\
\mathcal{T}+t-t^{\prime}&otherwise.\end{cases}$

The WFS for a fixed sequence length $\mathcal{T}$ can be formulated as
follows.

$\displaystyle\min\quad$ $\displaystyle\theta$ (1) $\displaystyle\sum_{1\leq
t\leq\mathcal{T}}x^{t}_{i}$ $\displaystyle\geq f_{i}$
$\displaystyle\quad\forall a_{i}\in A$ (2) $\displaystyle\sum_{a_{i}\in
A}x^{t}_{i}$ $\displaystyle=1$ $\displaystyle\quad 1\leq t\leq\mathcal{T}$ (3)
$\displaystyle x^{t}_{i}-\sum_{1\leq
t^{\prime}\leq\mathcal{T}}p_{i}^{t,t^{\prime}}$ $\displaystyle=0$
$\displaystyle\quad\forall a_{i}\in A,1\leq t\leq\mathcal{T}$ (4)
$\displaystyle x^{t}_{i}-\sum_{1\leq
t^{\prime}\leq\mathcal{T}}s_{i}^{t,t^{\prime}}$ $\displaystyle=0$
$\displaystyle\quad\forall a_{i}\in A,1\leq t\leq\mathcal{T}$ (5)
$\displaystyle s_{i}^{t,t^{\prime}}-p_{i}^{t^{\prime},t}$ $\displaystyle=0$
$\displaystyle\quad\forall i\in A_{i},1\leq t,t^{\prime}\leq\mathcal{T}$ (6)
$\displaystyle\theta-\sum_{a_{i}\in A}\sum_{1\leq
t^{\prime}\leq\mathcal{T}}w(a_{i})dist(t,t^{\prime})p^{t,t^{\prime}}_{i}$
$\displaystyle\geq 0$ $\displaystyle 1\leq t\leq\mathcal{T}$ (7)
$\displaystyle\theta-\sum_{a_{i}\in A}\sum_{1\leq
t^{\prime}\leq\mathcal{T}}w(a_{i})dist(t^{\prime},t)s^{t,t^{\prime}}_{i}$
$\displaystyle\geq 0$ $\displaystyle 1\leq t\leq\mathcal{T}$ (8)
$\displaystyle x^{t}_{i}$ $\displaystyle\in\\{0,1\\}$
$\displaystyle\quad\forall a_{i}\in A,1\leq t\leq\mathcal{T}$ $\displaystyle
p^{t,t^{\prime}}_{i}$ $\displaystyle\in\\{0,1\\}$ $\displaystyle\quad\forall
a_{i}\in A,1\leq t,t^{\prime}\leq\mathcal{T}$ $\displaystyle
s^{t,t^{\prime}}_{i}$ $\displaystyle\in\\{0,1\\}$ $\displaystyle\quad\forall
a_{i}\in A,1\leq t,t^{\prime}\leq\mathcal{T}$

Constraints (2) ensure that each symbol $a_{i}\in A$ is appearing in the
sequence at least $f_{i}$-times. Constraints (3) ensure that each position in
the sequence only get assigned a single symbol. Constraints (4) and (5) ensure
that for each placed symbol in the sequence at a certain position, an
indicator-variables for the next and previous occurrence of the symbol is
selected. Constraints (6) link the $s$-variables with the $p$-variables. Note
that constraints (4), (5), (6) only enforce that for each symbol $a_{i}$
placed at a position $t$, some position $t^{\prime}$, where symbol $a_{i}$ is
also placed is defined as ”predecessor” and ”successor”. However, on their
own, they do not enforce that these selected positions are the truly the
previous/next occurrence of the symbol in the solution sequence. In fact, our
model does not enforce that this must hold for all the $s$-variables and
$p$-variables, but only for the symbol-position-combinations causing the
largest weight-distance-product value for the sequence encoded by the
$x$-variables. As the objective in the WFS is concerned with minimizing the
maximum weight-distance-product, this is enough to solve the problem to proven
optimality. The two set of constraints (7) and (8), together with the
minimization objective function ensure that this value is measured correctly.
For each position $1\leq t\leq\mathcal{T}$, in the sequence, constraint (7)
measure the weight-distance-product induced by the symbol $a_{i}$ placed at
this position $t$, and the position $t^{\prime}$ encoded as predecessor
position by $p^{t,t^{\prime}}_{i}$, and ensure that $\theta$ takes at least
this value. Now suppose that there is a solution
$(x^{*},s^{*},p^{*},\theta^{*})$, where $p^{*t,t^{\prime}}_{i}$ is not
selected in such a way that $t^{\prime}$ is the predecessor position for the
symbol placed at position $t$ for a constraint (7) fulfilled with equality by
$(x^{*},s^{*},p^{*},\theta^{*})$. Clearly, another feasible solution
$(x^{*},s^{\prime},p^{\prime},\theta^{\prime})$ also exists, where $p^{\prime
t,t^{\prime}}_{i}$ is selected in such a way that $t^{\prime}$ is the
predecessor position for the symbol placed at position $t$ for this
constraint, and $\theta^{\prime}\leq\theta^{*}$, as the selection of
$p^{\prime t,t^{\prime}}_{i}$ in such a way makes the sum in (7) as small as
possible. As the objective function consists of minimizing $\theta$, this
ensures that for all constraints (7) fulfilled with equality in a solution the
$p$-variables are selected correctly, and thus the objective is measured
correctly. Constraints (8) do the same for the $s$-variables and the
successors in the sequence.

###  2.2 Valid inequalities, variable fixings and other enhancements for the
solution algorithm

The following set of inequalities is valid for our MIP model in the sense that
there exists at least one optimal solution fulfilling it.

######  Obervation 1.

Let $M_{i}$ be an upper bound one the number of times symbol $a_{i}$ can occur
in an optimal solution. Then the inequality

$\sum_{1\leq t\leq\mathcal{T}}x^{t}_{i}\leq M_{i}$ (9)

is valid for all $a_{i}\in A$.

As the upper bound $M_{i}$ the value $min(\mathcal{T}/2,\mathcal{T}-n-1)$ can
be used, which is an upper bound for which at least one optimal solution to
the WFS exists, see Pessoa et al. (2018). This upper bound is based on the
observation that there exists an optimal solution, in which no symbol $a_{i}$
will be placed at both position $t$ and $t+1$ (including the
$\\{\mathcal{T},1\\}$ combination of positions).

This observation of Pessoa et al. (2018) can also be used to fix some of the
$s$-variables and $p$-variables. Correctness of this fixing follows from the
fact that a value of one for these variables would mean that a symbol $a_{i}$
is placed at two consecutive positions in the sequence.

######  Obervation 2.

All variables $p^{t,t^{\prime}}_{i},s^{t,t^{\prime}}_{i}$ with
$|t-t^{\prime}|=1$ can be fixed to zero. Moreover, variables
$p^{1,\mathcal{T}}_{i},s^{1,\mathcal{T}}_{i}$ and
$p^{\mathcal{T},1}_{i},s^{\mathcal{T},1}_{i}$ can also be fixed to zero.

The next observation describes some variable fixings which can be done in our
MIP model given an upper bound $z^{*}$ for the optimal solution value of an
WFS instance

######  Obervation 3.

Let $z^{*}$ be a given upper bound on the optimal solution value of a WFS
instance. Then all variables $p^{t,t^{\prime}}_{i}$ with
$w(a_{i})dist(t,t^{\prime})\geq z^{*}$ and all variables
$s^{t,t^{\prime}}_{i}$ with $w(a_{i})dist(t^{\prime},t)\geq z^{*}$ can be
fixed to zero.

Note that we assume that we also have a feasible solution $S(z^{*})$
associated with this upper bound, e.g., in the context of an iteration of our
algorithm, this is the best solution found in the previous iterations. As
initial solution before the first iteration, any heuristic solution can be
used. In our approach, we use the trivial solution, which just puts $f_{1}$
copies of symbol $a_{1}$ at the beginning of the sequence, followed by $f_{2}$
copies of symbol $a_{2}$ and so on.

With a feasible solution available, we can pose constraints such as the one in
Observation 3 that in the subsequent iterations only solutions which improve
the objective value compared to $z^{*}$ are feasible. This avoids the search
for an optimal solution for the MIP in an iteration with a $\mathcal{T}$,
where no improving solution can be found. In fact, we also implicitly add a
constraint such that only solutions where the solution value $\theta$ improves
on $z^{*}$ are feasible. To do so, we calculate
$\theta(z^{*})=\max\\{\theta^{\prime}:k_{i}\geq
f_{i},w(a_{i})k_{i}<z^{*},w(a_{i})k_{i}<\theta^{\prime},\forall a_{i}\in
A;k\in\mathbb{N}^{n}\\}$, i.e., we look for the maximum positive integer
multiple of the weights which is smaller than the current $z^{*}$ and add
$\theta\leq\theta(z^{*})$ to our MIP. When these constraints only allowing
improved solutions are added to the MIP, in line 1 of our algorithm, we will
either get that the MIP is infeasible, or if it is feasible, we are sure to
have found an improved solution.

Given an upper bound $z^{*}$ for the optimal solution value of an WFS
instance, we can also potentially lift constraints (2) by increasing the
right-hand-side of them.

######  Obervation 4.

Let
$k^{*}_{i}=\min\\{k_{i}:w(a_{i})\lceil\mathcal{T}/k_{i}\rceil<z^{*};k_{i}\geq
f_{i};k_{i}\in\mathbb{N}\\}$. As we want to find an improving solution, we can
set $f_{i}=k_{i}$ on the right-hand-side of constraints (2).

###### Proof.

Suppose in a solution we would place symbol $a_{i}$ $k_{i}$-times in a
sequence $S$, i.e., $|a_{i}(S)|=k_{i}$. Then the best possible distance (i.e.,
the minimal possible maximal distance between all its consecutive occurrences)
for this symbol in any solution sequence is
$D^{\prime}_{i}=\lceil\mathcal{T}/k_{i}\rceil$. This value is achieved by
evenly distributing the placement of the symbol in the sequence. Due to the
circular distance function, any non-even distribution would lead to a minimal
maximal distance as least as large as can be seen by an exchange argument. ∎

The next observation is based on Observation 4 and can allow us to conclude
for a given $\mathcal{T}$ that there can be no improving solution without the
need of solving our MIP.

######  Obervation 5.

Let $K^{*}=\sum_{a_{i}\in A}k^{*}_{i}$. If $K^{*}>\mathcal{T}$ then there
exists no improving solution with sequence length $\mathcal{T}$.

Observation 4 also allows us to lift the right-hand-side of valid inequalities
9.

######  Obervation 6.

For a given $a_{i}\in A$, let $M^{*}_{i}=\mathcal{T}-K^{*}+k^{*}_{i}$. Then an
improving solution fulfills

$\sum_{1\leq t\leq\mathcal{T}}x^{t}_{i}\leq M^{*}_{i}$ (10)

###### Proof.

Suppose there are more than $M^{*}_{i}$ copies of symbol $a_{i}$ in a
sequence. Then there are only less than $\mathcal{T}-M^{*}_{i}$ positions
available for the other symbols, but we need $\sum_{a^{\prime}_{i}\in
A:a^{\prime}_{i}\neq a_{i}}k^{*}_{i}\geq\mathcal{T}-M^{*}_{i}$ for the
existence of an improving solution. ∎

Due to the structure of the WFS, there can be many symmetric solutions, i.e.,
if there are two or more symbols with the same $f_{i}$ and $w(a_{i})$-values,
they can be exchanged in a solution without changing the solution value.
Moreover, due to the circular distance function, any solution which is
obtained by shifting the positions of all the symbols in the solution has the
same objective function value. To break these symmetries, we propose to use
the following two sets of constraints. For posing these constraints, without
loss of generality, we assume that the symbols are ordered in descending order
by $w$, and if there are multiple symbols with the same way, these symbols are
ordered in descending order by $f$. First, we fix that the symbol $a_{1}$ must
be placed in the first position of the sequence, i.e.,

$x^{1}_{1}=1,$ (11)

to deal with the rotational symmetry of our solutions. Moreover, we impose an
ordering on the symbols with the same $w(a_{i})$ and $f_{i}$ values to deal
with the exchange-symmetry, this is done with the following constraints

$\sum_{1\leq t\leq\mathcal{T}^{\prime}}x^{t}_{\ell}\geq
x^{t}_{\ell+1}\quad\forall a_{\ell}\in
A\setminus\\{a_{n}\\}:w(a_{\ell})=w(a_{\ell+1}),f_{\ell}=f_{\ell+1},1\leq
t\leq\mathcal{T}.$ (12)

They ensure that for two symbols $a_{\ell}$, $a_{\ell+1}$ with the same
$w(a_{i})$ and $f_{i}$ values, the one with smaller index must be placed first
in the solution sequence.

Next, we present another set of valid inequalities, which are based on an
extended model, i.e., a model with an additional set of variables. Let binary
variables $d_{i}^{j}$, $a_{i}\in A$, $1\leq j\leq M^{*}_{i}$ indicate the
number of times symbol $a_{i}$ is appearing in the sequence $S$ encoded by the
$x$-variables. The following constraints link the $x$-variables and the
$d$-variables.

$\sum_{1\leq t\leq\mathcal{T}}x^{t}_{i}-\sum_{1\leq j\leq
M^{*}_{i}}jd^{j}_{i}=0\quad\forall a_{i}\in A$ (13)

With these $d$-variables, we can pose the following set of constraints (14),
which encode the connection between the number $k_{i}=|a_{i}(S)|$ of
occurrences of a symbol $a_{i}$ in a sequence $S$ and the minimal possible
weight-distance product induced by $a_{i}$, using the
$D^{\prime}_{i}=\lceil\mathcal{T}/k_{i}\rceil$ relationship we discussed above
in connection with the lifting of inequalities (2).

######  Obervation 7.

Let $z^{*}$ be an upper bound on the objective value of an WFS instance. Then
the following inequalities are valid for our model extended with constraints
(13).

$P-z^{*}+\sum_{1\leq j\leq M_{i}:w(a_{i})\lceil\mathcal{T}/j\rceil\leq
z^{*}}(z^{*}-w(a_{i})\lceil\mathcal{T}/j\rceil)d^{j}_{i}\geq 0\quad\forall
a_{i}\in A$ (14)

##  3 Computational results

The solution algorithm was implemented in C++ and IBM ILOG CPLEX 12.10 was
used to solve the MIP models. The computations were made on a single core of
an Intel Xeon E5-2670v2 machine with 2.5 GHz and 3GB of RAM, and all CPLEX
settings were left on their default values.

###  3.1 Instances

We used the instances introduced in Pessoa et al. (2018), which are available
at https://sites.google.com/site/weightedfairsequencesproblem/instances. There
are two instance sets available at this site.

  * •

normal: This was the main set used in the computational study of Pessoa et al.
(2018). The instance set consists of ten instances for each combination of
$n=5,7,9,11,13,15$ (number of symbols) and $T=2n,3n,4n$, resulting in 180
instances in total. They were created by giving random integer weights from
the interval $[1,2n]$ to each symbol, and the frequency $f_{i}=1$ for all
symbols $a_{i}\in A$.

  * •

large: This instance set was created by the authors of Pessoa et al. (2018) to
push the limits of their proposed approach. This instance set consists of ten
instances for various combination of $n\in\\{5,7,\ldots,15,20,\ldots,50\\}$
and $T\in\\{2n,3n,\ldots,10n,15n,\ldots,40n\\}$, resulting in 260 instances in
total (see Table 2 for the used combinations). The weights and frequencies
were created in the same fashion as in instance set normal.

###  3.2 Results

We are first interested in the influence of the various ingredients of our
solution framework. To do so, we compared the following three settings with a
timelimit of 1800 seconds on instance set normal.

  * •

basic: This is a basic setting consisting of Algorithm 1 used with our MIP
model without any enhancements.

  * •

ineqs: In this setting, the MIP gets enhanced by the valid inequalities (9),
the variable fixings described and lifting described in in Observations 2, 3,
4 and also the symmetry breaking constraints (11), (12).

  * •

enhanced: This setting is setting ineqs enhanced with the extended MIP model
with inequalities (13)(14) and the results of Observations 5, 6, which can
allow us to skip solving some MIPs and to lift the right-hand-side of
inequalities (9).

Figure 2 shows a plot of the runtime for solving instance set normal. We see
that the additional ingredients improve the performance of our solution
approach, and setting enhanced manages to solve nearly all instances to
optimality within the given timelimit.

Figure 2: Runtime to optimality for instance set normal and different
settings.

Table 1 gives the average runtime ($t[s]$) and number of solved instances
($\\#nS$) aggregated by number of symbols and $T$ and also contains the
results of the best approach of Pessoa et al. (2018)111the raw-data of their
experiments is available at
https://sites.google.com/site/weightedfairsequencesproblem/computational-
experiments. The runs in Pessoa et al. (2018) were made with CPLEX 12.6 on an
Intel Core i7 with 1.9 GHz and 6GB of RAM, and as timelimit, they used 3600
seconds for all instances, except for the combinations $n=13,T=52$ and
$n=15,T=60$ for which they used 18000 seconds.

Table 1: Results for instance set normal aggregated by number of symbols and $T$ . |  | basic | ineqs | enhanced | Pessoa et al. (2018)
---|---|---|---|---|---
$n$ | $T$ | t [s] | $\\#nS$ | t [s] | $\\#nS$ | t [s] | $\\#nS$ | t [s] | $\\#nS$
5 | 10 | 0.33 | 10 | 0.12 | 10 | 0.04 | 10 | 0.45 | 10
5 | 15 | 1.67 | 10 | 0.38 | 10 | 0.10 | 10 | 1.51 | 10
5 | 20 | 4.25 | 10 | 0.89 | 10 | 0.31 | 10 | 18.58 | 10
7 | 14 | 4.73 | 10 | 0.55 | 10 | 0.11 | 10 | 0.76 | 10
7 | 21 | 121.15 | 10 | 2.45 | 10 | 0.55 | 10 | 15.85 | 10
7 | 28 | 971.58 | 7 | 25.43 | 10 | 5.71 | 10 | 301.93 | 10
9 | 18 | 119.09 | 10 | 2.60 | 10 | 0.24 | 10 | 1.54 | 10
9 | 27 | 1617.55 | 2 | 7.60 | 10 | 0.91 | 10 | 28.33 | 10
9 | 36 | TL | 0 | 181.18 | 10 | 13.13 | 10 | 1475.92 | 8
11 | 22 | 740.50 | 8 | 13.31 | 10 | 0.53 | 10 | 2.46 | 10
11 | 33 | TL | 0 | 293.12 | 10 | 2.89 | 10 | 184.12 | 10
11 | 44 | TL | 0 | 940.85 | 5 | 189.40 | 9 | 2529.78 | 5
13 | 26 | TL | 0 | 48.78 | 10 | 1.33 | 10 | 6.82 | 10
13 | 39 | TL | 0 | 1052.43 | 5 | 10.26 | 10 | 1354.14 | 10
13 | 52 | TL | 0 | TL | 0 | 390.60 | 9 | 13013.13 | 4
15 | 30 | TL | 0 | 506.48 | 9 | 3.05 | 10 | 10.06 | 10
15 | 45 | TL | 0 | TL | 0 | 30.78 | 10 | 1471.48 | 7
15 | 60 | TL | 0 | TL | 0 | 377.60 | 8 | 15903.48 | 2

The results show that our best setting enhanced manages to solve 176 of 180
instances of this set. Moreover, for the combinations of $n$ and $T$ were the
setting manages to solve all of the instances, the average runtime is at most
30 seconds. In contrast to this, the best setting of Pessoa et al. (2018) only
manages to solve 154 instances to ”optimality” (recall that the exactness of
their algorithm relies on an unproven conjecture), with runtimes up to 1350
seconds for combinations of $n$ and $T$ were their approach manages to solve
all the instances to ”optimality”.

The results for instance set normal also show that our approach begins to
struggle when $T=4n$ for $n=11,13,15$. Thus, next we are interested in the
results for instance set large which contains challenging instances, where
some have larger $n$ and $T$ is created based on a larger multiplication
factor for $n$. Table 2 gives the result for our approach with setting
enhanced and the best approach from Pessoa et al. (2018), the timelimit was
set to 3600 seconds for these runs.

Table 2: Results for instance set large aggregated by number of symbols and $T$ . |  | enhanced | Pessoa et al. (2018)
---|---|---|---
$n$ | $T$ | t [s] | $\\#nS$ | t [s] | $\\#nS$
5 | 25 | 2.35 | 10 | 384.44 | 10
5 | 30 | 3.05 | 10 | 1305.70 | 8
5 | 35 | 10.98 | 10 | 2281.99 | 5
5 | 40 | 173.92 | 10 | 2658.08 | 3
5 | 50 | 407.71 | 10 | 1823.73 | 5
5 | 75 | 837.11 | 8 | 2178.25 | 4
5 | 100 | 450.99 | 9 | 2648.17 | 3
5 | 125 | 1518.29 | 6 | 2620.63 | 3
5 | 150 | 1618.53 | 6 | 2962.30 | 3
5 | 200 | 2186.13 | 4 | TL | 0
7 | 35 | 79.36 | 10 | 2334.06 | 5
7 | 42 | 91.21 | 10 | 2995.13 | 2
7 | 49 | 566.62 | 9 | 2503.26 | 4
7 | 56 | 798.94 | 8 | 3142.86 | 2
7 | 63 | 1595.93 | 6 | TL | 0
9 | 45 | 802.45 | 8 | TL | 0
11 | 55 | 674.43 | 9 | TL | 0
20 | 40 | 11.57 | 10 | 28.07 | 10
20 | 60 | 116.78 | 10 | 2933.50 | 3
25 | 50 | 49.27 | 10 | 115.55 | 10
25 | 75 | 763.45 | 10 | TL | 0
30 | 60 | 140.12 | 10 | 498.84 | 9
35 | 70 | 383.09 | 10 | 1310.33 | 8
40 | 80 | 763.53 | 10 | 2693.67 | 5
45 | 90 | 1976.25 | 10 | 3445.86 | 3
50 | 100 | 3180.80 | 5 | TL | 0

We see that our approach manages to solve 228 of 260 instances to optimality,
while the approach of Pessoa et al. (2018) only solves 105 instances.
Moreover, our approach manages to solve at least one instance for each
combination of $n$ and $T$, while there are six such combinations where the
approach of Pessoa et al. (2018) cannot solve any instance. The problem seems
to become harder when $n$ and $T$ gets larger, this is not unexpected, as in
this case also the model gets larger and more iterations have to be computed
in the algorithm. Detailed results for both instance sets are made available
in machine-readable format at
https://msinnl.github.io/pages/instancescodes.html.

##  4 Conclusion and outlook

In this paper, we presented a new iterative exact solution algorithm for the
weighted fair sequences problem (WFS), which is a recently introduced NP-hard
sequencing problem with applications in diverse areas such as TV advertisement
scheduling, periodic machine maintenance and real-time scheduling. In the WFS
we are given an upper bound on the allowed solution sequence length and a list
of symbols. For each symbols, there is a positive weight and a number, which
gives the minimum 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. Our solution algorithm is based on a new mixed-integer programming
model for a fixed sequence length. This model is then solved iteratively. We
develop valid inequalities, variable fixings and an extended model which
allows to pose additional valid inequalities. We also present a result which
can allow to skip solving some iterations. In a computational study on
instances from literature, we see that our approach vastly outperforms
existing solution approaches from literature.

There are various avenues for further work. The development of additional
valid inequalities could be interesting to further speed up the solution
process. The design of effective heuristics could also be a worthwhile topic,
as feasible solutions can be used to initialize our solution algorithm.
Studying alternative modeling approaches, such as a column generation/branch-
and-price based solution approach were there is a set of variables for each
label, which encodes the positions in the sequence this label is placed could
also be fruitful.

## Acknowledgments

The research was supported by the Linz Institute of Technology (Project
LIT-2019-7-YOU-211) and the JKU Business School.

## References

## References

  * Allahverdi et al. (2008) Allahverdi, A., Ng, C. T., Cheng, T. E., Kovalyov, M. Y., 2008. A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187 (3), 985–1032.
  * Anily et al. (1998) Anily, S., Glass, C. A., Hassin, R., 1998. The scheduling of maintenance service. Discrete Applied Mathematics 82 (1-3), 27–42.
  * Bar-Noy et al. (2002) Bar-Noy, A., Bhatia, R., Naor, J., Schieber, B., 2002. Minimizing service and operation costs of periodic scheduling. Mathematics of Operations Research 27 (3), 518–544.
  * Bar-Noy and Ladner (2003) Bar-Noy, A., Ladner, R. E., 2003. Windows scheduling problems for broadcast systems. SIAM Journal on Computing 32 (4), 1091–1113.
  * Brucker (2004) Brucker, P., 2004. Scheduling Algorithms. Springer Berlin Heidelberg.
URL https://doi.org/10.1007/978-3-540-24804-0

  * Chen and Chen (2009) Chen, D., Chen, R., 2009. New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems. Computers & Operations Research 36 (5), 1646–1655.
  * Contardo et al. (2019) Contardo, C., Iori, M., Kramer, R., 2019. A scalable exact algorithm for the vertex p-center problem. Computers & Operations Research 103, 211–220.
  * García-Villoria and Salhi (2015) García-Villoria, A., Salhi, S., 2015. Scheduling commercial advertisements for television. International Journal of Production Research 53 (4), 1198–1215.
  * Jiménez (2013) Jiménez, P., 2013. Survey on assembly sequencing: a combinatorial and geometrical perspective. Journal of Intelligent Manufacturing 24 (2), 235–250.
  * Kubiak (2004) Kubiak, W., 2004. Fair sequences. In: In Handbook of Scheduling: Algorithms, Models and Performance Analysis, Leung, JY-T., editor, Chapman & Hall/CRC, Boca. Citeseer.
  * Levner et al. (2010) Levner, E., Kats, V., De Pablo, D. A. L., Cheng, T. E., 2010. Complexity of cyclic scheduling problems: A state-of-the-art survey. Computers & Industrial Engineering 59 (2), 352–361.
  * Monden (2011) Monden, Y., 2011. Toyota Production System: An Integrated Approach to Just-In-Time. CRC Press.
  * Pessoa et al. (2018) Pessoa, B. J. d. S., Aloise, D., Cabral, L. A., 2018. The weighted fair sequences problem. Computers & Operations Research 91, 121–131.
  * Sinnl (2020) Sinnl, M., 2020. A note on computational approaches for the antibandwidth problem. Central European Journal of Operations Research, 1–21.
  * Tijdeman (1980) Tijdeman, R., 1980. The chairman assignment problem. Discrete Mathematics 32 (3), 323–330.
  * Waldspurger and Weihl W. (1995) Waldspurger, C. A., Weihl W., E., 1995. Stride scheduling: deterministic proportional-share resource management.