The complexity of the travelling repairman problem
Modifications to a procedure for determining necessary and sufficient conditions for the existence of a solution to the multi-index problem are described. These modifications reduce the computation required to such an extent that necessary and sufficient conditions for the existence of a solution to the 3x3x3 multi-index problem can now be determined. These conditions are given in this paper.
This paper considers an exponential cost optimality problem for finite horizon semi-Markov decision processes (SMDPs). The objective is to calculate an optimal policy with minimal exponential costs over the full set of policies in a finite horizon. First, under the standard regular and compact-continuity conditions, we establish the optimality equation, prove that the value function is the unique solution of the optimality equation and the existence of an optimal policy by using the minimum nonnegative...