ABSTRACT

In this chapter we will look at methods that cannot guarantee optimal solutions, but nevertheless have a strong tendency to produce good solutions. These are called heuristics. As such, most of these are applicable to any kind of problem, as long as the problem is formulated for a specific heuristic. They are not only useful in scheduling, but can be used for any kind of combinatorial optimization. The ones that we will look at are not an exhaustive list, but do represent a large percentage of available heuristics. We will cover random pairwise exchanges (PE), genetic algorithms (GA), simulated annealing (SA), the shifting bottleneck heuristic (SB), and Monte Carlo methods (MC).