Optimization Online


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

Francis Sourd (Francis.Sourd***at***lip6.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society