1
Introduction

1.1 Introduction to Sequencing and Scheduling

Scheduling is a term in our everyday vocabulary, although we may not always have a good definition of it in mind. Actually, it's not scheduling that is a common concept in our everyday life; rather it is schedules. A schedule is a tangible plan or document, such as a bus schedule or a class schedule. A schedule usually tells us when things are supposed to happen; it shows us a plan for the timing of certain activities and answers the question, "If all goes well, when will a particular event take place?" Suppose we are interested in when dinner will be served or when a bus will depart. In these instances, the event we are interested in is the completion of a particular activity, such as preparing dinner, or the start of a particular activity such as a bus trip. Answers to the "when" question usually come to us with information about timing. Dinner is scheduled to be served at 6:00 p.m., the bus is scheduled to depart at 8:00 a.m., and so on. However, an equally useful answer might be in terms of sequence rather than timing: That is, dinner will be served as soon as the main course is baked, or the bus will depart right after cleaning and maintenance are finished. Thus, the "when" question can be answered by timing or by sequence information obtained from the schedule.

If we take into account that some events are unpredictable, then changes may occur in a schedule. Thus, we may say that the bus leaves at 8:00 a.m. unless it is delayed for cleaning and maintenance, or we may leave the condition implicit and just say that the bus is scheduled to leave at 8:00 a.m. If we make allowances for uncertainty when we schedule cleaning and maintenance, then passengers can trust that the bus will leave at 8:00 a.m. with some confidence. Using a time buffer (or safety time) helps us cope with uncertainty.

Intuitively, we think of scheduling as the process of generating the schedule, although we seldom stop to consider what the details of that process might be. In fact, although we think of a schedule as something tangible, the process of scheduling seems intangible, at least until we consider it in some depth. For example, we often approach the problem in two steps: sequencing and scheduling. In the first step, we plan a sequence or decide how to select the next task. In the second step, we plan the start time, and perhaps the completion time, of each task. The determination of safety time is part of the second step.

Preparing a dinner and doing the laundry are good examples of everyday scheduling problems. They involve tasks to be carried out, the tasks are well specified, and particular resources are required - a cook and an oven for dinner preparation and a washer and a dryer for laundry. Scheduling problems in industry have similar elements: they contain a set of tasks to be carried out and a set of resources available to perform those tasks. Given tasks and resources, together with some information about uncertainties, the general problem is to determine the timing of the tasks while recognizing the capability of the resources. This scheduling problem usually arises within a decision-making hierarchy in which it follows some earlier, more basic decisions. Dinner preparation, for example, typically requires a specification of the menu items, recipes for those items, and information on how many portions are needed. In industry, analogous decisions are usually part of the planning function. Among other things, the planning function might describe the design of a company's products, the technology available for making and testing the required components, and the volumes that are required. In short, the planning function determines the resources available for production and the tasks to be scheduled.

In the scheduling process, we need to know the type and the amount of each resource so that we can determine when the tasks can feasibly be accomplished. When we specify the tasks and resources, we effectively define the boundary of the scheduling problem. In addition, we describe each task in terms of such information as its resource requirement, its duration, the earliest time at which it may start, and the time at which it is due to complete. If the task duration is uncertain, we may want to suppress that uncertainty when stating the problem. We should also describe any logical constraints (precedence restrictions) that exist among the tasks. For example, in describing the scheduling problem for several loads of laundry, we should specify that each load requires washing to be completed before drying begins.

Along with resources and tasks, a scheduling problem contains an 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 describe a scheduling problem by providing information about tasks, resources, and an objective function. However, finding a solution is often a fairly complex matter, and formal problem-solving approaches are helpful. Formal models help us first to understand the scheduling problem and then to find a good solution systematically. For example, one of the simplest and most widely used models is the Gantt chart, which is an analog representation of a schedule. In its basic form, the Gantt chart displays resource allocation over time, with specific resources shown along the vertical axis and a time scale shown along the horizontal axis. The basic Gantt chart assumes that processing times are known with certainty, as in Figure 1.1.

Figure 1.1 A Gantt chart.

A chart such as Figure 1.1 helps us to visualize a schedule and its detailed elements because resources and tasks show up clearly. With a Gantt chart, we can discover information about a given schedule by analyzing geometric relationships. In addition, we can rearrange tasks on the chart to obtain comparative information about alternative schedules. In this way, the Gantt chart serves as an aid for measuring performance and comparing schedules as well as for visualizing the problem in the first place. In this book, we will examine graphical, algebraic, spreadsheet, and simulation models, in addition to the Gantt chart, all of which help us analyze and compare schedules. In essence, models help us formalize the otherwise intangible process we call scheduling.

Many of the early developments in the field of scheduling were motivated by problems arising in manufacturing. Therefore, it was natural to employ the vocabulary of manufacturing when describing scheduling problems. Now, although scheduling work is of considerable significance in many nonmanufacturing areas, the terminology of manufacturing is still frequently used. Thus, resources are usually called machines and tasks are called jobs. Sometimes, jobs may consist of several elementary tasks called operations. The environment of the scheduling problem is called the job shop, or simply, the shop. For example, if we encounter a scheduling problem faced by underwriters processing insurance policies, we could describe the situation generically as an insurance "shop" that involves the processing of policy "jobs" by underwriter "machines."

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 translates decision-making goals into an explicit objective function.

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 activities, 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...