k-server problems with bulk requests: an application to tool switching in manufacturing

Caroline Privault and Gerd Finke

Annals of Operations Research, 2000, vol. 96, issue 1, 255-269

Abstract: The classical k-server problem has been widely used to model two-level memory systems (e.g., paging and caching). The problem is to plan the movements of k mobile servers on the vertices of a graph under an on-line sequence of requests. We generalize this model in order to process a sequence of bulk requests and formulate, in this way, a valid model for the usual two-level tooling configuration in automated production systems. A slight adaptation of the so-called Partitioning Algorithm provides an on-line algorithm for this more general case, preserving basically the same competitive properties as the classical model. This approach yields a new tool management procedure in manufacturing which outperforms in its quality the usual methods that are based on heuristics for the traveling salesman problem. Copyright Kluwer Academic Publishers 2000

Keywords: paging; on-line tool switching; k-server problems; competitive analysis; 90B30; 90B35 (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018939132489 (text/html)
Access to full text is restricted to subscribers.

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: https://EconPapers.repec.org/RePEc:spr:annopr:v:96:y:2000:i:1:p:255-269:10.1023/a:1018939132489

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018939132489

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().