DGAP-The dynamnic generalized assignment problem

The Generalized Assignment Problem is a well-known operations research model. Given a set of tasks to be assigned to a group of agents and the cost of performing each task by each agent, the model allocates tasks to agents to minimize the total cost subject to the availability of a single resource type. The single resource is consumed by the agents when performing these tasks. In this paper, the authors add the impact of time to the model assuming that each task has a due date, and inventory cost as well as shortage cost is incurred when a task is finished ahead or after its due date, respectively. They formulate the continuous-time optimal control model of the problem where identical tasks are grouped into jobs (or batches), each job is performed by each agent with a fixed (production) rate, while due dates are transformed into demand. As a result, analytical properties of the optimal behavior of such a dynamic system are derived. Based on those properties, an efficient time-decomposition procedure is developed to solve the problem.