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.

   Applied Research .

   Applied research may go a little bit deeper into some of the topics covered in Part III of this book. The applied topics described in this section include (i) performance analyses of heuristics, (ii) robustness and reactive scheduling, and (iii) integrated scheduling models. Performance analysis of heuristics is a very important area of empirical and experimental research. Currently, many job shop problems can only be dealt with on a small scale. For example, it is still very hard to find an optimal solution for an instance of Jm || _wjTj with, say, 10 machines and 30 jobs. If  there are multiple objectives and a parametric analysis has to be done, then the problemb ecomes even harder. Many different types of heuristics are available, but it is not clear how effective they are in dealing with large scale scheduling problems, e.g., job shop scheduling problems with two or three objectives and with, say, 50 machines and 1000 jobs. The heuristics for these large scale job shops may require continuous improvement and fine-tuning in the future. Heuristics can be compared to one another with respect to several criteria. In practice, three criteria are important. First, the quality of the solution obtained; second, the amount of computer time needed to generate a good solution; third, the time required to develop and implement the heuristic. Comparative studies of heuristics conducted in academic environments typically take only the first two criteria into account. However, in an industrial environment the third criterion is of critical importance. In industry it is important that the time needed to develop a heuristic be short. This is one of the reasons why in practice local search heuristics are often more popular than very sophisticated decomposition techniques such as the shifting bottleneck heuristic. The performance of any heuristic depends, of course, on the structure of the scheduling problem, e.g., the type of routing constraints in job shops. The performance may even depend on the particular data set. Often, when one deals with a unary NP-hard problem, it turns out that most instances can be solved to optimality in a reasonably short time; however, some instances may turn out be very hard to solve and may require an enormous amount of computing time before reaching optimality. It is of interest to find out why such instances are hard to solve. Empirical studies indicate that a heuristic often may perform quite well when the data of an instance are generated randomly, whereas that heuristic may perform quite poorly when it is applied to an instance of that same problemwith data froma n industrial setting. (Itmay be the case that industrial data have certain dependencies and correlations that make such instances hard to solve.) It would be useful to establish rules that indicate the type of algorithm that is most suitable for the type of instance under consideration. In order to characterize a probleminsta nce properly, one may want to have a number of suitable descriptive factors, such as, for example, the due date tightness factor τ defined in Chapter 14. One may also have to assess proper weights to each one of the factors. It would be useful to know which type of algorithmis most suitable for a given instance when the following is known: the size of the instance (the scale), the values of characteristic factors, and the computer time available. An important class of heuristic methods comprises local search procedures. The last two decades have seen an enormous amount of work on applications and implementations of local search procedures. This research has yielded interesting results with regard to neighbourhood structures. However, most of this research has focused on nonpreemptive scheduling. Preemptive scheduling has received very little attention fromresearc hers specializing in local search procedures. One reason is that it tends to be more difficult to design an effective neighbourhood structure for a preemptive environment than for a nonpreemptive environment. It may be of interest to focus attention first on problems that allow preemptions only at certain well-defined points in time, e.g., when new jobs are released.It is likely that in the future there will be a certain demand for industrial strength heuristics that are applicable to scheduling problems common in industry. Consider, for example, the problem Qm | rj, sjk | θ1_wjTj+θ2Cmax. This scheduling problemis typical in many process industries. The two objectives are quite common: One objective focuses on the due dates and the other tries to balance the loads over the machines and minimize setup times. In the future, heuristics may be developed that are problem-specific and that can be linked easily to a variety of scheduling systems. These industrial strength heuristics may be hybrids that make use of Operations Research (OR) techniques as well as Artificial Intelligence (AI) techniques. For example, such a hybrid may combine an integer programming procedure with a constraint-based local search procedure. Robustness and reactive scheduling. A completely different line of empirical research involves robustness and rescheduling. As stated in the previous section, the concepts of robustness and rescheduling may lead to interesting theoretical research. However, they may lead to even more interesting empirical and experimental research. New measures for robustness have to be developed. The definition of these measures may depend on the machine environment.  Integrated Scheduling models. More practical models often combine machine scheduling aspects with other aspects, such as inventory control, workforce scheduling, maintenance scheduling, capacity control or pricing. For example, in supply chains the production scheduling function is often tied to inventory control and to transportation scheduling. The models that are useful for the analysis of such real world environments tend to be more involved than the simpler machine scheduling models considered in this book. However, in the analysis of these more complicated models one may often have to resort to decomposition methods that partition the problem into a number of different modules. The smaller modules can then be tackled more easily using procedures that are described in this book. For example, in the airline industry, planes and crews have to be scheduled in a coherent way. An extensive amount of research has been done on pure personnel scheduling (independent of machine scheduling), but little research has been done on models that combine personnel scheduling with machine scheduling. Some more theoretical research has been done in other areas related to these types of problems, namely resource constrained scheduling (i.e., a limited number of personnel may be equivalent to a constraining resource). However, research in resource constrained scheduling has typically focused on complexity analysis and on worst case analysis of heuristics. It may be of interest in the future to study more specific models that combine machine scheduling with personnel scheduling. There are many scheduling applications in the information systems world. Nowadays, distributed computer systems are connected to one another in socalled grid environments in which users can submit jobs that are automatically assigned to appropriate resources. The performance of a grid computing system depends heavily on the underlying scheduling procedures. A grid scheduling systemop erates on the premise that a new job that is in need of processing must make itself known to the ”resource selector”. In current systems, the resource selector acts as a gateway to the grid. It will select resources from a global directory and then allocates the job to one of the nodes on the grid. Typically, a job allocation is done in two phases. First, a job is allocated to a node on the grid, and second, within that node, the job is scheduled onto the processor. The first phase is referred to as resource allocation, whereas the second phase is referred to as job scheduling. The last decade has seen a fair amount of development and implementation of grid scheduling systems. However, it seems that less attention has been paid to the more theoretical and algorithmic aspects of these systems. 

   Systems Development

   Systems development may focus in the future a little bit more on some of the topics covered in Part III of this book. In this section the topics discussed include

   (i) problemdeco mposition and distributed scheduling,

   (ii) user interfaces and interactive optimization,

   (iii) scheduling description languages, and

   (iv) integration within supply chain management systems.

   Problem decomposition and distributed scheduling. Dealing with large scale scheduling problems may lead to implementations of distributed scheduling. Many industrial problems are so large that they cannot be solved on a single workstation. The computational effort has to be divided over a number of workstations or computers that may reside at different locations. With certain procedures the computational effort can be divided up rather easily whereas with other procedures it may not be that easy. For example, when a problem is solved via branch-and-bound it may be relatively easy to decompose the branching tree and partition the computational work involved. At periodic intervals the different workstations still have to compare their progress and share information (e.g., compare their best solutions found so far). If a problem is solved via time based decomposition, then distributed scheduling may also be applicable (as long as the schedules of the different periods are somewhat independent of one another). With the latest Internet technologies, distributed scheduling may become increasingly more important in the future. User interfaces and interactive optimization. The development of user interfaces and interactive optimization may face some interesting hurdles in the future. The designs of the user interfaces have to be such that interactive optimization can be done easily and effectively. A scheduler must maintain at all times a good overview of the schedule, even when the schedule contains over a thousand jobs. The user interface must have abilities to zoom in and out of a schedule easily. In order to allow for interactive optimization the user interface must have provisions for clicking, dragging and dropping operations, freezing operations, dealing with cascading and propagation effects, and rescheduling. After the user makes some manual changes in the system, the system may reschedule automatically in order to maintain feasibility (without any user input). The (internal) algorithms that are used to maintain schedule feasibility may be relatively simple; they may only postpone some operations. However, internal algorithms may also be more involved and may perform some internal reoptimization (that is done automatically). On the other hand, the reoptimization process may also be managed by the user; he may want to specify the appropriate objective functions for the reoptimization process. Reoptimization algorithms may be very different from optimization algorithms that generate schedules from scratch. The main reason why reoptimizing is harder than optimizing fromscr atch is because an algorithmtha t reoptimizes has to deal with boundary conditions and constraints that are dictated by the original schedule. Embedding rescheduling algorithms in a user interface that enables the user to optimize schedules interactively is not easy. Scheduling description languages. Composition and integration of procedures have led to the development of so-called scheduling description languages. A scheduling description language is a high level language that enables a scheduler to write the code for a complex algorithm with only a limited number of concise statements or commands. Each statement in a description language involves the application of a relatively powerful procedure. For example, a statement may give an instruction to apply a tabu search procedure on a given set of  jobs in a given machine environment. The input to such a statement consists of the set of jobs, the machine environment, the processing restrictions and constraints, the length of the tabu-list, an initial schedule, and the maximum number of iterations. The output consists of the best schedule obtained with the procedure. Other statements may be used to set up various different procedures in parallel or to concatenate two different procedures. Scheduling description languages are not yet very popular. However, the existing languages are still somewhat cumbersome and need streamlining. It is likely that there will be some improvement in the future. Integration within supply chain management systems. Many companies had started out initially with developing scheduling software for the manufacturing industry. However, they soon realized that in order to compete in the market place they had to offer software dealing with all aspects of supply chain management. The types of modules that are required in supply chain optimization include, besides planning and scheduling, forecasting, demand management, inventory control, and so on. Scheduling problems in supply chain management have to take forecasts, inventory levels and routings into consideration. These integrated scheduling problems are considerably harder than the more  lementary problems studied in the research literature. The structure and the organization of the software must be well designed and modular.

   Deterministic and Stochastic

   Dynamic Programming

   Dynamic programming is one of the more widely used techniques for dealing with combinatorial optimization problems. Dynamic Programming can be applied to problems that are solvable in polynomial time, as well as problems that cannot be solved in polynomial time (see Appendix C). It has proven to be very useful for stochastic problems as well.

   B.1 Deterministic Dynamic Programming

   Dynamic programming is basically a complete enumeration scheme that attempts, via a divide and conquer approach, to minimize the amount of computation to be done. The approach solves a series of subproblems until it finds the solution of the original problem. It determines the optimal solution for each subproblema nd its contribution to the objective function. At each iteration it determines the optimal solution for a subproblem, which is larger than all previously solved subproblems. It finds a solution for the current subproblem by utilizing all the information obtained before in the solutions of all the previous subproblems. Dynamic programming is characterized by three types of equations, namely

   (i) initial conditions;

   (ii) a recursive relation and

   (iii) an optimal value function.

   In scheduling, a choice can be made between forward dynamic programming and backward dynamic programming. The following example illustrates the use of forward dynamic programming.

   B.2 Stochastic Dynamic Programming

   Dynamic programming is often used in stochastic sequential decision processes, especially when the randomv ariables are exponentially distributed. This class of decision processes is usually referred to as Markovian Decision Processes (MDP’s). An MDP can be characterized, in the same way as a deterministic dynamic program, by

   (i) initial conditions;

   (ii) a recursive relation and

   (iii) an optimal value function

   Constraint Programming

   C.1 Constraint Satisfaction

   C.2 Constraint Programming

   C.3 An Example of a Constraint Programming Language

   C.4Constrai nt Programming vs. Mathematical 

   In contrast to mathematical programming, which has its roots in the Operations Research community, constraint programming has its origins in the Artificial Intelligence and Computer Science communities. Constraint programming can be traced back to the constraint satisfaction problems studied in the 1970’s. A constraint satisfaction problemrequires a search for a feasible solution that satisfies all given constraints. To facilitate the search for a solution to such a problemv arious special purpose languages have been developed, e.g., Prolog. However, during the last decade of the twentieth century, constraint programming has not only been used for solving feasibility problems, but also for solving optimization problems. Several approaches have been developed that facilitate the application of constraint programming to optimization problems. One such approach is via the Optimization Programming Language (OPL), which was designed for modeling and solving optimization problems through both constraint programming techniques and mathematical programming procedures.

   C.1 Constraint Satisfaction

   To describe the constraint programming framework, it is necessary to first define the constraint satisfaction problem. In order to be consistent with the mathematical programming material presented in Appendix A, it is advantageous to present the constraint satisfaction problem using mathematical programming terminology. Assume n decision variables x1, . . . , xn and let Dj denote the set of allowable values for decision variable xj . This set is typically referred to as the domain of the variable xj . Decision variables can take integer values, real values, as well as set elements. Formally, a constraint is a mathematical relation that implies a subset S of the set D1 ×D2 ×・ ・ ・×Dn such that if (x1, . . . , xn) ∈ S, then the constraint is said to be satisfied. One can also define a mathematical function f such that f(x1, . . . , xn) = 1 if and only if the constraint is satisfied. Using this notation, the Constraint Satisfaction Problem(CSP ) can be defined as follows:

   fi(x1, . . . , xn) = 1, i= 1, . . .,m       xj ∈ Dj j = 1, . . . , n

   Since the problemis only a feasibility problem, no objective function has to be defined. The constraints in the constraint set may be of various different types: they may be linear, nonlinear, logical combinations of other constraints,cardinality constraints, higher order constraints or global constraints. One basic difference between the constraints in a mathematical programming formulation and the constraints in a constraint satisfaction problem lies in the fact that the constraints in a mathematical programming formulation are typically either linear or nonlinear, whereas the constraints in a constraint programming formulation can be of a more general form. Constraint Satisfaction is typically solved via a tree search algorithm. Each node in the search tree corresponds to a set of domains D_1 ×D_2 ×・ ・ ・×D_n such that D_j ⊂ Dj . In other words, a node is nothing more than a contraction of the original domains that has not yet proven infeasible. The tree search algorithm can branch fromon e node to another by assigning a value to a problemv ariable. 
 

