# 3Optimization Methods for the Single‐machine Problem

## 3.1 Introduction

In the previous chapter, we explored fundamental performance measures for the single‐machine problem and observed that different scheduling procedures were appropriate for different measures. In the *T*‐problem, we encountered a relatively simple problem statement for which the determination of an optimal sequence was not a simple matter. Although we made some progress toward the solution of the *T*‐problem with adjacent pairwise interchange methods, we deferred discussion of a complete solution until we could examine more powerful optimization techniques. In this chapter we introduce some general‐purpose optimization methods for sequencing and scheduling problems and illustrate their application to the *T*‐problem.

As a general setting, suppose that a cost function, denoted *g*_{j}(*t*), is incurred when job *j* completes at time *t*. We assume only that *g*_{j}(*t*) is nondecreasing. Typical scheduling problems involve minimizing the maximum *g*_{j}(*t*) value (the maximum cost problem) or minimizing the sum of *g*_{j}(*t*) values (the total cost problem). We first examine the solution of the maximum cost problem.

Let *P* represent the total processing time of the jobs to be scheduled. Obviously, *P* is equal to the completion time of the last job. The following result identifies the job that should be placed last.

Get *Principles of Sequencing and Scheduling, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.