The design of scheduling schemes for wireless communication systems has been driven by a compromise between the objectives of system throughput and fairness among users. In case the quality of all user channels is known to the controller, proportional fair scheduling has been well understood. However, to acquire the channel quality information may consume substantial amount of resources. In this work, it is assumed that probing for channel quality information takes a fraction of the coherence block, so that the amount of time for data transmission is reduced. A simple strategy for channel probing and scheduling is proposed, which achieves the maximum throughput under the proportional fairness constraint. It is found that when probing cost is taken into account, the multi-user diversity gain does not always increase as the number of users increases. Simulation results show that the proposed strategy significantly outperforms existing schemes when the channel probing cost is taken into account.