1.2. SCHEDULING THEORY

1.2. SCHEDULING THEORY

Scheduling theory is concerned primarily with mathematical models that relate to the process of scheduling. The development of useful models, which leads in turn to solution techniques and practical insights, has been the continuing interface between theory and practice. The theoretical perspective is also largely a quantitative approach, one that attempts to capture problem structure in mathematical form. In particular, this quantitative approach begins with a description of resources and tasks and with the translation of decision-making goals into an explicit objective function.

Ideally, the objective function should consist of all costs that depend on scheduling decisions. In practice, however, such costs are often difficult to measure, or even to completely identify. The major operating costs—and the most readily identifiable—are determined by the planning function, while scheduling-related costs are difficult to isolate and often tend to appear fixed. Nevertheless, three types of decision-making goals seem to be prevalent in scheduling: turnaround, timeliness, and throughput. Turnaround measures the time required to complete a task. Timeliness measures the conformance of a particular task’s completion to a given deadline. Throughput measures the amount of work completed during a fixed period of time. The first two goals need further elaboration, because although we can speak of turnaround or timeliness for a given task, scheduling problems require a performance measure for the entire set of tasks in a schedule. Throughput, in contrast, is already a measure that applies to the entire set. As we develop the subject of scheduling in the following chapters, we will elaborate on the specific objective functions that make these three goals operational.

We categorize the major scheduling models by specifying the resource configuration and the nature of the tasks. For instance, a model may contain one machine or several machines. If it contains one machine, jobs are likely to be single stage, whereas multiple-machine models usually involve jobs with multiple stages. In either case, machines may be available in unit amounts or in parallel. In addition, if the set of jobs available for scheduling does not change over time, the system is called static, in contrast to cases in which new jobs appear over time, where the system is called dynamic. Traditionally, static models have proved more tractable than dynamic models and have been studied more extensively. Although dynamic models would appear to be more important for practical application, static models often capture the essence of dynamic systems, and the analysis of static problems frequently uncovers valuable insights and sound heuristic principles that are useful in dynamic situations. Finally, when conditions are assumed to be known with certainty, the model is called deterministic. On the other hand, when we recognize uncertainty with explicit probability distributions, the model is called stochastic.

Two kinds of feasibility constraints are commonly found in scheduling problems. First, there are limits on the capacity of machines, and second, there are technological restrictions on the order in which some jobs can be performed. A solution to a scheduling problem is any feasible resolution of these two types of constraints, so that “solving” a scheduling problem amounts to answering two kinds of questions:

• Which resources should be allocated to perform each task?
• When should each task be performed?

In other words, a scheduling problemgives rise to allocation decisions and sequencing decisions. From the start, the scheduling literature has relied on mathematical models for these two kinds of decision problems. In more recent developments, referred to as safe scheduling, the models recognize service levels as well. Safe scheduling may also involve the decision to accept a job or reject it in the first place, so that when we make commitments to customers, we can be confident that their jobs will finish within the time allowed. An alternative approach to safe scheduling minimizes the expected economic cost of a schedule, including the cost of tardiness and the cost of safety time. Instead of specifying a service level in advance, this approach determines economic service levels as part of the solution.

The need to account for safety time also has important implications for sequencing decisions. As an example of the economic approach to safe scheduling, consider a hub airport that serves several cities (Trietsch, 1993). Instead of providing direct flights for all pairs of cities, incoming flights from each city are directed to the hub, and passengers then take outgoing flights to their destinations. Flights are interrelated because they feed each other with passengers. Ideally, all incoming flights should arrive at about the same time and all outgoing flights should leave at about the same time. In practice, however, sufficient time gaps must be maintained between aircraft when landing or taking off, so both sequencing decisions and timing decisions are necessary. In sequencing, we must account for the fact that different incoming flights have different variances: in general, higher variance implies the need for more safety time, so flights with high variance should be scheduled to arrive earlier. Thus, sequencing decisions may be quite different from those obtained by deterministic models. Furthermore, sequencing in this case is not necessarily about the final order in which aircraft will arrive but about the best plan fromwhich to deviate later, when we correct for various random events, including stochastic departure delays at the originating airports of the incoming flights, emergencies (such as low fuel) forcing the need to expedite some landings in favor of others, and so on. Very tight schedules are likely to lead to higher disruption costs but loose schedules have higher safety time cost. The challenge is to schedule all incoming and outgoing flights so as to minimize the total expected time cost of passengers and equipment plus the disruption cost that occurs if feeding flights are late or if aircraft are forced to wait too long for permission to land.

Traditionally, many scheduling problems have been viewed as problems in optimization subject to constraints—specifically, problems in allocation and sequencing. Sometimes, scheduling is purely allocation (e.g, choosing the product mix with limited resources), and in such cases mathematical programming models are usually appropriate for determining optimal decisions. These general techniques are described in many available textbooks and are not emphasized in our coverage. At other times, scheduling is purely sequencing. In these cases, the problems are unique to scheduling theory and account for much of our emphasis in the chapters that follow.

The theory of scheduling also includes a variety of methodologies. Indeed, the scheduling field has become a focal point for the development, application, and evaluation of combinatorial procedures, simulation techniques, and heuristic solution approaches. The selection of an appropriate method depends mainly on the nature of the model and the choice of objective function. In some cases, it makes sense to consider alternative techniques. For this reason, it is important to study methodologies as well as models.

A useful perspective on the relation of scheduling problems and their solution techniques comes from developments in a branch of computer science known as complexity theory. The notion of complexity refers to the computing effort required by a solution algorithm. Computing effort is described by order-of-magnitude notation. For example, suppose we use a particular algorithm to solve a problem of size n.
(Technically, n denotes the amount of information needed to specify the problem.) The number of computations required by the algorithm is typically bounded from above by a function of n. If the order of magnitude of this function is polynomial as n gets large, then we say the algorithm is polynomial. For instance, if the function has order of magnitude n 2, denoted O(n2), then the algorithm is polynomial. On the other hand, if the function is O(2n), then the algorithm is nonpolynomial (in this case, exponential). Other things being equal, we prefer to use a polynomial algorithm because as n grows large, polynomial algorithms are ultimately faster.

A class of problems called NP-complete problems includes many well-known and difficult combinatorial problems. These problems are equivalent in the sense that if one of them can be solved by a polynomial algorithm, then so can the others. However, many years of research by mathematicians and computer scientists has not yielded a polynomial algorithm for any problem in this class, and the conjecture is that no such algorithm exists. Optimization problems as difficult as these, or even more difficult, are called NP-hard problems. The usefulness of this concept, which applies to many scheduling problems, is that if we are faced with the need to solve large versions of an NP-hard problem, we know in advance that we may not be able to find optimal solutions with available techniques. We might be better off to use a heuristic solution procedure that has a more modest computational requirement but does not guarantee optimality. NP-hard instances exist for which it would take less time to actually perform the work in the shop (using any reasonable sequence) than to solve the problem optimally on the fastest available computer. Therefore, the reliance on heuristics is often the rule in practice, rather than the exception. Finally, some solution procedures involve simulation. Although simulation is inherently imprecise, it can produce nearly optimal solutions that are completely satisfactory for practical purposes. In that respect, simulation is conceptually similar to the use of heuristics.

We will have occasion to refer to the computational complexity of certain algorithms. We will also mention that certain problems are known to be NP-hard. This is relevant information for classifying many of the problems we introduce, but the details of complexity theory are beyond the scope of our main coverage. For a thorough introduction to the subject, see Garey and Johnson (1979).