In this paper, we propose a framework for studying optimal agency execution strategies in a Limit Order Book (LOB) under a Markov-modulated market environment. The Almgren-Chriss's market impact model [1] is extended to a more general situation where multiple venues are available for investors to submit trades. Under the assumption of risk-neutrality, a compact recursive formula is derived, using the value iterative method, to calculate the optimal agency execution strategy. The original optimal control problem is then converted to a constrained quadratic optimization problem, which can be solved by using the Quadratic Programming (QP) approach. Numerical examples are given to illustrate the efficiency and effective of our proposed methods.