Stationary object servicing dispatching problems in a one-dimensional processor working zone

Abstract

We consider a system where servicing of a collection of stationary objects distributed inside a one-dimensional zone is done by a moving processor. One-time servicing of each object must be performed during two runs of the processor, direct and reverse. Servicing of any object cannot begin before a predefined time moment; each object is also associated with an individual penalty which is a monotone increasing function of the moment when servicing ends. For the resulting optimization problems, we propose algorithms based on dynamic programming, give examples of their implementation, show results of numerical experiments; we study the computational complexity of these algorithms and the problems themselves.