Abstract. The Stochastic Dynamic Distance Optimal Partitioning problem (SDDP problem) is a complex Operations Research problem. The SDDP problem is based on an industrial problem, which contains an optimal conversion of machines.

Partitions of integers as states of these stochastic dynamic programming problems involves combinatorial aspects of SDDP problems. Under the assumption of identical ''basic costs'' (in other words of ''unit distances'') and independent and identically distributed requirements we will show (in many cases) by means of combinatorial ideas that decisions for feasible states with least square sums of their parts are optimal solutions. Corresponding Markov kernels are called partitions-Requirements-Matrices (PRMs).

Optimal decisions of such problems can be used as approximate solutions of corresponding SDDP problems, in which the basic costs differ only slightly from each other or as starting decisions if corresponding SDDP problems are solved by iterative methods, such as the Howard algorithm.

Received: June 25, 2013

AMS Subject Classification: 90C40, 05A99, 15B51, 15B36, 90B30, 90B06

Key Words and Phrases: Markov decision process, combinatorics, stochastic dynamic distance optimal partitioning problem, partitions-requirements-matrices, production, transport

Download paper from here.