Video coding standards like H.264 offer the flexibility to select reference frames during motion estimation for predicted frames. We investigate the packet scheduling problem of streaming video over lossy networks from a real-time encoder with flexible reference frame. In particular, we consider a multi-path streaming setting where each predicted frame of video, in addition to the flexibility to select a reference frame, can schedule one or multiple transmissions on one or multiple delivery paths for the upcoming optimization period. We present an algorithm based on dynamic programming that provides a locally optimal solution with high complexity. We then present a rounding method to reduce computation complexity at the expense of degrading solution quality. Results show that our algorithm performs noticeably better than a greedy scheme, and graceful tradeoff between complexity and solution quality can be achieved.