A fractional 0-1 program for task assignment with respect to preferences

Abstract

We consider a task assignment problem with respect to preferences. The objective is to maximize total weighted satisfaction while maintaining a fair distribution. The problem's mathematical model turns out to be a multiple-ratio, constrained, fractional 0-1 program since satisfaction is defined as a ratio of two linear functions. We discuss the computational complexity of the problem, give three equivalent mixed-integer linear formulations, and propose a naive heuristic the usefulness of which is demonstrated by a numeric study. This paper not only provides a new application of fractional 0-1 programming, but it also suggests an alternative solution approach for a similar problem dealt in the literature before with nonlinear nonconvex methods.