We investigate the problem of minimizing the overall transmission delay of packets in a multi-access wireless communication system, where the transmitters have average power constraints. We use a multi-dimensional Markov chain to model the medium access control (MAC) layer behavior. The state of the Markov chain represents current queue lengths. Our goal is to minimize the average packet delay through controlling the probability of departure at each state, while satisfying the average power constraint for each queue. First, we formulate the problem as a constrained optimization problem. Next, we transform the problem into a standard linear programming problem. Then, we analyze the linear programming problem, and develop a procedure by which we determine the optimal solution analytically.