Temporal reasoning is an essential part of tasks such as planning and scheduling. In this paper, we discussed the design and an empirical analysis of two key algorithms for a temporal reasoning system. The algorithms are a path consistency algorithm and a backtracking algorithm. The temporal reasoning system is based on Allen's [2] interval-based framework for representing temporal information. Our emphasis was on how to make the algorithms robust and efficient in practice on problems that vary from easy to hard. For the path consistency algorithm, the bottleneck is in performing the composition operation. We developed methods for reducing the number of composition operations that need to be performed. These methods can result in almost an order of magnitude speedup over an already highly optimized implementation of the algorithm. For the backtracking algorithm, we developed variable and value ordering heuristics and showed that an alternative formulation of the problem can considerably reduce the time taken to find a solution. The techniques allow an interval-based temporal reasoning system to be applied to larger problems and to perform more efficiently in existing applications.