Principles of Sequencing and Scheduling, 2nd Edition

4Heuristic Methods for the Single‐machine Problem

4.1 Introduction

In earlier chapters, we studied the basic single‐machine sequencing model, paying particular attention to the variations that arise for different objective functions. For some objective functions, such as total flowtime, we saw that an optimal solution can be obtained by a procedure as simple as sorting the jobs. For other objective functions, such as total weighted tardiness, no simple solution procedure is available, and we have to resort to more general techniques of combinatorial optimization.

As mentioned earlier, the computational effort required to solve problems using combinatorial procedures grows remarkably fast as the size of the problem increases. Suppose, for instance, that a computer application for the dynamic programming algorithm allows us to generate and evaluate 1 000 000 subsets per second. Then the solution of a 25‐job problem would consume roughly half a minute of computer time, but a 35‐job problem would take roughly 9 hours to solve, and a 45‐job problem would take over a year. If we need a quick answer to a 45‐job problem, the dynamic programming approach will hardly be suitable. In the case of branch‐and‐bound algorithms, we cannot guarantee a better performance because it is impossible to predict the computational effort precisely: It depends on the parameters in each specific problem.

Although it would be difficult to designate any one problem size as typical of practical problems, ...