Home

Vita

Research

Teaching

A Greedy Heuristic for a Nonlinear Generalized Assignment Problem

In this paper, we examine a nonlinear Generalized Assignment Problem. In particular, we wish to minimize the sum of the cost of assigning jobs to machines plus the sum of a nonlinear function of a linear function of the assignments made to each machine. We propose a greedy heurstic based on a set of dual multipliers associated with the optimal solution to the relaxation of the problem that allows a job to be split among machines. We develop properties of the solution returned by the greedy heurstic. We analyze the performance of the greedy heuristic under a probabilistic model for several types of functions, including piecewise linear functions, concave functions, and polynomial functions.