  We study service scheduling problems in a slotted system in which agents
arrive with service requests according to a Bernoulli process and have to leave
within two slots after arrival, service costs are quadratic in service rates,
and there are also waiting costs. We consider quadratic waiting costs. We frame
the problems as average cost Markov decision processes. While the studied
system is a linear system with quadratic costs, it has state dependent control.
Moreover, it also possesses a non-standard cost function structure in the case
of fixed waiting costs, rendering the optimization problem complex. We
characterize optimal policy. We provide an explicit expression showing that the
optimal policy is linear in the system state. We also consider systems in which
the agents make scheduling decisions for their respective service requests
keeping their own cost in view. We consider quadratic waiting costs and frame
these scheduling problems as stochastic games. We provide Nash equilibria of
this game. To address the issue of unknown system parameters, we propose an
algorithm to estimate them. We also bound the cost difference of the actual
cost incurred and the cost incurred using estimated parameters.
