The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions

Francis Sourd (Francis.Sourdlip6.fr)

Abstract: It is with the aim of solving scheduling problems with irregular cost functions that this paper focuses on the continuous assignment problem. It consists in partitioning a d dimensional region into subregions of prescribed volumes so that the total cost is minimized. The dual problem of the continuous assignment problem is an unconstrained maximisation of a non-smooth concave function. The preemptive variant of the scheduling problem with irregular cost functions corresponds to the one-dimensional continuous assignment problem and a lower bound for the non-preemptive variant can be derived. It is computationally tested in a branch-and-bound algorithm.

Keywords: Just-in-time scheduling, geometric partitioning, preemptive relaxation

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Scheduling )

Category 3: Infinite Dimensional Optimization (Other )

Citation: INFORMS Journal on Computing 16(2). p198-208. 2004

Download:

Entry Submitted: 10/03/2002
Entry Accepted: 10/03/2002
Entry Last Modified: 06/01/2004

Modify/Update this entry