We consider a model where multiple queues are served by a server whose capacity varies randomly and asynchronously with respect to different queues. The problem is to optimally control large deviations of the queues in the following sense: find a scheduling rule maximizing min i h lim n!1 1 n log P (aiQi n) i , (1) where Qi is the length of i-th queue in a stationary regime, and ai 0 are parameters. Thus, we seek to maximize the minimum of the exponential decay rates of the tails of distributions of weighted queue lengths aiQi. We give a characterization of the upper bound on (1) under any scheduling rule, and of the lower bound on (1) under the exponential (EXP) rule. For the case of two queues, we prove that the two bounds match, thus proving optimality of EXP rule in this case. The EXP rule is not asymptotically invariant with respect to scaling of the queues, which complicates its analysis in large deviations regime. To overcome this, we introduce and prove a refined sample path large deviations principle, or refined Mogulsky theorem, which is of independent interest.