Wordtrade.com
Mathematics

Handbook of Scheduling: Algorithms, Models, and Performance Analysis edited by Joseph Y-T. Leung (Chapman & Hall/CRC) Over the past few years, the field of scheduling has changed dramatically because of the complexity of the problems now involved. This has led many researchers to develop approximation algorithms that can handle these more difficult kinds of scheduling problems. This in turn has resulted in enormous growth of the field and a wide body of knowledge that has never been pulled together into one volume-until now. Handbook of Scheduling: Algorithms, Models, and Performance Analysis collects all of the up-to-date information on approximation algorithms into one resource that will prove useful to a wide range of users from computer science, industrial engineering, operations research, and management science.

Scheduling is a form of decision-making that plays an important role in many disciplines. It is concerned with the allocation of scarce resources to activities with the objective of optimizing one or more performance measures. Depending on the situation, resources and activities can take on many different forms. Resources may be nurses in a hospital, bus drivers, machines in an assembly plant, CPUs, mechanics in an automobile repair shop, etc. Activities may be operations in a manufacturing process, duties of nurses in a hospital, executions of computer programs, car repairs in an automobile repair shop, and so on. There are also many different performance measures to optimize. One objective may be the minimization of the mean flow time, while another objective may be the minimization of the number of jobs completed after their due dates.

Scheduling has been studied intensively for more than 50 years, by researchers in management, industrial engineering, operations research, and computer science. There is now an astounding body of knowledge in this field. This book is the first handbook on scheduling. It is intended to provide a comprehensive coverage of the most advanced and timely topics in scheduling. A major goal of this project is to bring together researchers in the above disciplines in order to facilitate cross fertilization. The authors and topics chosen cut across all these disciplines.

Scheduling is concerned with the allocation of scarce resources to activities with the objective of optimizing one or more performance measures. Depending on the situation, resources and activities can take on many different forms. Resources may be machines in an assembly plant, CPU, memory and I/O devices in a computer system, runways at an airport, mechanics in an automobile repair shop, etc. Activities may be various operations in a manufacturing process, execution of a computer program, landings and take-offs at an airport, car repairs in an automobile repair shop, and so on. There are also many different performance measures to optimize. One objective may be the minimization of the makespan, while another objective may be the minimization of the number of late jobs.

The study of scheduling dates back to 1950s. Researchers in operations research, industrial engineering, and management were faced with the problem of managing various activities occurring in a workshop. Good scheduling algorithms can lower the production cost in a manufacturing process, enabling the company to stay competitive. Beginning in the late 1960s, computer scientists also encountered scheduling problems in the development of operating systems. Back in those days, computational resources (such as CPU, memory and I/O devices) were scarce. Efficient utilization of these scare resources can lower the cost of executing computer programs. This provided an economic reason for the study of scheduling.

The scheduling problems studied in the 1950s were relatively simple. A number of efficient algorithms have been developed to provide optimal solutions. Most notable are the work by Jackson [1, 2], Johnson [3], and Smith [4]. As time went by, the problems encountered became more sophisticated, and researchers were unable to develop efficient algorithms for them. Most researchers tried to develop efficient branch-and-bound methods that are essentially exponential-time algorithms. With the advent of complexity theory [5-7], researchers began to realize that many of these problems may be inherently difficult to solve. In the 1970s, many scheduling problems were shown to be NP-hard.

In the 1980s, several different directions were pursued in academia and industry. One direction was the development and analysis of approximation algorithms. Another direction was the increasing attention paid to stochastic scheduling problems. From then on, research in scheduling theory took off by leaps and bounds. After almost 50 years, there is now an astounding body of knowledge in this field.

This book is the first handbook in scheduling. It is intended to provide a comprehensive coverage of the most advanced and timely topics in scheduling. A major goal is to bring together researchers in computer science, industrial engineering, operations research, and management science so that cross fertilization can be facilitated. The authors and topics chosen cut across all of these disciplines.

The book comprises six major parts, each of which has several chapters.

