Abstract: Optical Burst Switching (OBS) is a promising paradigm for the next-generation internet. In OBS, a key problem is to schedule bursts on wavelength channels whose bandwidth may become fragmented with the so-called void (or idle) intervals when attempting to reduce the burst loss with both fast and bandwidth efficient algorithms. Till date, only two scheduling algorithms called Horizon and LAUC-VF have been proposed which trade off bandwidth efficiency with fast running time and vice versa. In this study, we propose several novel algorithms for scheduling bursts in OBS networks with and without Fiber Delay Lines (FDLs). In networks without FDLs, the proposed Min-SV algorithm can schedule a burst successfully in O (log m) time where m is the total number of void intervals as long as there are suitable void intervals. Simulation results suggest that the algorithm achieves a loss rate which is as low as that provided previously known algorithm LAUC-VF but can run much faster. In fact, its speed can be almost the same as Horizon (which has a much higher loss rate). In networks with FDL's, the proposed Batching FDL algorithm considers a batch of FDL's simultaneously to find a suitable FDL to delay a burst which would otherwise be discarded due to contention, instead of considering the FDL's one by one. The average search time of this algorithm is therefore significantly reduced from that of the existing sequential search algorithms.