The Online Target Date Assignment Problem

S. Heinz, S.O. Krumke, N. Megow, J. Rambau, A. Tuchscherer and T. Vredeveld
Additional contact information
T. Vredeveld: METEOR

No 55, Research Memoranda from Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization

Abstract: Many online problems encountered in real-life involve a twostage decision process: upon arrival of a new request, an irrevocable firststage 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 particularresource) 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 Online- TDAP 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.

Keywords: operations research and management science (search for similar items in EconPapers)
Date: 2005
View list of references

Downloads: (external link)
http://edocs.ub.unimaas.nl/loader/file.asp?id=1133 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:dgr:umamet:2005055

Access Statistics for this paper

More papers in Research Memoranda from Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization
Series data maintained by Willy Villevoye ().