Part I presents introductory materials and notation. Chapter 1 gives an overview of the book and the a notation for classical scheduling problems. Chapter 2 is a tutorial on complexity theory. It is included for those readers who are unfamiliar with the theory of NP-completeness and NP-hardness. Complexity theory plays an important role in scheduling theory. Anyone who wants to engage in theoretical scheduling research should be proficient in this topic. Chapter 3 describes some of the basic scheduling algorithms for classical scheduling problems. They include Hu's, Coffman-Graham, LPT, McNaughton's, and Muntz-Coffman algorithms for makespan minimization; SPT, Ratio, Baker's, Generalized Baker's, Smith's, and Generalized Smith's rules for the minimization of total (weighted) completion time; algorithms for dual objectives (makespan and total completion time); EDD, Lawler's, and Horn's algorithms for the minimization of maximum lateness; Hodgson-Moore algorithm for minimizing the number of late jobs; Lawler's pseudo-polynomial algorithm for minimizing the total tardiness.

Part II is devoted to classical scheduling problems. These problems are among the first studied by scheduling theorists, and for which the 3-field notation was introduced for classification.

Chapters 4 to 7 deal with job shop, flow shop, open shop, and cycle shop, respectively. Job shop problems are among the most difficult scheduling problems. There was an instance of job shop with 10 machines and 10 jobs that was not solved for a very long time. Exact solutions are obtained by enumerative search. Chapter 4 gives a concise survey of elimination rules and extensions that are one of the most powerful tools for enumerative search designed in the last two decades. Hybrid flow shops are flow shops where each stage consists of parallel and identical machines. Chapter 5 describes a number of approximation algorithms for two-stage flexible hybrid flow shops with the objective of minimizing the makespan. Open shops are like flow shops, except that the order of processing on the various machines is immaterial. Chapter 6 discusses the complexity of generating exact and approximate solutions for both nonpreemptive and preemptive schedules, under several classical objective functions. Cycle shops are like job shops, except that each job passes through the same route on the machines. Chapter 7 gives polynomial-time and pseudo-polynomial algorithms for cycle shops, as well as NP-hardness results and approximation algorithms.

Chapter 8 shows a connection between an NP-hard preemptive scheduling problem on parallel and identical machines with the corresponding problem in a job shop or open shop environment for a set of chains of equal-processing-time jobs. The author shows that a number of NP-hardness proofs for parallel and identical machines can be used to show the NP-hardness of the corresponding problem in a job shop or open shop.

Chapters 9 to 13 cover the five major objective functions in classical scheduling theory: makespan, maximum lateness, total weighted completion time, total weighted number of late jobs, and total weighted tardiness. Chapter 9 discusses the makespan objective on parallel and identical machines. The author presents polynomial solvability and approximability, enumerative algorithm, and polynomial-time approximations under this framework. Chapter 10 deals with the topic of minimizing maximum lateness on parallel and identical machines. Complexity results and exact and approximation algorithms are given for nonpreemptive and preemptive jobs, as well as jobs with precedence constraints. Chapter 11 gives a comprehensive review of recently developed approximation algorithms and approximation schemes for minimizing the total weighted completion time on parallel and identical machines. The model includes jobs with release dates and/or precedence constraints. Chapter 12 gives a survey of the problem of minimizing the total weighted number of late jobs. The chapter concentrates mostly on exact algorithms and their correctness proofs. Total tardiness is among the most difficult objective functions to solve, even for a single machine. Chapter 13 gives branch-and-bound algorithms for minimizing the total weighted tardiness on one machine, where jobs are nonpreemptible and have release dates (but not precedence constraints).

Many NP-hard scheduling problems become solvable in polynomial time when the jobs have identical processing times. Chapter 14 gives polynomial-time algorithms for several of these cases, concentrating on one machine as well as parallel and identical machines' environments.

The scheduling problems dealt in the above-mentioned chapters are all offline deterministic scheduling problems. This means that the jobs' characteristics are known to the decision maker before a schedule is constructed. In contrast, online scheduling restricts the decision maker to schedule jobs based on the currently available information. In particular, the jobs' characteristics are not known until they arrive. Chapter 15 surveys the literature in online scheduling.

