We introduce a comprehensive modeling framework for the problem of scheduling a finite number of finite-length jobs where the available service rate is time-varying. The main motivation comes from wireless data networks where the service rate of each user varies randomly due to fading. We employ recent advances on the restless bandit problem that allow us to obtain an opportunistic scheduling rule for the system without arrivals. When the objective is to minimize the mean number of users in the system or to minimize the mean waiting time, we obtain a priority-based policy which we call the “Potential Improvement” (PI) rule, since the priority index equals the ratio between the current available service rate and the expected potential improvement of the service rate. We also show that for certain objective functions, the index rule takes the form of known opportunistic scheduling rules like “Relatively Best” (RB) or “Proportionally Best” (PB). Thus our model provides a formal justification for the deployment of opportunistic scheduling rules in order to improve the flow-level performance in the presence of time-varying capacities. We further analyze the performance of the PI rule in the presence of randomly arriving users. When the service rates are constant, PI is equivalent to the cμcμ-rule, which is known to be optimal with any distribution of arrivals. Using a recent characterization for the stability region of flow-level scheduling rules under random arrivals, we show that PI achieves the maximum stability region. We perform numerical experiments in a wide range of scenarios and compare the performance of PI with other popular disciplines like RB, PB, Score-Based (SB) and the cμcμ-rule. Our results show that RB, PB, SB or the cμcμ-rule might outperform the others depending on the scenario, but regardless of this, the performance of PI is always superior or equivalent to the best of these opportunistic rules.