The Role of Scheduling

   The Role of Scheduling

   Scheduling is a decision-making process that is used on a regular basis in many manufacturing and services industries. It deals with the allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives. The resources and tasks in an organization can take many different forms. The resources may be machines in a workshop, runways at an airport, crews at aconstruction site, processing units in a computing environment, and so on. The tasks may be operations in a production process, take-offs and landings at an airport, stages in a construction project, executions of computer programs, and so on. Each task may have a certain priority level, an earliest possible starting time and a due date. The objectives can also take many different forms. One objective may be the minimization of the completion time of the last task and another may be the minimization of the number of tasks completed after their respective due dates. Scheduling, as a decision-making process, plays an important role in most manufacturing and production systems as well as in most information processing environments. It is also important in transportation and distribution settings and in other types of service industries. The following examples illustrate the role of scheduling in a number of real world environments. 1.2 The Scheduling Function in an Enterprise The scheduling function in a production systemor service organization must interact with many other functions. These interactions are system-dependent and may differ substantially from one situation to another. They often take place within an enterprise-wide information system. A modern factory or service orgnization often has an elaborate information systemin place that includes a central computer and database. Local area networks of personal computers, workstations and data entry terminals, which are connected to this central computer, may be used either to retrieve data from the database or to enter new data. The software controlling such an elaborate  information system is typically referred to as an Enterprise Resource Planning (ERP) system. A number of software companies specialize in the development  of such systems, including SAP, J.D. Edwards, and PeopleSoft. Such an ERP systempla ys the role of an information highway that traverses the enterprise with, at all organizational levels, links to decision support systems. Scheduling is often done interactively via a decision support systemtha t is installed on a personal computer or workstation linked to the ERP system. Terminals at key locations connected to the ERP system can give departments throughout the enterprise access to all current scheduling information. These departments, in turn, can provide the scheduling system with up-to-date information concerning the statuses of jobs and machines. There are, of course, still environments where the communication between the scheduling function and other decision making entities occurs in meetings or through memos. Scheduling in Manufacturing Consider the following generic manufacturing  environment and the role of its scheduling. Orders that are released in a manufacturing setting have to be translated into jobs with associated due dates. These jobs often have to be processed on the machines in a workcenter in a given order or sequence. The processing of jobs may sometimes be delayed if certain machines are busy and preemptions may occur when high priority jobs  arrive at machines that are busy. Unforeseen events on the shop floor, such as machine breakdowns or longer-than-expected processing times, also have to be taken into account, since they may have a major impact on the schedules. In such an environment, the development of a detailed task schedule helps maintain efficiency and control of operations. The shop floor is not the only part of the organization that impacts the scheduling process. It is also affected by the production planning process that handles medium- to long-term planning for the entire organization. This process attempts to optimize the firm’s overall product mix and long-term resource allocation based on its inventory levels, demand forecasts and resource requirements.Decisions made at this higher planning level may impact the scheduling process directly. Figure 1.1 depicts a diagram of the information flow in a manufacturing system.In a manufacturing environment, the scheduling function has to interact with other decision making functions. One popular system that is widely used is the Material Requirements Planning (MRP) system. After a schedule has been generated it is necessary that all raw materials and resources are available at the specified times. The ready dates of all jobs have to be determined jointly by the production planning/scheduling systema nd the MRP system. MRP systems are normally fairly elaborate. Each job has a Bill Of Materials  (BOM) itemizing the parts required for production. The MRP system keeps track of the inventory of each part. Furthermore, it determines the timing of the purchases of each one of the materials. In doing so, it uses techniques such as lot sizing and lot scheduling that are similar to those used in scheduling  systems. There are many commercial MRP software packages available and,  as a result, there are many manufacturing facilities with MRP systems. In the  cases where the facility does not have a scheduling system, the MRP system  may be used for production planning purposes. However, in complex settings it is not easy for an MRP systemto do the detailed scheduling satisfactorily. Scheduling in Services Describing a generic service organization and atypical scheduling systemis not as easy as describing a generic manufacturing organization. The scheduling function in a service organization may face a variety of problems. It may have to deal with the reservation of resources, e.g., the assignment of planes to gates (see Example 1.1.3), or the reservation of meeting rooms or other facilities. The models used are at times somewhat different fromtho se used in manufacturing settings. Scheduling in a service environment must be coordinated with other decision making functions, usually within elaborate information systems, much in the same way as the scheduling function in a manufacturing setting. These information systems usually rely on extensive databases that contain all the relevant information with regard to availability of resources and (potential) customers. The scheduling system interacts often with forecasting and yield management modules. Figure 1.2 depicts the information flow in a service organization such as a car rental agency. In contrast to manufacturing settings, there is usually no MRP system in a service environment.

   Framework and Notation 

   In all the scheduling problems considered the number of jobs and the number of machines are assumed to be finite. The number of jobs is denoted by n and  the number of machines by m. Usually, the subscript j refers to a job while the subscript i refers to a machine. If a job requires a number of processing steps or operations, then the pair (i, j) refers to the processing step or operation of job j on machine i. The following pieces of data are associated with job j. Processing time (pij) The pij represents the processing time of job j on machine i. The subscript i is omitted if the processing time of job j does not depend on the machine or if job j is only to be processed on one given machine. Release date (rj ) The release date rj of job j may also be referred to as the ready date. It is the time the job arrives at the system, i.e., the earliest time  at which job j can start its processing. Due date (dj) The due date dj of job j represents the committed shipping or completion date (i.e., the date the job is promised to the customer). Completion  of a job after its due date is allowed, but then a penalty is incurred. When adue date must be met it is referred to as a deadline and denoted by Ї dj . Weight (wj) Theweight wj of job j is basically a priority factor, denoting  the importance of job j relative to the other jobs in the system. For example, this weight may represent the actual cost of keeping the job in the system. This cost could be a holding or inventory cost; it also could represent the amount of value already added to the job. A scheduling problemis described by a triplet α | β | γ. The α field describes the machine environment and contains just one entry. The β field provides details of processing characteristics and constraints and may contain no entry at all, a single entry, or multiple entries. The γ field describes the objective to be minimized and often contains a single entry. The possible machine environments specified in the α field are: Single machine (1) The case of a single machine is the simplest of all possible machine environments and is a special case of all other more complicated machine environments. Identical machines in parallel (Pm) There are m identical machines in parallel. Job j requires a single operation and may be processed on any one of the m machines or on any one that belongs to a given subset. If job j cannot be processed on just any machine, but only on any one belonging to a specific subset Mj, then the entry Mj appears in the β field. Machines in parallel with different speeds (Qm) Therearem machines in parallel with different speeds. The speed of machine i is denoted by vi. The time pij that job j spends on machine i is equal to pj/vi (assuming job j receives all its processing fromm achine i). This environment is referred to as uniform machines. If all machines have the same speed, i.e., vi = 1 for all i and pij = pj , then the environment is identical to the previous one.Unrelated machines in parallel (Rm) This environment is a further  generalization of the previous one. There are m different machines in parallel. Machine i can process job j at speed vij. The tim epij that job j spends on machine i is equal to pj/vij (again assuming job j receives all its processing fromm achine i). If the speeds of the machines are independent of the jobs, i.e., vij = vi for all i and j, then the environment is identical to the previous one. Flow shop (Fm) There are m machines in series. Each job has to be processed on each one of the m machines. All jobs have to follow the same route, i.e., they have to be processed first on machine 1, then on machine 2, and so on. After completion on one machine a job joins the queue at the next machine. Usually, all queues are assumed to operate under the First In First Out (FIFO) discipline, that is, a job cannot ”pass” another while waiting in a queue. If the FIFO discipline is in effect the flow shop is referred to as apermutation flow shop and the β field includes the entry prmu. Flexible flow shop (FFc) A flexible flow shop is a generalization of the flow shop and the parallel machine environments. Instead of m machines in series there are c stages in series with at each stage a number of identical machines inparallel. Each job has to be processed first at stage 1, then at stage 2, and so on. A stage functions as a bank of parallel machines; at each stage job j requires processing on only one machine and any machine can do. The queues between the various stages may or may not operate according to the First Come First Served (FCFS) discipline. (Flexible flow shops have in the literature at times also been referred to as hybrid flow shops and as multi-processor flow shops.) Job shop (Jm) In a job shop with m machines each job has its own predetermined route to follow. A distinction is made between job shops in which each job visits each machine at most once and job shops in which a job may visit each machine more than once. In the latter case the β-field contains the entry rcrc for recirculation. Flexible job shop (FJc) A flexible job shop is a generalization of the job shop and the parallel machine environments. Instead of m machines in series there are c work centers with at each work center a number of identical machines in parallel. Each job has its own route to follow through the shop; job j requires processing at each work center on only one machine and any machine can do.If a job on its route through the shop may visit a work center more than once,then the β-field contains the entry rcrc for recirculation.Open shop (Om) There are m machines. Each job has to be processed again on each one of the m machines. However, some of these processing times may be zero. There are no restrictions with regard to the routing of each job through the machine environment. The scheduler is allowed to determine aroute for each job and different jobs may have different routes.The processing restrictions and constraints specified in the β field may include multiple entries. Possible entries in the β field are: Release dates (rj ) If this symbol appears in the β field, then job j cannot start its processing before its release date rj. If rj does not appear in the β field, the processing of job j may start at any time. In contrast to release dates, due dates are not specified in this field. The type of objective function gives  sufficient indication whether or not there are due dates. Preemptions (prmp) Preemptions imply that it is not necessary to keep a job on a machine, once started, until its completion. The scheduler is allowed to interrupt the processing of a job (preempt) at any point in time and put a different job on the machine instead. The amount of processing a preempted job already has received is not lost.When a preempted job is afterwards put back on the machine (or on another machine in the case of parallel machines), it only needs the machine for its remaining processing time. When preemptions are allowed prmp is included in the β field; when prmp is not included, preemptions are not allowed.Precedence constraints (prec) Precedence constraints may appear in a single machine or in a parallel machine environment, requiring that one or more jobs may have to be completed before another job is allowed to start its processing. There are several special forms of precedence constraints: if each job has at most one predecessor and at most one successor, the constraints are referred to as chains. If each job has at most one successor, the constraints are referred to as an intree. If each job has at most one predecessor the constraints are referred to as an outtree. If no prec appears in the β field, the jobs are not subject to precedence constraints. Sequence dependent setup times (sjk) The sjk represents the sequence dependent setup time that is incurred between the processing of jobs j and k; s0k denotes the setup time for job k if job k is first in the sequence and sj0 the clean-up time after job j if job j is last in the sequence (of course, s0k and sj0  may be zero). If the setup time between jobs j and k depends on the machine, then the subscript i is included, i.e., sijk. If no sjk appears in the β field, all setup times are assumed to be 0 or sequence independent, in which case they are simply included in the processing times. Job families (fmls) The n jobs belong in this case to F different job families. Jobs from the same family may have different processing times, but they can be processed on a machine one after another without requiring any setup in between. However, if the machine switches over from one family to another, say fromfa mily g to family h, then a setup is required. If this setup time depends on both families g and h and is sequence dependent, then it is denoted by sgh. If this setup time depends only on the family about to start, i.e., family h, then it is denoted by sh. If it does not depend on either family, it is denoted by s. Batch processing (batch(b)) A machine may be able to process a number of jobs, say b, simultaneously; that is, it can process a batch of up to b jobs at the same time. The processing times of the jobs in a batch may not be all the same and the entire batch is finished only when the last job of the batch has been completed, implying that the completion time of the entire batch is determined  by the job with the longest processing time. If b = 1, then the problemr educes to a conventional scheduling environment. Another special case that is of interest is b = ∞, i.e., there is no limit on the number of jobs the machine can handle at any time. Breakdowns (brkdwn) Machine breakdowns imply that a machine may not be continuously available. The periods that a machine is not available are, in this part of the book, assumed to be fixed (e.g., due to shifts or scheduled maintenance). If there are a number of identical machines in parallel, the number of machines available at any point in time is a function of time, i.e., m(t). Machine breakdowns are at times also referred to as machine availability constraints. Machine eligibility restrictions (Mj) The Mj symbol may appear in the β field when the machine environment is m machines in parallel (Pm). When the Mj is present, not all m machines are capable of processing job j. Set Mj denotes the set of machines that can process job j. If the β field does not contain Mj, job j m ay be processed on any one of the m machines. Permutation (prmu) A constraint that may appear in the flow shop environment is that the queues in front of each machine operate according to the First In First Out (FIFO) discipline. This implies that the order (or permutation) in which the jobs go through the first machine is maintained throughout the system. Blocking (block) Blocking is a phenomenon that may occur in flow shops. If a flow shop has a limited buffer in between two successive machines, then it may happen that when the buffer is full the upstream machine is not allowed to release a completed job. Blocking implies that the completed job has to remain on the upstream machine preventing (i.e., blocking) that machine from working on the next job. The most common occurrence of blocking that is considered in this book is the case with zero buffers in between any two successive machines. In this case a job that has completed its processing on a given machine cannot leave the machine if the preceding job has not yet completed its processing on the next machine; thus, the blocked job also prevents (or blocks) the next job from starting its processing on the given machine. In the models with blocking that are considered in subsequent chapters the assumption is made that the machines operate according to FIFO. That is, block implies prmu. No-wait (nwt) The no-wait requirement is another phenomenon that may occur in flow shops. Jobs are not allowed to wait between two successive machines. This implies that the starting time of a job at the first machine has to be delayed to ensure that the job can go through the flow shop without having to wait for any machine. An example of such an operation is a steel rolling mill in which a slab of steel is not allowed to wait as it would cool off during a wait. It is clear that under no-wait the machines also operate according to the FIFO discipline. Recirculation (rcrc) Recirculation may occur in a job shop or flexible job shop when a job may visit a machine or work center more than once. Any other entry that may appear in the β field is self explanatory. For example,pj = p implies that all processing times are equal and dj = d implies that all due dates are equal. As stated before, due dates, in contrast to release dates, are usually not explicitly specified in this field; the type of objective function gives sufficient indication whether or not the jobs have due dates. The objective to be minimized is always a function of the completion times of the jobs, which, of course, depend on the schedule. The completion time of the operation of job j on machine i is denoted by Cij. The tim ejob j exits the system (that is, its completion time on the last machine on which it requires processing) is denoted by Cj . The objective may also be a function of the due dates. The lateness of job j is defined as

   Lj = Cj − dj ,  

   which is positive when job j is completed late and negative when it is completed early. The tardiness of job j is defined as

   Tj = m ax(Cj − dj , 0) = max(Lj, 0).

   The difference between the tardiness and the lateness lies in the fact that the tardiness never is negative. The unit penalty of job j is defined as

   Uj = _1 if Cj > dj 0

    otherwise The lateness, the tardiness and the unit penalty are the three basic due date related penalty functions considered in this book. The shape of these functions are depicted in Figure 2.1. Examples of possible objective functions to be minimized are:  Makespan (Cmax) The makespan, defined as max(C1, . . ., Cn), is equivalent to the completion time of the last job to leave the system. A minimum makespan usually implies a good utilization of the machine(s). Maximum Lateness (Lmax) The maximum lateness, Lmax, is defined as max(L1, . . ., Ln). It measures the worst violation of the due dates. Total weighted completion time (_wjCj) The sumof the weighted completion times of the n jobs gives an indication of the total holding or inventory costs incurred by the schedule. The sum of the completion times is in the literature often referred to as the flow time. The total weighted completion time is then referred to as the weighted flow time. Discounted total weighted completion time (_wj(1−e−rCj)) This is a more general cost function than the previous one, where costs are discounted at a rate of r, 0 < r < 1, per unit time. That is, if job j is not completed by time t an additional cost wjre−rtdt is incurred over the period [t, t + dt]. If job j is completed at time t the total cost incurred over the period [ 0, t ] is wj(1 − e−rt). The value of r is usually close to 0, say 0.1 or 10 %. Total weighted tardiness (_wjTj) This is also a more general cost function than the total weighted completion time. Weighted number of tardy jobs (_wjUj) The weighted number of tardy jobs is not only a measure of academic interest, it is often an objective in practice as it is a measure that can be recorded very easily. All the objective functions above are so-called regular performance measures. A regular performance measure is a function that is nondecreasing in C1, . . ., Cn. Recently researchers have begun to study objective functions that are not regular. For example, when job j has a due date dj , it may be subject to an earliness penalty, where the earliness of job j is defined as

   Ej = m ax(dj − Cj , 0).

   This earliness penalty is nonincreasing in Cj . An objective such as the total earliness plus the total tardiness, i.e.,

   is therefore not regular. A more general objective that is not regular is the total weighted earliness plus the total weighted tardiness, i.e.,

   The weight associated with the earliness of job j (w_j ) m ay be different from the weight associated with the tardiness of job j (w__ j )  

   Classes of Schedules

   In scheduling terminology a distinction is often made between a sequence, a schedule and a scheduling policy. A sequence usually corresponds to a permutation of the n jobs or the order in which jobs are to be processed on a given machine. A schedule usually refers to an allocation of jobs within a more complicate setting of machines, allowing possibly for preemptions of jobs by other jobs that are released at later points in time. The concept of a scheduling policy is often used in stochastic settings: a policy prescribes an appropriate action for any one of the states the system may be in. In deterministic models usually only sequences or schedules are of importance. Assumptions have to be made with regard to what the scheduler may and may not do when he generates a schedule. For example, it may be the case that a schedule may not have any unforced idleness on any machine. This class of schedules can be defined as follows. Definition 2.3.1 (Non-Delay Schedule). A feasible schedule is called non-delay if no machine is kept idle while an operation is waiting for processing. Requiring a schedule to be non-delay is equivalent to prohibiting unforced idleness. For many models, including those that allow preemptions and have regular objective functions, there are optimal schedules that are non-delay. For many models considered in this part of the book the goal is to find an optimal schedule that is non-delay. However, there are models where it may be advantageous to have periods of unforced idleness. A smaller class of schedules, within the class of all non-delay schedules, is the class of nonpreemptive non-delay schedules. Nonpreemptive non-delay schedules may lead to some interesting and unexpected anomalies. Definition 2.3.2 (Active Schedule). A feasible nonpreemptive schedule is called active if it is not possible to construct another schedule, through changes in the order of processing on the machines, with at least one operation finishing earlier and no operation finishing later.In other words, a schedule is active if no operation can be put into an empty hole earlier in the schedule while preserving feasibility. A nonpreemptive nondelay schedule has to be active but the reverse is not necessarily true. The following example describes a schedule that is active but not non-delay. Definition 2.3.3 (Semi-Active Schedule). A feasible nonpreemptive schedule is called semi-active if no operation can be completed earlier without changing the order of processing on any one of the machines. It is clear that an active schedule has to be semi-active. However, the reverse is not necessarily true. Single Machine Models (Deterministic) Single machine models are important for various reasons. The single machine environment is very simple and a special case of all other environments. Single machine models often have properties that neither machines in parallel nor machines in series have. The results that can be obtained for single machine models not only provide insights into the single machine environment, they also provide a basis for heuristics that are applicable to more complicated machine environments. In practice, scheduling problems in more complicated machine environments are often decomposed into subproblems that deal with single machines. For example, a complicated machine environment with a single bottleneck may give rise to a single machine model. In this chapter various single machine models are analyzed in detail. The total weighted completion time objective is considered first, followed by several due date related objectives, including the maximum lateness, the number of tardy jobs, the total tardiness and the total weighted tardiness. All objective functions considered in this chapter are regular. In most models considered in this chapter there is no advantage in having  preemptions; for these models it can be shown that the optimal schedule in the class of preemptive schedules is nonpreemptive. However, if jobs are released at different points in time, then it may be advantageous to preempt. If jobs are released at different points in time in a nonpreemptive environment, then it may be advantageous to allow for unforced idleness (i.e., an optimal schedule may not be non-delay). 3.1 The Total Weighted Completion Time The first objective to be considered is the total weighted completion time, i.e., 1 || _wjCj. The weight wj of job j may be regarded as an importance factor; it may represent either a holding cost per unit time or the value already added to job j. This problemg ives rise to one of the better known rules in scheduling theory, the so-called Weighted Shortest Processing Time first (WSPT) rule. According to this rule the jobs are ordered in decreasing order of wj/pj. Theorem 3.1.1. The WSPT rule is optimal for Proof. By contradiction. Suppose a schedule S, that is notWSPT, is optim al. In this schedule there must be at least two adjacent jobs, say job j followed by job k, such that

   Assume job j starts its processing at time t. Performa so-called Adjacent Pairwise Interchange on jobs j and k. Call the new schedule S_. While under the original schedule S job j starts its processing at time t and is followed by job k, under the new schedule S_ job k starts its processing at time t and is followed by job j. All other jobs remain in their original position. The total weighted completion time of the jobs processed before jobs j and k is not affected by the interchange. Neither is the total weighted completion time of the jobs processed after jobs j and k. Thus the difference in the values of the objectives under schedules S and S_ is due only to jobs j and k (see Figure 3.1). Under S the total weighted completion time of jobs j and k is ( + pj)wj + (t + pj + pk)wk, while under S_ it is (t + pk)wk + (t + pk + pj)wj . It is easily verified that if wj/pj < wk/pk the sumof the two weighted completion times under S_ is strictly less than under S. This contradicts the optimality of S and completes the proof of the theorem The computation time needed to order the jobs according to WSPT is the time required to sort the jobs according to the ratio of the two parameters. A simple sort can be done in O(n lo g(n)) time, see Example D.1.1 in Appendix D. How is the minimization of the total weighted completion time affected by precedence constraints? Consider the simplest form of precedence constraints, i.e., precedence constraints that take the formof parallel chains This problemca n still be solved by a relatively simple and very efficient (polynomial time) algorithm. This algorithm is based on some fundamental properties of scheduling with precedence constraints. Consider two chains of jobs. One chain, say Chain I, consists of jobs 1, . . . , k and the other chain, say Chain II, consists of jobs k +1, . . . , n. The precedence constraints are as follows:

   1 → 2→・ ・ ・→k

   and

   k + 1 → k + 2→・ ・ ・→n.

   The next lemma is based on the assumption that if the scheduler decides to start processing jobs of one chain he has to complete the entire chain before he is allowed to work on jobs of the other chain. The question is: if the scheduler wishes to minimize the total weighted completion time of the n jobs, which one of the two chains should he process first?

   Lemma 3.1.2. If

   then it is optimal to process the chain of jobs 1, . .. , k before (after) the chain of jobs k + 1, . . , n. Proof. By contradiction. Under sequence 1, . . . , k, k+1, . . . , n the total weighted completion time is

   while under sequence k + 1, . . . , n, 1, . . . , k it is

   The total weighted completion time of the first sequence is less than the total weighted completion time of the second sequence if

   The result follows. An interchange between two adjacent chains of jobs is usually referred to as an Adjacent Sequence Interchange. Such an interchange is a generalization of an Adjacent Pairwise Interchange. An important characteristic of chain

   1 → 2→・ ・ ・→k

   is defined as follows: let l∗ satisfy

   The ratio on the left-hand side is called the ρ-factor of chain 1, . . . , k and is denoted by ρ(1, . . . , k). Job l∗ is referred to as the job that determines the ρ-factor of the chain. Suppose now that the scheduler does not have to complete all the jobs in a chain before he is allowed to work on another chain. He may process some jobs of one chain (while adhering to the precedence constraints), switch over to another chain, and, at some later point in time, return to the first chain. If, in the case of multiple chains, the total weighted completion time is the objective function, then the following result holds.

   Theoretical Research

   In the future, theoretical research may well focus on theory and models that have not been covered in Parts I and II of this book. This section considers

               (i) theoretical underpinnings of scheduling,

   (ii) new scheduling formats and assumptions, and

   (iii) theoretical properties of specific models.

   Theoretical underpinnings of scheduling. The theoretical underpinnings will always receive a certain amount of research attention. One theoretical research area within deterministic scheduling deals with polyhedral combinatorics and cutting planes. This research area has already generated for some of the basic scheduling models exact solution methods of the branch-and-cut type (see Appendix A) and also approximation algorithms with good performance guarantees. It is likely that this research will be extended to more general scheduling models. Another form of branch-and-bound, namely branch-and-price, has recently been applied successfully to several parallel machine scheduling problems. Another research direction in deterministic scheduling is the area of Polynomial Time Approximation Schemes (PTAS) for NP-hard problems; this area has received a significant amount of attention in the recent past (see Appendix D). It is likely that this area will receive even more attention in the future and that schemes will be developed for models that are more complicated than those that have been considered up to now. However, it is not clear when these developments will start contributing to the effectiveness of heuristics used in practice. Other types of approximation methods will also be investigated; one very promising class of approximation algorithms is based on Linear Programming relaxations. New scheduling formats and assumptions. The classical scheduling format, covering most models discussed in Part I, can be described as follows: In a given machine environment there are n jobs and all the information concerning the n jobs is available at time zero; a specific objective function has to be minimized and an optimal (or at least a very good) schedule has to be generated from scratch. There are several new and interesting research directions that concern models based on scheduling assumptions that differ significantly from those in Part I of this book. One of the new scheduling formats concerns online scheduling. Online scheduling is important since it is in a way very different from the conventional (offline) deterministic models which assume that all information is known a priori, i.e., before any decision is made. In online scheduling, decisions have to be made based on information regarding the jobs that already have been released and not on information regarding jobs that are to be released in the future. In semi-online scheduling some, but not all, information regarding future job releases is known. The relationships between online scheduling, semi-online scheduling, and stochastic scheduling may receive some attention in the future as well. This seems to be a relatively open research area. Another new format concerns scheduling with multiple agents. In a multiagent scheduling problemeac h agent is responsible for a set of jobs and has his own objective function. The objective functions of the different agents may not be the same. The agents have to share the machine(s) with one another. A multi-agent problem is different from a multi-objective problem: in a multiobjective problemeac h job contributes to all objectives whereas in amulti-agent problemea ch job contributes to only one of the objectives (i.e., the objective of his agent). Multi-agent problems have several important applications. For example, maintenance scheduling problems can be formulated as multi-agent  problems. A third format comprises sequencing and scheduling games. In a scheduling game there are multiple players who have to share one (or more) machine(s) with each other; each player is responsible for a set of jobs and has his own objective function. Research in sequencing and scheduling games typically focuses on issues that are different fromt hose studied in other classes of scheduling problems. When analyzing a scheduling game, one tends to be interested in certain structural properties of the game (e.g., the conditions under which a  game is balanced or convex), whereas in most other types of scheduling problems one is interested in algorithms that generate optimal schedules for specific objective functions. There are various different types of scheduling games. One important class of scheduling games are the so-called cooperative scheduling games. In a cooperative scheduling game an initial schedule is given. Players can formco alitions and the players within a coalitionmay reschedule (or swap) their jobs among themselves; however, jobs belonging to players outside the coalition may not be completed later than they did in the initial schedule. In the new schedule, some players in the coalition may have a lower penalty cost, while others may have a higher penalty cost. A distribution mechanism has to be designed that allocates the benefits of the rescheduling over all the players within the coalition. Certain distribution mechanisms are referred to as core allocations. A cooperative scheduling game actually exhibits some similarities to competitive agent scheduling problems. The jobs that belong to a coalition may be regarded as jobs that belong to an agent and the sequence of the jobs within each coalition has to be optimized. Two coalitions can form a grand coalition and develop thus a joint schedule. The formation of a grand coalition can be compared to two competitive agents creating a joint schedule for their two sets of jobs. A fourth, entirely different format, is based on the rescheduling concept. Rescheduling has been touched upon briefly in Chapter 18. However, a formal theoretical framework for the analysis of rescheduling problems has not yet been established. A rescheduling problemm ay have multiple objectives: the objective of the original problem(e.g ., the total weighted tardiness) and the minimization of the difference between the new schedule (after rescheduling) and the old schedule (before rescheduling). It may be necessary to have formal definitions or functions that measure the ”difference” or the ”similarity” between two schedules for the same job set or between two schedules for two slightly different job sets, e.g., one job set having all the jobs of a second set plus one additional job (a rush job). The rescheduling process may also have to deal with ”frozen” jobs, i.e., jobs that have been assigned earlier to certain time slots and that may not be moved. Sometimes the constraints on the frozen jobs do allow the scheduler to make some minor adjustments in the timing of the processing of these jobs. A frozen job may be started slightly earlier or slightly later. That is, there may be a time range in which a frozen job can be processed (there may be a limited amount of slack). Scheduling around frozen jobs tends to be similar to dealing with machine breakdowns or with preventive maintenance schedules (i.e., scheduling subject to availability constraints). However, there may be a difference due to the fact that data regarding frozen jobs tend to be deterministic, whereas data concerning machine breakdowns tend to be stochastic. The concept of robustness is closely related to rescheduling and deserves more attention in the future as well. Chapter 18 gives a relatively short treatment of this topic. It presents a number of robustness measures as well as several practical rules for constructing robust schedules. However, very little theoretical research has been done with regard to these rules. At this point it is not clear how useful these rules are in the various different scheduling environments. Theoretical properties of specific models. One such research area deals with models that combine deterministic features with stochastic features. For example,consider a model with jobs that have deterministic processing times and due dates, and machines that are subject to a random breakdown process. Such a model may be quite realistic in many environments. Only very special cases are tractable. For example, a single machine with up times that are i.i.d. exponential and down times that all have the same mean can be analyzed. The WSPT rule then minimizes the total expected weighted completion time. However, it may be of interest to study more complicated machine environments in which the machines are subject to more general forms of breakdown processes. Since such models tend to be more complicated than the more classical models described in Parts I and II of this book, the types of results one can expect may be of a more structural nature. Structural results may, for example, include proofs for dominance criteria or proofs for monotonicity results.