A number of approximation algorithms for scheduling problems have been developed that are based on linear programming. The basic idea is to formulate the scheduling problem as an integer programming problem, solve the underlying linear programming relaxation to obtain an optimal fractional solution, and then round the fractional solution to a feasible integer solution in such a way that the error can be bounded. Chapter 16 describes this technique as applied to the problem of minimizing the total weighted completion time on unrelated machines.

Part III is devoted to scheduling models that are different from the classical scheduling models. Some of these problems come from applications in computer science and some from the operations research and management community.

Chapter 17 discusses the master-slave scheduling model. In this model, each job consists of three stages and processed in the same order: preprocessing, slave processing, and postprocessing. The preprocessing and postprocessing of a job are done on a master machine (which is limited in quantity), while the slave processing is done on a slave machine (which is unlimited in quantity). Chapter 17 gives NP-hardness results, polynomial-time algorithms, and approximation algorithms for makespan minimization.

Local area networks (LAN) and wide area networks (WAN) have been the two most studied networks in the literature. With the proliferation of hand-held computers, Bluetooth network is gaining importance. Bluetooth networks are networks that have an even smaller distance than LANs. Chapter 18 discusses scheduling problems that arise in Bluetooth networks.

Suppose a manufacturer needs to produce d; units of a certain product for customer i, 1 < i < n. Assume that each unit takes one unit of time to produce. The total time taken to satisfy all customers is D = E dj. If we produce all units for a customer before we produce for the next customer, then the last customer will have to wait for a long time. Fair sequences are those such that each customer would ideally receive (aj / D) t units at time t. Chapter 19 gives a review of fair sequences. Note that fair sequences are related to Pfair scheduling in Chapter 27 and fair scheduling of real-time tasks on multiprocessors in Chapter 30.

In scheduling problems with due date-related objectives, the due date of a job is given a priori and the scheduler needs to schedule jobs with the given due dates. In modern day manufacturing operations, the manufacturer can negotiate due dates with customers. If the due date is too short, the manufacturer runs the risk of missing the due date. On the other hand, if the due date is too long, the manufacturer runs the risk of loosing the customer. Thus, due date assignment and scheduling should be integrated to make better decisions. Chapters 20 and 21 discuss due date assignment problems.

In classical scheduling problems, machines are assumed to be continuously available for processing. In practice, machines may become unavailable for processing due to maintenance or breakdowns. Chapter 22 describes scheduling problems with availability constraints, concentrating on NP-hardness results and approximation algorithms.

So far we have assumed that a job only needs a machine for processing without any additional resources. For certain applications, we may need additional resources, such as disk drives, memory, and tape drives, etc. Chapters 23 and 24 present scheduling problems with resource constraints. Chapter 23 discusses discrete resources, while Chapter 24 discusses continuous resources.

In classical scheduling theory, we assume that each job is processed by one machine at a time. With the advent of parallel algorithms, this assumption is no longer valid. It is now possible to process a job with several machines simultaneously so as to reduce the time needed to complete the job. Chapters 25 and 26 deal with this model. Chapter 25 gives complexity results and exact algorithms, while Chapter 26 presents approximation algorithms.

Part IV is devoted to scheduling problems that arise in real-time systems. Real-time systems are those that control real-time processes. As such, the primary concern is to meet hard deadline constraints, while the secondary concern is to maximize machine utilization. Real-time systems will be even more important in the future, as computers are used more often to control our daily appliances.

Chapter 27 surveys the pinwheel scheduling problem, which is motivated by the following application. Suppose we have n satellites and one receiver in a ground station. When satellite j wants to send information to the ground, it will repeatedly send the same information in aj consecutive time slots, after which it will cease to send that piece of information. The receiver in the ground station must reserve one time slot for satellite j during those aj consecutive time slots, or else the information is lost. Information is sent by the satellites dynamically. How do we schedule the receiver to serve the n satellites so that no information is ever lost? The question is equivalent to the following: Is it possible to write an infinite sequence of integers, drawn from the set {1, 2, ..., n}, so that each integer j, 1 < j < n, appears at least once in any aj consecutive positions? The answer, of course, depends on the values of aj. Sufficient conditions and algorithms to construct a schedule are presented in Chapter 27.

