Principles of Sequencing and Scheduling, 2nd Edition

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.

Theorem 3.1

When the objective is to minimize the maximum cost, job i may be assigned the last position in sequence if g_i(P) ≤  ...