Scheduling to Minimize Interaction Cost

Abstract

A model is developed for a scheduling problem in which several activities are competing for a limited number of facilities. It is assumed that any number of activities may be scheduled on any single facility; however there is an interaction cost corresponding to every combination of two activities scheduled on the same facility. This problem is a quadratic program with a rather special structure. An efficient algorithm is developed for determining feasible schedules that are local minima. The nonconvexity of the objective function prevents the identification of a global minimum.