In the last two decades, a lot of attention has been paid to the following scheduling problem. There are n periodic, real-time jobs. Each job i has an initial start time si, a computation time ci, a relative deadline di, and a period pi. Job i initially makes a request for execution at time si, and thereafter at times si + kpi, k = 1, 2, .... Each request for execution requires ci time units and it must finish its execution within di time units from the time the request is made. Given m > 1 machines, is it possible to schedule the requests of these jobs so that the deadline of each request is met? Chapter 28 surveys the current state of the art of this scheduling problem.

Chapter 29 discusses an important issue in the scheduling of periodic, real-time jobs — a high-priority job is blocked by a low-priority job due to priority inversion. This can occur when a low-priority job gains access to shared data, which will not be released by the job until it is finished; in other words, the low-priority job cannot be preempted while it is holding the shared data. Chapter 29 discusses some solutions to this problem.

Chapter 30 presents Pfair scheduling algorithms for real-time jobs. Pfair algorithms produce schedules in which jobs are executed at a steady rate. This is similar to fair sequences in Chapter 19, except that the jobs are periodic, real-time jobs.

Chapter 31 discusses several approaches in scheduling periodic, real-time jobs on parallel and identical machines. One possibility is to partition the jobs so that each partition is assigned to a single machine. Another possibility is to treat the machines as a pool and allocate upon demand. Chapter 31 compares several approaches in terms of the effectiveness of optimal algorithms with each approach.

Chapter 32 describes several approximation algorithms for partitioning a set of periodic, real-time jobs into a minimum number of partitions so that each partition can be feasibly scheduled on one machine. Worst-case analyses of these algorithms are also presented.

When a real-time system is overloaded, some time-critical jobs will surely miss their deadlines. Assuming that each time-critical job will earn a value if it is completed on time, how do we maximize the total value? Chapter 33 presents several algorithms, analyzes their competitive ratios, and gives lower bounds for any competitive ratios. Note that this problem is equivalent to online scheduling of independent jobs with the goal of minimizing the weighted number of late jobs.

One way to cope with an overloaded system is to completely abandon a job that cannot meet its deadline. Another way is to execute less of each job with the hope that more jobs can meet their deadlines. This model is called the imprecise computation model. In this model each job i has a minimum execution time mini and a maximum execution time maxi, and the job is expected to execute ai time units, mini < ai < maxi. If job i executes less than maxi time units, then it incurs a cost equal to maxi — ai. The objective is to find a schedule that minimizes the total (weighted) cost or the maximum (weighted) cost. Chapter 34 presents algorithms that minimize total weighted cost, and Chapter 35 presents algorithms that minimize maximum weighted cost as well as dual criteria (total weighted cost and maximum weighted cost). Chapter 36 studies the same problem with arbitrary cost functions. It is noted there that this problem has some connections with power-aware scheduling.

Chapter 37 presents routing problems of real-time messages on a network. A set of n messages reside at various nodes in the network. Each message Mi has a release time ri; and a deadline dj;. The message is to be routed from its origin node to its destination node. Both online and offline routing are discussed. NP-hardness results and optimal algorithms are presented.

Part V is devoted to stochastic scheduling and queueing networks. The chapters in this part differ from the previous chapters in that the characteristics of the jobs (such as processing times and arrival times) are not deterministic; instead, they are governed by some probability distribution functions.

Chapter 38 compares the three classes of scheduling: offline deterministic scheduling, stochastic scheduling, and online deterministic scheduling. The author points out the similarities and differences among these three classes.

Chapter 39 deals with the earliness and tardiness penalties. In Just-in-Time (JIT) systems, a job should be completed close to its due date. In other words, a job should not be completed too early or too late. This is particularly important for products that are perishable, such as fresh vegetables and fish. Harvesting is another activity that should be completed close to its due date. The authors studied this problem under the stochastic setting, comparing the results with the deterministic counterparts.

The methods to solve queueing network problems can be classified into exact solution methods and approximation solution method. Chapter 40 reviews the latest developments in queueing networks with exact solutions. The author presents sufficient conditions for the network to possess a product-form solution, and in some cases necessary conditions are also presented.

