Growing environmental awareness and new government directives have set the stage for an increase in the fraction of energy supplied using renewable resources. The fast variation in renewable power, coupled with uncertainty in availability, emphasizes the need for algorithms for intelligent online generation scheduling. These algorithms should allow us to compensate for the renewable resource when it is not available and should also account for physical generator constraints. We apply and extend recent work in the field of online optimization to the scheduling of generators in smart (micro) grids and derive bounds on the performance of asymptotically good algorithms in terms of the generator parameters. We also design online algorithms that intelligently leverage available information about the future, such as predictions of wind intensity, and show that they can be used to guarantee near optimal performance under mild assumptions. This allows us to quantify the benefits of resources spent on prediction technologies and different generation sources in the smart grid. Finally, we empirically show how both classes of online algorithms, (with or without the predictions of future availability) significantly outperform certain 'natural' algorithms. © 2012 ACM.