Scheduling in Supply Chain

What is Scheduling?

Scheduling in supply chain management involves determining the timing and sequencing of activities within the production or distribution process to optimize efficiency, minimize costs, and meet customer demand.

Scheduling specifies when labor, equipment, and facilities are needed to produce a product or provide a service. It is the last stage of planning before production takes place.

The scheduling function differs considerably based on the type of operation:

• In process industries, such as chemicals and pharmaceuticals, scheduling might consist of determining the mix of ingredients that goes into a vat or when the system should stop producing one type of mixture, clean out the vat, and start producing another.
  
  Linear programming can find the lowest-cost mix of ingredients, and the production order quantity can determine the optimal length of a production run.
  
  
• For mass production, the schedule of production is pretty much determined when the assembly line is laid out. Products simply flow down the assembly line from one station to the next in the same prescribed, non-deviating order every time.
  
  Day-to-day scheduling decisions consist of determining how fast to feed items into the line and how many hours per day to run the line. On a mixed-model assembly line, the order of products assembled also has to be determined.
  
  
• For projects, the scheduling decisions are so numerous and interrelated that specialized project-scheduling techniques such as PERT and CPM have been devised.
  
  
• For batch or job shop production, scheduling decisions can be quite complex. Scheduling determines to which machine a part will be routed for processing, which worker will operate a machine that produces a part, and the order in which the parts are to be processed.
  
  Scheduling also determines which patient to assign to an operating room, which doctors and nurses are to care for a patient during certain hours of the day, the order in which a doctor is to see patients, and when meals should be delivered, or medications dispensed.

What makes scheduling so difficult in a job shop is the variety of jobs (or patients) that are processed, each with distinctive routing and processing requirements. In addition, although the volume of each customer order may be small, there are probably a great number of different orders in the shop at any one time. This necessitates planning to produce each job as it arrives, scheduling its use of limited resources, and monitoring its progress through the system.

This chapter concentrates on scheduling issues for job shop production. We also examine one of the most difficult scheduling problems for services— employee scheduling.

---

Objectives in Scheduling

There are many possible objectives in constructing a schedule, including

• Meeting customer due dates;
  
• Minimizing job lateness;
  
• Minimizing response time;
  
• Minimizing completion time;
  
• Minimizing time in the system;
  
• Minimizing overtime;
  
• Maximizing machine or labor utilization;
  
• Minimizing idle time; and
  
• Minimizing work-in-process inventory.

Job Shop Scheduling

Job shop scheduling is also known as production control, shop floor control (SFC), and production activity control (PAC). Regardless of their primary scheduling objective, manufacturers typically have a production control department whose responsibilities consist of three activities:

Loading

Checking the availability of material, machines, and labor. The MRP system plans for material availability. CRP converts the material plan into machine and labor requirements, and projects resource overloads and underloads.

Production control assigns work to individual workers or machines and then attempts to smooth out the load to make the MRP schedule “doable.” Smoothing the load is called load leveling.

Sequencing

Releasing work orders to the shop and issuing dispatch lists for individual machines. MRP recommends when orders should be released (hence the name planned order releases). After verifying their feasibility, production control releases the orders.

When several orders are released to one machine center, they must be prioritized so that the worker will know which ones to do first. The dispatch list contains the sequence in which jobs should be processed. This sequence is often based on certain sequencing rules.

Monitoring

Maintaining progress reports on each job until it is completed. This is important because items may need to be rescheduled as changes occur in the system. In addition to timely data collection, it involves the use of Gantt charts and input/output control charts.

---

What is Loading?

Loading is the process of assigning work to limited resources. Many times, an operation can be performed by various persons, machines, or work centers but with varying efficiencies. If there is enough capacity, each worker should be assigned to the task that he or she performs best and each job to the machine that can process it most efficiently. In effect, that is what happens when CRP generates a load profile for each machine center. The routing file used by CRP lists the machine that can perform the job most efficiently first.

If no overloads appear in the load profile, then production control can proceed to the next task of sequencing the work at each center. However, when resource constraints produce overloads in the load profile, production control must examine the list of jobs initially assigned and decide which jobs to reassign elsewhere. The problem of determining how best to allocate jobs to machines or workers to tasks can be solved with the assignment method of linear programming.

Assignment Method

The assignment method is a specialized linear programming solution procedure for deciding which worker to assign to a task or which job to assign to a machine. Given a table of tasks and resources, the procedure creates an opportunity cost matrix and selects the best assignment in consideration of trade-offs among alternatives. With this technique, only one job may be assigned to each worker or machine.

The procedure for a minimization problem is outlined as follows:

• Perform row reductions by subtracting the minimum value in each row from all other row values.
  
  
• Perform column reductions by subtracting the minimum value in each column from all other column values.
  
  
• The resulting table is an opportunity cost matrix. Cross out all zeros in the matrix using the minimum number of horizontal or vertical lines.
  
  
• If the number of lines equals the number of rows in the matrix, an optimal solution has been reached and assignments can be made where the zeros appear. Otherwise, modify the matrix by subtracting the minimum uncrossed value from all other uncrossed values and adding this same amount to all cells where two lines intersect. All other values in the matrix remain unchanged.
  
  
• Repeat steps 3 and 4 until an optimal solution is reached.

Assignment problems may also involve maximizing profit or customer satisfaction. When solving maximization problems by hand, each entry in the initial matrix should be subtracted from the largest matrix value before proceeding as a minimization problem.

This is potentially ambiguous as it assumes students’ familiarity with Solver. When solving with Excel, simply change the Solver objective function from min to max.

---

Sequencing

When more than one job is assigned to a machine or activity, the operator needs to know the order in which to process the jobs. The process of prioritizing jobs is called sequencing. If no order is specified, the operator would probably process the job that arrived first.

This default sequence is called first-come, first-served (FCFS). If jobs are stacked on arrival to a machine, it might be easier to process the job first that arrived last and is now on top of the stack. This is called last-come, first-served (LCFS) sequencing.

Another common approach is to process the job first that is due the soonest or the job that has the highest customer priority. These are known as earli- est due date (DDATE) and highest customer priority (CUSTPR) sequencing. Operators may also look through a stack of jobs to find one with a similar setup to the job that is currently being processed (SETUP). That would min- imize the downtime of the machine and make the operator’s job easier.

Variations on the DDATE rule include minimum slack (SLACK) and smallest crit- ical ratio (CR). SLACK considers the work remaining to be performed on a job as well as the time remaining (until the due date) to perform that work. Jobs are pro- cessed first that have the least difference (or slack) between the two, as follows:

SLACK = (due date − today’s date) − (processing time)

The critical ratio uses the same information as SLACK, but recalculates the sequence as processing continues and arranges the information in ratio form. Mathematically, the CR is calculated as follows:

CR = time remaining / work remaining = due date – today s date / remaining processing time

If the work remaining is greater than the time remaining, the critical ratio will be less than 1. If the time remaining is greater than the work remaining, the critical ratio will be greater than 1. If the time remaining equals work remaining, the critical ratio exactly equals 1. The critical ratio allows us to make the following statements about our schedule:

If CR > 1, then the job is ahead of schedule.
If CR < 1, then the job is behind schedule.
If CR = 1, then the job is exactly on schedule.

Other sequencing rules examine processing time at a particular operation and order the work either by shortest processing time (SPT) or longest pro- cessing time (LPT). LPT assumes long jobs are important jobs and is analo- gous to the strategy of doing larger tasks first to get them out of the way. SPT focuses instead on shorter jobs and can complete many more jobs earlier than LPT. With either rule, some jobs may be inordinately late because they are always put at the back of a queue. All these “rules” for arranging jobs in a certain order for processing seem reasonable.

Sequencing Jobs Through Two Serial Processes

Since few factories consist of just one process, we might wonder if techniques exist that will produce an optimal sequence for any number of jobs processed through more than one machine or process. Johnson’s rule finds the fastest way to process a series of jobs through a two-step system in which every job follows the same sequence through two processes. Based on a variation of the SPT rule, it requires that the sequence be “mapped out” to determine the completion time or makespan, for the set of jobs. The procedure is as follows:

List the time required to complete each job at each process. Set up a one-dimensional matrix to represent the desired sequence with the number of slots equal to the number of jobs. 2. Select the smallest processing time at either process. If that time occurs at process 1, put the associated job as near to the beginning of the sequence as possible. 3. If the smallest time occurs at process 2, put the associated job as near the end of the sequence as possible. 4. Remove the job from the list. 5. Repeat steps 2–4 until all slots in the matrix have been filled or all jobs have been sequenced.

Guidelines for Selecting a Sequencing Rule

In a real-world job shop, jobs follow different routes through a facility that consists of many different machine centers or departments. A small job shop may have three or four departments; a large job shop may have 50 or more. From several to several hundred jobs may be circulating the shop at any given time. New jobs are released into the shop daily and placed in competition with existing jobs for priority in processing.

Queues form and dissipate as jobs move through the system. A dispatch list that shows the sequence in which jobs are to be processed at a particular machine may be valid at the beginning of a day or week but become outdated as new jobs arrive in the system. Some jobs may have to wait to be assembled with others before continuing to be processed. Delays in completing operations can cause due dates to be revised and schedules changed.

The complexity and dynamic nature of most scheduling environments preclude the use of analytical solution techniques. The most popular form of analysis for these systems is simulation. Academia has especially enjoyed creating and testing sequencing rules in simulations of hypothetical job shops.

One early simulation study alone examined 92 different sequencing rules. Although no optimal solutions have been identified in these simulation studies, they have produced some general guidelines for when certain sequencing rules may be appropriate. Here are a few of their suggestions:

• SPT is most useful when the shop is highly congested SPT tends to minimize mean flow time, mean number of jobs in the system (and thus work-in-process inventory), and percent of jobs tardy. Completing more jobs quickly, theoretically satisfies a greater number of customers than the other rules.
  
  However, with SPT some long jobs may be completed very late, resulting in a small number of very unsatisfied customers. For this reason, when SPT is used in practice, it is usually truncated (or stopped), depending on the amount of time a job has been waiting or the nearness of its due date.
  
  
  For example, many shared computer services process jobs by SPT. Jobs that are submitted are placed in several categories (A, B, or C) based on expected CPU time. The shorter jobs, or A jobs, are processed first, but every couple of hours the system stops processing A jobs and picks the first job from the B stack to run. After the B job is finished, the system returns to the A stack and continues processing. C jobs may be processed only once a day. Other systems that have access to due date information will keep a long job waiting until its SLACK is zero or its due date is within a certain range.
  
  
• Use SLACK for periods of normal activity When capacity is not severely restrained, a SLACK-oriented rule that considers both due date and processing time will produce good results.
  
  
• Use DDATE when only small tardiness values can be tolerated DDATE tends to minimize mean tardiness and maximum tardiness. Although more jobs will be tardy under DDATE than SPT, the degree of tardiness will be much less.
  
  
• Use LPT if subcontracting is anticipated so that larger jobs are completed in-house, and smaller jobs are sent out as their due date draws near.
  
  
• Use FCFS when operating at low-capacity levels FCFS allows the shop to operate essentially without sequencing jobs. When the workload at a facility is light, any sequencing rule will do, and FCFS is certainly the easiest to apply.
  
  
• Do not use SPT to sequence jobs that have to be assembled with other jobs at a later date For assembly jobs, a sequencing rule that gives a common priority to the processing of different components in an assembly, such as assembly DDATE, produces a more effective schedule.

---

Monitoring in Job Shops

In a job shop environment, where jobs follow different paths through the shop, visit many different machine centers, and compete for similar resources, it is not always easy to keep track of the status of a job. When jobs are first released to the shop, it is relatively easy to observe the queue that they join and predict when their initial operations might be completed.

As the job progresses, however, or the shop becomes more congested, it becomes increasingly difficult to follow the job through the system. Competition for resources (resulting in long queues), machine breakdowns, quality problems, and setup requirements are just a few of the things that can delay a job’s progress.

Shop paperwork, sometimes called a work package, travels with a job to specify what work needs to be done at a particular work center and where the item should be routed next. Workers are usually required to sign off on a job, indicating the work they have performed, either manually on the work package or electronically through a PC located on the shop floor. Bar code technology and RFID tags have made this task easier by eliminating much of the tedium and errors of entering information with a computer keyboard.

In its simplest form, the bar code is attached to the work package, which the worker reads with a wand at the beginning and end of his or her work on the job. In other cases, an RFID tag is attached to the pallet or crate that carries the items from the work center to the work center. The tag is read automatically as it enters and leaves the work area. The time a worker spends on each job, the results of quality checks or inspections, and the utilization of resources can also be recorded similarly.

For the information gathered at each work center to be valuable, it must be up-to-date, accurate, and accessible to operations personnel. The monitoring function performed by production control takes this information and transforms it into various reports for workers and managers to use. Progress reports can be generated to show the status of individual jobs, the availability or utilization of certain resources, and the performance of individual workers or work centers.

Exception reports may be generated to highlight deficiencies in certain areas, such as scrap, rework, shortages, anticipated delays, and unfilled orders. Hotlists show which jobs receive the highest priority and must be done immediately. A well-run facility will produce fewer exception reports and more progress reports. In the next two sections, we describe two such progress reports, the Gantt chart and the input/output control chart.

For the information gathered at each work center to be valuable, it must be up-to-date, accurate, and accessible to operations personnel. The monitoring function performed by production control takes this information and transforms it into various reports for workers and managers to use. Progress reports can be generated to show the status of individual jobs, the availability or utilization of certain resources, and the performance of individual workers or work centers.

Exception reports may be generated to highlight deficiencies in certain areas, such as scrap, rework, shortages, anticipated delays, and unfilled orders. Hotlists show which jobs receive the highest priority and must be done immediately. A well-run facility will produce fewer exception reports and more progress reports. In the next two sections, we describe two such progress reports, the Gantt chart and the input/output control chart.

Gantt Charts

Gantt charts, used to plan or map out work activities, can also be used to monitor a job’s progress against the plan. , Gantt charts can display both planned and completed activities against a time scale. In this figure, the dashed line indicating today’s date crosses over the schedules for job 12A, job 23C, and job 32B.

From the chart, we can quickly see that job 12A is exactly on schedule because the bar monitoring its completion exactly meets the line for the current date. Job 23C is ahead of schedule and job 32B is behind schedule. They have been used since the early 1900s and are still popular today. They may be created and maintained digitally or by hand. In some facilities, Gantt charts consist of large scheduling boards (the size of several bulletin boards) with magnetic strips, pegs, or strings of different colors that mark job schedules and job progress for everyone to see.

Input/output Control

Input/output (I/O) control monitors the input to and output from each work center. Before such analysis, it was common to examine only the output from a work center and to compare the actual output with the output planned in the shop schedule.

Using that approach in a job shop environment in which the performance of different work centers is interrelated may result in erroneous conclusions about the source of a problem. Reduced output at one point in the production process may be caused by problems at the current work center, but it may also be caused by problems at previous work centers that feed the current work center.

Thus, to identify more clearly the source of a problem, the input to a work center must be compared with the planned input, and the output must be compared with the planned output. Deviations between planned and actual values are calculated, and their cumulative effects are observed. The resulting backlog or waiting line of work to be completed is monitored to ensure that it stays within a manageable range.

The input rate to a work center can be controlled only for the initial operations of a job. These first work centers are often called gateway work centers because most jobs must pass through them before subsequent operations are performed. Input to later operations, performed at downstream work centers, is difficult to control because it is a function of how well the rest of the shop is operating—that is, where queues are forming and how smoothly jobs are progressing through the system.

The deviation of planned to actual input for downstream work centers can be minimized by controlling the output rates of feeding work centers. It provides the information necessary to regulate the flow of work to and from a network of work centers.

Increasing the capacity of a work center that is processing all the work available to it will not increase output. The source of the problem needs to be identified. Excessive queues, or backlogs, are one indication that bottlenecks exist. To alleviate bottleneck work centers, the problem causing the backlog can be worked on, the capacity of the work center can be adjusted, or input to the work center can be reduced.

---

Advanced Planning and Scheduling Systems

The process for scheduling, loading work into work centers, leveling the load, sequencing the work, and monitoring its progress, is called infinite scheduling. The term infinite is used because the initial loading process assumes infinite capacity. Leveling and sequencing decisions are made after overloads or underloads have been identified. This iterative process is time-consuming and not very efficient.

An alternative approach to scheduling called finite scheduling assumes a fixed maximum capacity and will not load the resource beyond its capacity. Loading and sequencing decisions are made at the same time so that the first jobs loaded onto a work center are of the highest priority.

Any jobs remaining after the capacity of the work center or resource has been reached are of lower priority and are scheduled for later periods. This approach is easier than the infinite scheduling approach, but it will be successful only if the criteria for choosing the work to be performed, as well as capacity limitations, can be expressed accurately and concisely.

Finite scheduling systems use a variety of methods to develop their schedules, including mathematical programming, network analysis, simulation, constraint-based programming, genetic algorithms, neural networks, and expert systems.

Because the scheduling system, not the human scheduler, makes most of the decisions, considerable time is spent incorporating the special characteristics and requirements of the production system into the database and knowledge base of the scheduling software. While some companies will develop their finite scheduling software, most will purchase generic or industry-specific scheduling software as an add-on to their ERP system.

This class of scheduling software, with libraries of algorithms and heuristics from which to choose, has become known as advanced planning and scheduling (APS). SAP’s APS system is called the Advanced Planner and Optimizer (APO), and JDA’s is called Factory Planner. These systems also support collaborative planning and scheduling with trading partners. Both APO and Factory Planner use constraint-based programming and genetic algorithms to develop schedules.

Applies these techniques to sequence a set of jobs so that setup time is minimized. Scheduling problems can be enormous, especially as the number of product options or customers proliferate and linked schedules along a supply chain are considered. Some relief has come from the availability of more powerful computers and the use of artificial intelligence techniques. But the biggest impact has come from altered views of the production system.

By grouping parts products or customers into families and scheduling bottleneck resources first, the scheduling problem is sufficiently reduced so that sophisticated solutions are feasible. In the next section, we present a common precept of today’s scheduling systems, the theory of constraints.

---

Theory of Constraints

In the 1970s, an Israeli physicist named Eliyahu Goldratt responded to a friend’s request for help in scheduling his chicken coop business. Lacking a background in manufacturing or production theory, Dr. Goldratt took a commonsense, intuitive approach to the scheduling problem. He developed a software system that used mathematical programming and simulation to create a schedule that realistically considered the constraints of the manufacturing system. The software produced good schedules quickly and was marketed in the early 1980s in the United States.

After more than 100 firms had successfully used the scheduling system (called OPT), the creator sold the rights to the software and began marketing the theory behind the software instead. He called his approach to scheduling the theory of constraints (TOC). General Motors and other manufacturers call its application synchronous manufacturing.

Decision-making in manufacturing is often difficult because of the size and complexity of the problems faced. Dr. Goldratt’s first insight into the scheduling problem led him to simplify the number of variables considered. He learned early that manufacturing resources typically are not used evenly. Instead of trying to balance the capacity of the manufacturing system, he decided that most systems are inherently unbalanced and that he would try to balance the flow of work through the system instead.

He identified resources as bottleneck or non-bottleneck and observed that the flow through the system is controlled by the bottleneck resource. This resource should always have material to work on, should spend as little time as possible on nonproductive activities (e.g., setups, waiting for work), should be fully staffed, and should be the focus of improvement or automation efforts. Goldratt pointed out that an hour’s worth of production lost at a bottleneck reduces the output of the system by the same amount of time, whereas an hour lost at a non-bottleneck may have no effect on system output.

From this realization, Goldratt was able to simplify the scheduling problem significantly. He concentrated initially on scheduling production at the bottleneck resource and then scheduling the non-bottleneck resources to support the bottleneck activities. Thus, production is synchronized, or “in sync,” with the needs of the bottleneck and the system as a whole.

Drum-Buffer-Rope

To maintain this synchronization, Goldratt introduced the concept of drum buffer-rope (DBR). The drum is the bottleneck, beating to set the pace of production for the rest of the system. The buffer is inventory placed in front of the bottleneck to ensure it is always kept busy. This is necessary because output from the bottleneck determines the output or throughput of the system. The rope is the communication signal that tells the processes upstream from the bottleneck when they should begin production (similar to a kanban).

This idea of scheduling the bottleneck first and supporting its schedule with production at non-bottleneck operations is the basis for virtually all scheduling software on the market today.

Process Versus Transfer Batch Sizes

Goldratt’s second insight into manufacturing concerned the concept of lot sizes or batch sizes. Goldratt saw no reason for fixed lot sizes. He differentiated between the quantity in which items are produced, called the process batch, and the quantity in which the items are transported, called the transfer batch. Ideally, items should be transferred in lot sizes of one. The process batch size for bottlenecks should be large to eliminate the need for setups. The process batch size for non-bottlenecks can be small because time spent in setups for non-bottlenecks does not affect the rest of the system.

The TOC scheduling procedure follows these steps:

• Identify the bottleneck.
  
  
• Schedule the job first whose lead time to the bottleneck is less than or equal to the bottleneck processing time.
  
  
• Forward schedule the bottleneck machine.
  
  
• Backward schedule the other machines to sustain the bottleneck schedule.
  
  
• Transfer in batch sizes smaller than the process batch size.

---

Employee Scheduling

Labor is one of the most flexible resources. Workers can be hired and fired more easily than equipment can be purchased or sold. Labor-limited systems can expand capacity through overtime, expanded workweeks, extra shifts, or part-time workers. This flexibility is valuable, but it tends to make scheduling difficult.

Service firms especially spend an inordinate amount of time developing employee schedules. A supervisor might spend an entire week making up the next month’s employee schedule. The task becomes even more daunting for facilities that operate on a 24-hour basis with multiple shifts.

The assignment method of linear programming discussed earlier in this chapter can be used to assign workers with different performance ratings to available jobs. Large-scale linear programming is currently used by McDonald’s to schedule its large part-time workforce. American Airlines uses a combination of integer linear programming and expert systems for scheduling ticket agents to coincide with peak and slack demand periods and for the complicated scheduling of flight crews.

Although mathematical programming certainly has found application in employee scheduling, most scheduling problems are solved by heuristics (i.e., rules of thumb) that develop a repeating pattern of work assignments. Often heuristics are imbedded in a decision support system to facilitate their use and increase their flexibility. One such heuristic used for scheduling full-time workers with two days off per week is given next.

Employee Scheduling Heuristic:

• Let
  • N = no. of workers available
  • Di = demand for workers on day i
  • X = day working
  • O = day off
    
    
• Assign the first N – D1 workers on day 1 off. Assign the next N – D2 workers on day 2 off. Continue similarly until all days have been scheduled.
  
  
• If the number of workdays for a full-time employee is fewer than five, assign the remaining workdays so that consecutive days off are possible or where unmet demand is highest. 4. Assign any remaining work to part-time employees, subject to maximum hour restrictions.
  
  
• If consecutive days off are desired, consider switching schedules among days with the same demand requirements.

Automated Scheduling Systems

Scheduling large numbers of workers at numerous locations requires a computerized scheduling system. Sophisticated employee scheduling software is available as a stand-alone system or as part of an ERP package. For example, Infor’s Workforce Labor Scheduler system provides:

• Staff scheduling assigns qualified workers to standardized shift patterns, considering leave requests and scheduling conflicts. The solutions consider legal and social constraints such as labor laws for minors, overtime payment regulations, and legal or religious holidays that may differ by global location.
  
  
• Schedule bidding puts certain shift positions or schedule assignments up for bid and allows workers to post and trade schedules with others if coverage and skill criteria are met.
  
  
• Schedule optimization creates demand-driven forecasts of labor requirements and assigns workers to variable schedules (in some cases, as small as 15-minute blocks of time) that change dynamically with demand. The optimization is based on mathematical programming and artificial intelligence techniques.