  We propose a general framework, dubbed Stochastic Processing under Imperfect
Information (SPII), to study the impact of information constraints and memories
on dynamic resource allocation. The framework involves a Stochastic Processing
Network (SPN) scheduling problem in which the scheduler may access the system
state only through a noisy channel, and resource allocation decisions must be
carried out through the interaction between an encoding policy (who observes
the state) and allocation policy (who chooses the allocation). Applications in
the management of large-scale data centers and human-in-the-loop service
systems are among our chief motivations.
  We quantify the degree to which information constraints reduce the size of
the capacity region in general SPNs, and how such reduction depends on the
amount of memories available to the encoding and allocation policies. Using a
novel metric, capacity factor, our main theorem characterizes the reduction in
capacity region (under "optimal" policies) for all non-degenerate channels, and
across almost all combinations of memory sizes. Notably, the theorem
demonstrates, in substantial generality, that (1) the presence of a noisy
channel always reduces capacity, (2) more memory for the allocation policy
always improves capacity, and (3) more memory for the encoding policy has
little to no effect on capacity. Finally, all of our positive (achievability)
results are established through constructive, implementable policies.
