The last chapter explored the idea of heuristic methods. We referred to some empirical studies that showed that in the majority of cases these ‘sensible’ rules generate reasonably good schedules. However, they cannot guarantee optimality and there is always a nagging doubt that in some unfortunate cases they may lead to very poor results. Our first objective in this chapter is to consider worst case bounds on the performance of certain heuristic algorithms, i.e., to discover how poorly they may perform in the worst of possible circumstances.