Ultra-Wideband (UWB) communication is a promising technology for high data rate multimedia services in future wireless personal and home entertainment networks. To support heterogeneous multimedia applications with a wide variety of QoS requirements and maintain fairness among various traffic classes, a utility-based optimal scheduling problem for UWB networks is formulated. To fully explore the wide spectrum of UWB, its unique characteristics and features, such as the potential of allowing simultaneous transmissions and precision positioning, are considered for scheduling. The optimal scheduling problem of UWB network is significantly different from that in traditional networks. In particular, each link proceeds in a peer-to-peer manner, and the aggregate utilities achieved by concurrent transmissions are random in nature. Thus, the optimal scheduling is formalized as a discrete stochastic optimization problem. We propose an exclusive-region based global searching algorithm (ER-GSA) to locate the global optimum efficiently. Extensive simulations demonstrate the effectiveness and efficiency of the ER-GSA.