At each node, the following operations have to be performed:

   WHILE not solved AND not infeasible DO

   consistency checking (domain reduction)

   IF a dead-end is detected THEN

   try to escape fromd ead-end (backtrack)

   ELSE

   select variable

   assign value to variable

   ENDIF

   ENDWHILE

   The selection of the next variable and the assignment of its value is done by variable selection heuristics and value assignment heuristics. In job shop scheduling a variable typically corresponds to an operation and the value corresponds to its starting time. After a value is assigned to a variable, inconsistent values of unassigned variables are deleted. The process of removing inconsistent values is often referred to as consistency checking or domain reduction. One well-known technique of consistency checking is constraint propagation. For a variable x, the current domain δ(x) is the set of values for which no inconsistency can be found with the available consistency checking techniques. If, after removing inconsistent values from the current domains, a current domain has become empty, a so-called dead-end has been reached. A dead-end means that either the original problem is infeasible or that some of the branching decisions made from the root of the tree down to this point has created an infeasibility. In such a case, the algorithm has to backtrack; that is, one or more assignments of variables have to be undone and alternatives have to be tried out. An instance is solved if every variable is assigned a value; an instance is shown to be infeasible if for a variable in the root of the tree no values are remaining to be tried. If constraint satisfaction is applied to the job shop problemin Chapter 7, then the problemis to verify whether there exists a feasible job shop schedule with a makespan Cmax that is less than a given value z∗. Domain reduction in job shop scheduling boils down to the following: Given the partial schedule already constructed, each operation yet to be scheduled has an earliest possible starting time and a latest possible completion time (which are basically equivalent to a release date and a due date). Whenever the starting time and completion time of an operation are fixed, some form of checking has to be done on how the newly scheduled (fixed) operation affects the earliest possible starting times and latest possible completion times of allthe operations that still remain to be scheduled. The earliest possible starting time of a yet to be scheduled operation may now have to be set later while the latest possible completion time of that operation may now have to be set earlier. Note that constraint satisfaction requires the specification of an actual makespan; this allows the procedure to construct a schedule going forward in time as well as backward in time. A branch-and-bound approach, on the other hand, often constructs a schedule going forward in time whenever the makespan is not known a priori (see, for example, Sections 3.2 and 7.1). 
 
 

   C.2 Constraint Programming 

   Originally, constraint satisfaction was used only to find feasible solutions for problems. However, the constraint satisfaction structure, when embedded in a more elaborate framework, can be applied to optimization (e.g., minimization) problems as well. An optimization problem may be formulated as follows:

   minimize g(x1, . . . , xn)

   subject to

   fi(x1, . . . , xn) = 1, i= 1, . . .,m

   xj ∈ Dj j = 1, . . . , n

   The standard search procedure for finding the optimal solution is to first find a feasible solution to the Constraint Satisfaction Problem, while ignoring the objective function. Let y1, . . . , yn represent such a feasible solution. Let z∗ = g(y1, . . . , yn) and add the constraint g(x1, . . . , xn) < z∗

   to the constraint set and solve this modified Constraint Satisfaction Problem. The additional constraint forces the new feasible solution to have a better objective  value than the current one. Constraint propagation may cause the domains of the decision variables to be narrowed, thus reducing the size of the search space. As the search goes on, new solutions must have progressively better objective values. The algorithmter minates when no feasible solution is found; when this happens, the last feasible solution found is optimal. A more sophisticated and efficient search procedure, often referred to as dichotomic search, requires at the outset a good lower bound L on the objective g(x1, . . . , xn). The procedure must also find an initial feasible solution that represents an upper bound U on the objective function. The dichotomic search procedure essentially performs a binary search on the objective function. The procedure computes the midpoint

   M= (U + L) 2

   of the two bounds and then solves the constraint satisfaction problemwith the added constraint

   g(x1, . . . , xn) <M

   If it finds a feasible solution, then the new upper bound is set equal to M and the lower bound is kept the same; a new midpoint is computed and the search continues. If it does not find a feasible solution, then the lower bound  is set equal to M and the upper bound is kept the same; a new midpoint is computed and the search continues. Dichotomic search is effective when the lower bound is strong, because the computational time that is needed to show that a constraint satisfaction problem do es not have a feasible solution may be very long. Constraint programming can be described as a two-level architecture that at one level has a list of constraints (sometimes referred to as a constraint store) and at the other level a programming language component that specifies the organization and the sequence in which the basic operations are executed. One fundamental feature of the programming language component is its ability to specify a search procedure.

   C.3A n Example of a Constraint Programming Language

   The Optimization Programming Language (OPL) was developed during the last decade of the twentieth century to deal with optimization problems through a combination of constraint programming techniques and mathematical programming techniques.This section describes a constraint programdesigned for the job shop problem  Jm || Cmax that is considered in Chapter 7. Example C.3.1 (An OPL Program for a Job Shop)

   An OPL programfo r the job shop problem Jm || Cmax can be written as

   follows:

   01. int nbMachines = . . .;

   02. range Machines 1..nbMachines;

   03. int nbJobs = . . .;