Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

The Online Target Date Assignment Problem

Title data

Heinz, Stefan ; Krumke, Sven O. ; Megow, Nicole ; Rambau, Jörg ; Tuchscherer, Andreas ; Vredeveld, Tjark:
The Online Target Date Assignment Problem.
In: Erlebach, Thomas ; Persinao, Giuseppe (Hrsg.): Approximation and Online Algorithms. - Berlin ; Heidelberg : Springer , 2006 . - pp. 230-243 . - (Lecture Notes in Computer Science ; 3879 )
ISBN 978-3-540-32207-8

Abstract in another language

Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain “subinstances” (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later.
We introduce the novel concept of an Online Target Date Assignment Problem (OnlineTDAP) as a general framework for online problems with this nature. Requests for the OnlineTDAP become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e. g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the downstream cost, the optimal cost of processing all requests at that date w. r. t. some fixed downstream offline optimization problem (e. g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the OnlineTDAP independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the particular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.

Further data

Item Type: Article in a book
Refereed: Yes
Institutions of the University: Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics in Economy > Chair Mathematics in Economy - Univ.-Prof. Dr. Jörg Rambau
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics in Economy
Result of work at the UBT: Yes
DDC Subjects: 500 Science > 510 Mathematics
Date Deposited: 04 Jun 2014 08:52
Last Modified: 07 Jun 2016 11:29
URI: https://eref.uni-bayreuth.de/id/eprint/748