Home

Welcome to the WFSP Website

This site has the goal of spreading the Weighted Fair Sequences Problem (WFSP) and the results obtained so far.

Weighted Fair Sequences Problem

The WFSP is a new optimization problem with a wide spectrum of applications, ranging from task scheduling in real-time systems to automobile production on a mixed-model assembly line. It can be defined as follow:

Let X = {x₁, x₂, …, x_n} be a set of n symbols, each having unit length, and c : X → Z⁺ a priority function. For a symbol x_i, we denote c_i = c(x_i) its priority. Consider a sequence S = s₁, s₂, ..., s_T of T symbols of X, with T ≤ TMAX, where TMAX is a parameter of the problem corresponding to the maximum length of the sequence. The frequency or the number of copies or occurrences of the symbols in S is a variable of the problem and is at least equal to one. The distance d_i,k,k+1 between the copies k and k + 1 of symbol x_i ∈ X is the number of symbols between them plus one. Assuming that l is the index of the last copy of symbol x_i in the sequence, d_i,l,1 is the distance between the last copy of x_i in a cycle and its first copy in the subsequent cycle. By denoting D_i the largest distance between all the consecutive copies of symbol x_i , including d_i,l,1, the goal is to find a sequence S that minimizes the largest product D_ic_i, ∀x_i ∈ X.

Figure 1 shows a set of symbols X = {A, B, C, D, E, F} , the priority order between them, and two possible solution sequences for this instance. The illustrated sequences represent two feasible solutions with different distributions of symbols. In Solution 1, the copies of a given symbol are positioned one after the other, which results in a bad solution to the WFSP. In the second solution, the copies are spaced as evenly as possible. Comparing these solutions on the basis of the distances between the copies of symbol A, the largest distance is observed to decrease from D_A = 9 in Solution 1 to D_A = 3 in Solution 2. Consequently, the product D_Ac_A also decreases. As the largest distances of all the symbols are minimized, Solution 2 is better than Solution 1.

Figure 1. Uniform and non-uniform distribution of symbols.