The online target date assignment problem

In: The 3rd Workshop on on Approximation and Online Algorithms. Lecture Notes in Computer Science, Volume 3879, Springer, P. 230--243, 2005

Authors

• Stefan Heinz
• Sven O. Krumke
• Nicole Megow
• Jörg Rambau
• Andreas Tuchscherer

Abstract

We present a new class of online optimization problems: An instance of the Online Target Date Assignment Problem (OnlineTDAP) consists of a sequence of requests of some type with a release date, a set of feasible target dates for their service, and a downstream optimization problem whose input consists of requests of the same type. The downstream cost at some date of some target date assignment is the minimal cost of the downstream optimization, where the input consists of all requests that have been assigned to that date. There are two natural objectives: minimize the sum over all dates of the downstream costs and minimize the maximum over all dates of the downstream costs. We show that this setting generalizes some existing online optimization problems. Moreover, we perform a competitive analysis for some OnlineTDAP-s where the downstream optimization problem is a binpacking or a scheduling problem.

BibTeX

 
@InProceedings{ HeinzEtAl:OnlineAssignment, 
   title = { The online target date assignment problem }, 
   author = { Stefan Heinz and Sven O. Krumke and Nicole Megow and Jörg Rambau and Andreas Tuchscherer },   
   booktitle = { The 3rd Workshop on on Approximation and Online Algorithms },  
   series = { Lecture Notes in Computer Science }, 
   volume = { 3879 },     
   publisher = { Springer },   
   pages = { 230--243 },   
   year = 2005, 
} 

---

This publication belongs to the project DeNDeMA.