Chapter 41 studies disk scheduling problems. Magnetic disks are based on technology developed 50 years ago. There have been tremendous advances in magnetic recording density resulting in disks whose capacity is several hundred gigabytes, but the mechanical nature of disk access remains a serious bottleneck. This chapter presents scheduling techniques to improve the performance of disk access.

The Internet has become an indispensable part of our life. Millions of messages are sent over the Internet everyday. Globally managing traffic in such a large-scale communication network is almost impossible. In the absence of global control, it is typically assumed in traffic modeling that the network users follow the most rational approach; i.e., they behave selfishly to optimize their own individual welfare. Under these assumptions, the routing process should arrive into a Nash equilibrium. It is well known that Nash equilibria do not always optimize the overall performance of the system. Chapter 42 reviews the analysis of the coordination ratio, which is the ratio of the worst possible Nash equilibrium and the overall optimum.

Part VI is devoted to applications. There are chapters that discuss scheduling problems that arise in the airline industry, process industry, hospitals, transportation industry, and educational institutions.

Suppose you are running a professional training firm. Your firm offers a set of training programs, with each program yielding a different payoff. Each employee can teach a subset of the training programs. Client requests arrive dynamically, and the firm must decide whether to accept the request, and if so which instructor to assign to the training program(s). The goal of the decision maker is to maximize the expected payoff by intelligently utilizing the limited resources to meet the stochastic demand for the training programs. Chapter 43 describes a formulation of this problem as a stochastic dynamic program and proposes solution methods for some special cases.

Constructing timetables of work for personnel in healthcare institutions is a highly constrained and difficult problem to solve. Chapter 44 presents an overview of the algorithms that underpin a commercial nurse rostering decision support system that is in use in over 40 hospitals in Belgium.

University timetabling problems can be classified into two main categories: course and examination timetabling. Chapter 45 discusses the constraints for each of them and provides an overview of some recent research advances made by the authors and members of their research team.

Chapter 46 describes a solution method for assigning teachers to classes. The authors have developed a system (GATES) that schedules incoming and outgoing airline flights to gates at the JFK airport in New York City. Using the GATES framework, the authors continue with its applications to the new domain of assigning teachers to classes.

Chapter 47 provides an introduction to constraint programming (CP), focusing on its application to production scheduling. The authors provide several examples of classes of scheduling problems that lend themselves to this approach and that are either impossible to formulate, using conventional Operations Research methods or are clumsy to do so.

Chapter 48 discusses batch scheduling problems in the process industry (e.g., chemical, pharmaceutical, or metal casting industries), which consist of scheduling batches on processing units (e.g., reactors, heaters, dryers, filters, or agitators) such that a time-based objective function (e.g., makespan, maximum lateness, or weighted earliness plus tardiness) is minimized.

The classical vehicle routing problem is known to be NP-hard. Many different heuristics have been proposed in the past. Chapter 49 surveys most of these methods and proposes a new heuristic, called Very Large Scale Neighborhood Search, for the problem. Computational tests indicate that the proposed heuristic is competitive with the best local search methods.

Being in a time-sensitive and mission-critical business, the airline industry bumps from the left to the right into all sorts of scheduling problems. Chapter 50 discusses the challenges posed by aircraft scheduling, crew scheduling, manpower scheduling, and other long-term business planning and real-time operational problems that involve scheduling.

Chapter 51 discusses bus and train driver scheduling. Driver wages represent a big percentage, about 45 percent for the bus sector in the U.K., of the running costs of transport operations. Efficient scheduling of drivers is vital to the survival of transport operators. This chapter describes several approaches that have been successful in solving these problems.

Sports scheduling is interesting from both a practical and theoretical standpoint. Chapter 52 surveys the current body of sports scheduling literature covering a period of time from the early 1970s to the present day. While the emphasis is on Single Round Robin Tournament Problem and Double Round Robin Tournament Problem, the chapter also discusses Balanced Tournament Design Problem and Bipartite Tournament Problem.

Headline 3

insert content here

WT Main | About WT | Review Links | Contact | Review Sources | Search