Open AccessThe Continuous Assignment Problem and Its Application to Preemptive and Non-Preemptive Scheduling with Irregular Cost Functions
Author(s) -
Francis Sourd
Publication year - 2004
Publication title -
informs journal on computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.403
H-Index - 80
eISSN - 1526-5528
pISSN - 1091-9856
DOI - 10.1287/ijoc.1030.0034
Subject(s) - mathematical optimization , scheduling (production processes) , branch and bound , preemption , assignment problem , computer science , generalized assignment problem , job shop scheduling , weapon target assignment problem , maximization , mathematics , algorithm , schedule , operating system
International audienceThis paper focuses on the continuous assignment problem with the eventual aim to solve scheduling problems with irregular cost functions. It consists of partitioning a region of Rd into subregions of prescribed volumes so that the total cost is minimized. The dual problem of the continuous assignment problem is an unconstrained maximization 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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom