Planning and Scheduling in Manufacturing and Services

Planning and scheduling are forms of decision-making that are used on a regular basis in many manufacturing and service industries. Decision-making processes play an important role in procurement and production, in transportation and distribution, and in information processing and communication. The planning and scheduling functions in a company rely on mathematical techniques and heuristic methods that allocate limited resources to the activities to be done. This allocation of resources has to be done in such a way that the company optimizes its objectives and achieves its goals. Resources may be machines in a workshop, runways at an airport, crews at a construction site, or processing units in a computing environment. Activities may be operations in a workshop, take-offs and landings at an airport, stages in a construction project, or computer programs that have to be executed. Each activity may have a priority level, an earliest possible starting time and/or a due date. Objectives can take many different forms, such as minimizing the time to complete all activities, minimizing the number of activities that are completed after the committed due dates, and so on.

The following ten examples illustrate the role of planning and scheduling in the real world. Each example describes a particular type of planning and scheduling problem. The first example shows the role of planning and scheduling in the management of a large construction or installation project that consists of many stages.

Manufacturing systems can be characterized by a variety of factors: the number of resources or machines, their characteristics and configuration, the level of automation, the type of material handling system, and so on. The differences in all these characteristics give rise to a large number of different planning and scheduling models. In a manufacturing model, a resource is usually referred to as a “machine”; a task that has to be done on a machine is typically referred to as a “job”. In a production process, a job may be a single operation or a collection of operations that have to be done on various different machines. Before describing the main characteristics of the planning and scheduling problems considered in Part II of this book, we give a brief overview of five classes of manufacturing models.

The first class of models are the project planning and scheduling models. Project planning and scheduling is important whenever a large project,that consists of many stages,h as to be carried out. A project,su ch as the construction of an aircraft carrier or a skyscraper,t ypically consists of a number of activities or jobs that may be subject to precedence constraints. A job that is subject to precedence constraints cannot be started until certain other jobs have been completed. In project scheduling,it is often assumed that there are an unlimited number of machines or resources,so that a job can start as soon as all its predecessors have been completed. The objective is to minimize the completion time of the last job,com monly referred to as the makespan. It is also important to find the set of jobs that determines the makespan,as these jobs are critical and cannot be delayed without delaying the completion of the entire project. Project scheduling models are also important in the planning and scheduling of services. Consider,fo r example, the planning and scheduling of a large consulting project.

Service industries are in many aspects different from manufacturing industries. A number of these differences affect the planning and the scheduling of the activities involved. One important difference can be attributed to the fact that in manufacturing it is usually possible to inventorize goods (e.g., raw material, Work-In-Process, and finished products), whereas in services there are typically no goods to inventorize. The fact that in manufacturing a job can either wait or be completed early affects the structure of the models in a major way. In service industries, a job tends to be an activity that involves a customer who does not like to wait. Planning and scheduling in service industries is, therefore, often more concerned with capacity management and yield management.

A second difference is based on the fact that in manufacturing the number of resources (which are typically machines) is usually fixed (at least for the short term),whereas in services the number of resources (e.g., people, rooms, and trucks) may vary over time. This variable may even be a part of the objective function.

A third difference is due to the fact that denying a customer a service is a more common practice than not delivering a product to a customer in a manufacturing setting. This is one of the reasons why revenue management plays such an important role in service industries.

This chapter focuses on the planning and scheduling of jobs that are subject to precedence constraints. The setting may be regarded as a parallel machine environment with an unlimited number of machines. The fact that the jobs are subject to precedence constraints implies that a job can start with its processing only when all its predecessors have been completed. The objective is to minimize the makespan while adhering to the precedence constraints. This type of problem is referred to as a project planning and scheduling problem.

A more general version of the project planning and scheduling problem assumes that the processing times of the jobs are not entirely fixed in advance. A project manager has some control on the durations of the processing times of the different jobs through the allocation of additional funds from a budget that he has at his disposal. Since a project may have a deadline and a completion after its deadline may entail a penalty, the project manager has to analyze the trade-off between the costs of completing the project late and the costs of shortening the durations of the individual jobs.

These types of planning and scheduling problems often occur in practice when large projects have to be undertaken. Examples of such projects are real estate developments,construction of power generation centers,sof tware developments, and launchings of spacecraft. Other applications include projects in the defense industry,suc h as the design,dev elopment and construction of aircraft carriers and nuclear submarines.

This chapter focuses on job shops. There are n jobs and each job visits a number of machines following a predetermined route. In some models a job may visit any given machine at most once and in other models a job may visit each machine more than once. In the latter case it is said that the job shop is subject to recirculation. A generalization of the basic job shop is a so-called flexible job shop. A flexible job shop consists of a collection of workcenters and each workcenter consists of a number of identical machines in parallel. Each job follows a predetermined route visiting a number of workcenters; when a job visits a workcenter, it may be processed on any one of the machines at that workcenter.

Job shops are prevalent in industries where each customer order is unique and has its own parameters. Wafer fabs in the semiconductor industry often function as job shops; an order usually implies a batch of a certain type of item and the batch has to go through the facility following a certain route with given processing times. Another classical example of a job shop is a hospital. The patients in a hospital are the jobs. Each patient has to follow a given route and has to be treated at a number of different stations while going through the system.

Flexible assembly systems differ in a number of ways from the job shops considered in the previous chapter. In a job shop, eac h job has its own identity and may be different from all other jobs. In a flexible assembly system, there are typically a limited number of different product types and the system has to produce a given quantity of each product type. So two units of the same product type are identical.

The movements of jobs in a flexible assembly system are often controlled by a material handling system, which imposes constraints on the starting times of the jobs at the various machines or workstations. The starting time of a job at a machine is a function of its completion time on the previous machine on its route. A material handling system usually also limits the number of jobs waiting in buffers between machines.

In this chapter we analyze three different models for flexible assembly systems. The machine environments in the three models are similar to the machine environments of a flow shop or a flexible flow shop. However,the models tend to be more complicated than the models considered in Chapter 5. This is mainly because of the additional constraints that are imposed by the material handling systems.

In a job shop,eac h job has its own identity and its own set of processing requirements. In a flexible assembly system,there are a number of different types of jobs and jobs of the same type have identical processing requirements; in such a system,set up times and setup costs are often not important and a schedule may alternate many times between jobs of different types. In a flexible assembly system an alternating schedule is often more efficient than a schedule with long runs of identical jobs.

In the models considered in this chapter,a set of identical jobs may be large and setup times and setup costs between jobs of two different types may be significant. A setup typically depends on the characteristics of the job about to be started and the one just completed. If a job’s processing on a machine requires a major setup then it may be advantageous to let this job be followed by a number of jobs of the same type.

In this chapter we refer to jobs as items and we call the uninterrupted processing of a series of identical items a run. If a facility or machine is geared to produce identical items in long runs,then the production tends to be Make-To-Stock,whic h inevitably involves inventory holding costs. This form of production is,at times, also referred to as continuous manufacturing (in contrast to the forms of discrete manufacturing considered in the previous chapters). The time horizon in continuous manufacturing is often in the order of months or even years. The objective is to minimize the total cost,whic h includes inventory holding cost as well as setup cost. The optimal schedule is typically a trade-off between inventory holding costs and setup costs and is often repetitive or cyclic.

This chapter focuses on models and solution approaches for planning and scheduling in supply chains. It describes several classes of planning and scheduling models that are currently being used in systems that optimize supply chains. It also discusses the architecture of the decision support systems that have been implemented in industry and the problems that have come up in the implementation and integration of systems for supply chains. In the implementations considered the total cost in the supply chain has to be minimized, i.e., the stages in the supply chain do not compete with one another in any form, but collaborate in order to minimize total cost.

This chapter basically embeds medium term planning models,suc h as the lot sizing models described in Chapter 7,a nd detailed scheduling models, such as the job shop scheduling models described in Chapter 5,in to a single framework. The models in this chapter are quite general. There is a network of interconnected facilities and the demands for the various end-products may not be stationary. The planning and scheduling may be done at the same point in time but with different horizons and with different levels of detail.

This chapter considers two types of timetabling problems. The first type of timetabling problem assumes that all operators are identical, i.e., the operators constitute a single homogeneous workforce. The total number of operators available is W and in order to do activity j on one of the resources W _j operators have to be present. If the sum of the people required by activities j and k is larger than W (i.e., W _j + W _k > W), then activities j and k may not overlap in time. This type of timetabling is in what follows referred to as timetabling with workforce or personnel constraints.

In this chapter we often make a distinction between the feasibility version of a problem and its optimization version. In the feasibility version we need to determine whether or not a feasible schedule exists; in the optimization version an objective has to be minimized. If no efficient algorithm exists for the feasibility version, then no efficient algorithm exists for the optimization version either.

Throughout this chapter we assume that all data are integer and that preemptions are not allowed.

The previous chapter covered the basics of interval scheduling and timetabling. The models considered were relatively simple and their main goal was to provide some insights. In practice, there are many, more complicated applications of interval scheduling and timetabling. For example, there are important applications in sports as well as in entertainment, e.g., the scheduling of games in tournaments and the scheduling of commercials on network television.

This chapter covers basically two topics, namely tournament scheduling and the scheduling of programs on network television. These two topics turn out to be somewhat related. The next section focuses on some theoretical properties of tournament schedules that are prevalent in U.S. college basketball, major league baseball, and European soccer; this section also presents a general framework for tackling the associated optimization problems via integer programming. The third section describes a completely different procedure for dealing with the same problem, namely the constraint programming approach. The fourth section looks at two tournament scheduling problems that are slightly different from the one discussed in the second and third section, and the solution techniques used are based on local search. The fifth section considers a scheduling problem in network television, i.e., how to schedule the programs in order to maximize overall ratings. The subsequent section contains a case study in tournament scheduling; the tournament considered being a college basketball conference. This particular tournament scheduling problem has been tackled with integer programming as well as with constraint programming techniques. The last section discusses the similarities and differences between the different models and approaches considered in this chapter.

The second section of this chapter focuses on oil tanker scheduling. These models are used in practice in a rolling horizon manner. Among all models discussed in this chapter, this one is the easiest to formulate. The subsequent section considers aircraft routing and scheduling. In aircraft routing and scheduling the goal is to create a periodic (daily) timetable. In a certain sense this model is an extension of the model for oil tanker scheduling. The integer programming formulation of the aircraft routing and scheduling problem is very similar to the formulation described for the oil tanker scheduling problem; however, in the airline case there are additional constraints that enforce periodicity. The fourth section discusses timetabling of trains. Track capacity constraints in railway operations specify that one train can pass another only at a station, and not in between stations. The fifth section describes the airline routing and scheduling systems designed and implemented by Jeppesen Systems. The discussion section focuses on the similarities and differences between tanker scheduling, a irline routing and scheduling, and train timetabling.

In most countries the health care industry represents a significant percentage of the Gross National Product. With the aging of the population, health care costs have been going up considerably over the last couple of decades. For these reasons, many governments have begun to look into the productivity of their health care industries.

Health care productivity is to a great extent based on the proper planning and scheduling of all the activities involved. The variety in planning and scheduling processes in health care turns out to be immense. This chapter focuses on just a few of these processes.

This chapter also considers other planning and scheduling problems that are of importance in health care. For example,the planning and scheduling of radiotherapy treatments (which is a special case of an appointment scheduling problem). Another example of a planning and scheduling problem in a health care setting that is considered in this chapter is the assignment of physicians to emergency room shifts. This problem is a special case of a workforce scheduling problem. (Workforce scheduling and staffing will be considered in more detail in the next chapter.)

Workforce allocation and personnel scheduling deal with the arrangement of work schedules and the assignment of personnel to shifts in order to cover the demand for resources that vary over time. These problems are very important in service industries,e.g ., telephone operators, hospital nurses,p olicemen, transportation personnel (plane crews,bus drivers),a nd so on. In these environments the operations are often prolonged and irregular and the staff requirements fluctuate over time. The schedules are typically subject to various constraints dictated by equipment requirements,unio n rules, and so on. The resulting problems tend to be combinatorially hard.

In this chapter we first consider a somewhat elementary personnel scheduling problem for which there is a relatively simple solution.We then describe an integer programming framework that encompasses a large class of personnel scheduling problems. We subsequently consider a special class of these integer programming problems, namely the cyclic staffing problems. This class of problems has many applications in practice and is easy from a combinatorial point of view. We then consider several special cases and extensions of cyclic staffing. In the sixth section we discuss the crew scheduling problems that occur in the airline industry. In the subsequent section we describe a case that involves the scheduling of operators in a call center.

Analyzing a planning or scheduling problem and developing a procedure for dealing with it on a regular basis is, in the real world, only part of the story. The procedure has to be embedded in a system that enables the decisionmaker to actually use it. The system has to be integrated into the information system of the organization, which can be a formidable task. This chapter deals with system design and implementation issues.

The next section presents an overview of the infrastructure of the information systems and the architecture of the decision support systems in an enterprise. We focus on planning and scheduling systems in particular. The third section covers database, object base, and knowledge-base issues. The fourth section describes the modules that generate the plans and schedules, while the fifth discusses user interface issues and interactive optimization. The sixth section describes the advantages and disadvantages of generic systems and application-specific systems, while the last section discusses implementation and maintenance issues.

This chapter focuses on a number of issues that have come up in recent years in the design, development, and implementation of planning and scheduling systems. The next section discusses issues concerning uncertainty, robustness and reactive decision making. In practice, plans or schedules often have to be changed because of random events. The more robust the original plan or schedule is, the easier the replanning or rescheduling process is. This section focuses on the generation of robust plans and schedules as well as the measurement of their robustness. The third section considers machine learning mechanisms. A system cannot consistently generate good solutions that are to the liking of the user. The decision-maker often has to tweak the plan or schedule generated by the system in order to make it usable. A well-designed system can learn from adjustments made by the user in the past; the mechanism that allows the system to do so is typically referred to as a learning mechanism. The fourth section focuses on the design of planning and scheduling engines. An engine often contains a library of algorithms and routines. One procedure may be more appropriate for one type of instance or data set, while another procedure may be more appropriate for another type of instance. The user should be able to select, for each instance, which procedure to apply. It may even be the case that a user would like to tackle an instance using a combination of various procedures. This fourth section discusses how a planning or scheduling engine should be designed in order to enable the user to adapt and combine algorithms in order to achieve maximum effectiveness. The fifth section focuses on reconfigurable systems. Experience has shown that the development and implementation of systems is very time consuming and costly. In order to reduce the costs, efforts should be made to maintain a high degree of modularity in the design of the system. If the modules are well designed and sufficiently flexible, they can be used over and over again without any major changes. The sixth section focuses on the design aspects of web-based planning and scheduling systems. This section discusses the effects of networking on the design of such systems. The seventh and last section discusses a number of other issues and presents a view on how planning and scheduling systems may evolve in the future.

With so many different types of applications, it is not surprising that there is such a great variety of planning and scheduling models. Moreover, the numerous solution methods provide a host of procedures for the myriad of problems. Any given application typically requires its own type of planning and scheduling engine as well as customized user interfaces. The overall architecture of a system may therefore be very application-specific. The decision support systems that have been designed for planning and scheduling in the various industries tend to be quite different from one another.

Over the last decade there has been a tendency to build larger systems that have more capabilities and that are better integrated within the ERP system of the enterprise. Especially in the manufacturing world there has been a tendency to design and develop integrated systems with multiple functionalities. Especially in supply chain management the systems (and their underlying models) have become more and more elaborate. The dimensions according to which such a system can be measured include the number of facilities in the network as well as the various time horizons over which the system must optimize. Integration may occur in scope, space and time.