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

The classical k-server problem has been widely used to model two-level memo ry systems (e.g., paging and caching). The problem is to plan the movements of Ic 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 bul k requests and formulate, in this way, a valid model for the usual two-leve l tooling configuration in automated production systems. A slight adaptatio n of the so-called Partitioning Algorithm provides an on-line algorithm for this more general case, preserving basically the same competitive properti es as the classical model. This approach yields a new tool management proce dure in manufacturing which outperforms in its quality the usual methods th at are based on heuristics for the traveling salesman problem.