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 gj(t), is incurred when job j completes at time t. We assume only that gj(t) is nondecreasing. Typical scheduling problems involve minimizing the maximum gj(t) value (the maximum cost problem) or minimizing the sum of gj(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.