Fair task allocation problem.

In fields like transport or materials sourcing, it is common industrial practice nowadays to contract several partners for the fulfilment of similar sets of tasks. A typical approach is to include quotes to the contracts that specify which portion of the total volume should be given to each partner. In this study, which is inspired by a real-world problem, we examine the question of operationally distributing jobs to a set of partners in order to meet the contracted quotes in different dimensions as closely as possible. We propose the term fair task allocation problem and analyze its complexity. While the problem is NP-hard in the strong sense for the general case, we show that it is solvable in pseudopolynomial time for a given number of partners and dimensions. Besides an exact solution approach based on dynamic programming, we present an efficient Tabu Search procedure. The Tabu Search is applied to real world as well as to self-generated instances. To verify its quality, the results are compared to the solutions of a commercial MIP-solver. [ABSTRACT FROM AUTHOR]