  In this paper, the cooperative jobs dispatching problem in an edge computing
network with multiple access points (APs) and edge servers is considered. Due
to the uncertain traffic in the network between APs and edge servers, the job
uploading delay can not be predicted accurately. Specifically, the job arrivals
at the APs, the job uploading delay from APs to edge servers and the job
computation time at the edge servers are all modeled as random variables. Since
each job dispatching decision will affect the system state in the future, we
formulate the joint optimization of jobs dispatching at all the APs and all the
scheduling time slots as an infinite-horizon Markov decision process (MDP). The
minimization objective is a discounted measurement of the average processing
time per job, including the uploading delay, the waiting time and the
computation time at the edge servers. In this problem, the approximate MDP
should be adopted to address the curse of dimensionality. Conventional
low-complexity approximate solution of MDP is usually hard to predict the
performance analytically. In this paper, a novel approximate MDP solution
framework is proposed via one-step policy iteration over a baseline policy,
where the analytical performance bound can be obtained. Moreover, since the
expression of the approximate value function is derived, the value iteration in
conventional methods can be eliminated, which can essentially reduce the
computation complexity. It is shown by simulations that proposed low-complexity
algorithm has significantly better performance than various benchmark schemes.
