Scheduling Methods

The scheduling approach and methods that are suitable for a production environment depends, as described earlier in this chapter, on the characteristics of the environment, the complexity, uncertainties and randomness of the production system, the scheduling objectives and the organization around the scheduling function. Scheduling methods can range from simple rules for choosing which job to execute next, often called dispatching rules, to sophisticated optimizing methods.

The more randomness there is in a system, the less advisable it is to employ very sophisticated optimization techniques. Equivalently, the more randomness the system is subject to, the simpler the scheduling rules should be.

If advanced scheduling methods should be applied in an environment the uncertainties must as much as possible be reduced and the remaining uncertain factors must be handled in some way. The production environment must also be possible to represent as a model that can be used by a software system. This model must describe the properties of the environment in enough detail to make the developed schedules feasible to execute on the shop floor. The information in the model must also be updated to reflect the actual conditions in the production environment. To keep the model updated can require a lot of effort and this must also be considered when selecting which scheduling method is appropriate for an environment.

Another aspect is how long into the future the schedule spans, which is called the scheduling horizon. This is a continuation of the planning process, it may not be useful to schedule the production in detail more than a limited time into the future, after that a more aggregated level is sufficient. What the scheduling horizon should be must be determined for the particular production environment in question.

The reason for using more advanced methods than just dispatching rules is to improve the performance of a production environment and to better satisfy the scheduling objectives. When using dispatching rules, the information used for choosing which job to execute is mostly local to the work center and this can result in sub-optimizations that do not contribute to the satisfaction of the scheduling objectives. More advanced methods tries to consider the global state of the production system to determine what actions should be taken to best satisfy these objectives. This bigger picture of course requires more information handling and when done manually relies primarily on the mind of the person doing the scheduling and the use of tools such as planning boards. It is here that a software system can be put to use to  handle the information processing. To do this the information has to be formalized in some way into a model as described above. When using a software system for scheduling, the methods used can be much more complex than what is possible with a manual system.

Deterministic and stochastic scheduling methods

The scheduling methods can be grouped into the general categories deterministic or stochastic. In deterministic methods all variables of the model describing the problem are assumed to be known in advance and no uncertainty exits. Stochastic models have some, or all, variables defined as random and the methods use probability distribution when developing schedules. Stochastic scheduling methods used in practice usually involve some kind of dispatching rule.

Since a production system without any uncertainty does not exist, ways of handling uncertainty in deterministic models have been developed. Deterministic methods with some kind of support to handle uncertainty seem to be the most frequent in literature.

Dispatching rules

The most basic scheduling method is to use dispatching rules (also called priority sequencing rules) to determine which order to run next at a work center. These rules are applied when jobs arrive at a work center to choose the next task to be executed. Since dispatching rules only use information that is available at the moment when the next activity shall be selected, they work equally well in systems with a high degree of uncertainty as in more stable environments. When there are high levels of randomness and uncertainty in the production environment, dispatching rules may be the only viable way to schedule the production. There exist many dispatching rules, some of the most common are

• First come, first served (FCFS). Jobs are process in the order they arrive at the work center.
• Shortest processing time (SPT). The job with the shortest processing time is processed first.
• Earliest due date (EDD). The job with the earliest due date is processed first.
• Critical ratio (CR). A priority index is calculated using (time remaining / work remaining). A ratio less than 1 means that the job is late. The job with the lowest ratio is processed first.
• Least work remaining (LWR). Priority based on all processing time remaining until job is completed.
• Fewest operations remaining (FOR). Priority based on number of remaining operations.
• Slack time (ST). Jobs run in the order of the smallest amount of slack.
• Slack time per operation (ST/O). Slack time is divided by the number of remaining operations. Jobs are sequenced in order of smallest value.
• Next queue (NQ). The queues in front of successive work centers are measured (in hours or number of jobs). The job that is going to the smallest queue is processed first.
• Least setup (LS). The job with the least setup time is processed first.

The general properties of these rules are different. SPT, and its variations LWR and FOR, reduces work in process inventory, average job completion time and average job lateness but can cause starvation of jobs with long processing times and thus cause missed due date. EDD, and its variations ST and ST/O, reduce job lateness but result in higher average time in the system. NQ and LSU maximize machine utilization. There exist many other dispatching rules and also variations of the above rules. To combine rules, for instance using different rules for different work centers is also possible.

Scheduling using these rules can, depending on the scheduling problem, give good results but there is a risk of sub-optimization since the information used is local and no consideration is given to the global state of the production system.

Advanced scheduling methods

Advanced scheduling methods use more information when developing schedules than dispatching rules and try to consider more or less of the global state of the production system. In industry these methods are categorized as Advanced Planning and Scheduling (APS) methods. The APS category includes methods for scheduling as well as demand management, production planning, distribution planning and transportation planning.

Advanced scheduling methods require that the production system is represented as a model that can be used as a good enough approximation of reality to make the developed schedules executable on the shop floor. The model must describe all the relevant constraints in the production system and include information such as:

• Orders, operations and precedence relations between these
• Resources required to perform the operations and their available capacity
• Materials required to perform the operations and the availability of these
• Release and due dates of orders
• Priorities among orders
• Real and expected costs incurred by the different activities and decisions

What is a good enough approximation must be determined from case to case, but there should always be a correspondence between how well the model describes reality and how advanced the used scheduling method is. The general rule, the more uncertainty the simpler scheduling method, applies here. If the developed schedule is not feasible to execute on the shop floor because of missing or faulty information in the model, applying advanced optimizing methods is a waste of time and resources. Effort should in those cases instead be put into developing and refining the model in combination with measures to remove uncertainties from the production system.

Finite capacity scheduling

In industry, applying advanced scheduling methods is often called finite capacity scheduling (FCS). Traditional methods such as MRP consider the capacity of production resources more or less as infinite. When the constraints imposed by the capacity actually available in the production resources are considered by the scheduling method this is termed FCS. Scheduling with and without consideration of capacity constraints is illustrated in figures below

In FCS jobs are only scheduled on a resource up to the resource’s capacity limit. This means that jobs that cannot be performed at the required time are going to be moved forward, possibly making jobs late. FCS makes it possible to find those resources where available capacity is not enough to perform the required work load. Such resources are called bottleneck resources and finding these problem spots is very important when making schedules. Just that a schedule is considering the constraint imposed by the finite capacity of the production environment says nothing of how well it satisfies the goals of the company. What can be said is however that the more advanced methods all must be developed against finite capacity to be feasible and possible to execute on the shop floor. A basic example of FCS can be a method that applies dispatching rules to all orders planned to be executed over some time period in a production environment while at the same time considering the constraints imposed by available capacity.

Advanced scheduling methods can be characterized by the way they decompose the problem. Decomposition approaches to scheduling problems can be grouped into the three categories job-based, resource-based and event-based. These approaches can also be combined in different ways to suit different production environments.

Job- based methods

In job based methods scheduling is performed at the job, or order, level. In this is referred to as horizontal loading. All jobs that are to be scheduled are given a priority. The priorities can be based on different factors such as due dates or other information determining the importance of jobs. The schedule is then developed by scheduling the jobs one at time in priority order, from highest priority to lowest. All operations that belong to a job are scheduled at the same time and required resource capacity and materials are allocated for these operations ahead of time. Job-based methods result in schedules that get jobs finished in priority order. Maintaining a high level of resource utilization is not considered. An effect can be that a work center is idle waiting for a high priority job to arrive while other, lower priority, jobs are ready to execute.

Resource-based methods

Resource-based methods decompose the problem by the utilization level of resources and places focus on bottlenecks in the production system. The methods are therefore often referred to as bottleneck methods. The bottleneck method that first got attention was developed by Eli Goldratt who has termed it the theory of constraint (TOC). The basic idea of TOC is that the constraints of a system determine its overall performance. A constraint according to Goldratt is “anything that limits the performance of a system relative to its goals” and the method actually can be applied to more than just scheduling. In the scheduling part of the theory, the method is to schedule the bottleneck resources very rigorously and use simple methods to schedule all other, non-bottleneck, resources. The bottleneck resource determines the throughput of the whole system and therefore its utilization should be maximized. A buffer is put before the bottleneck resource to ensure that it never has to wait for jobs to execute. The concept is called drum-buffer-rope where the bottleneck resource is the drum that determines the pace, the rope is the signaling mechanism that links the other resources to the bottleneck and the buffer insulates the bottleneck from the rest of the system. The method’s purpose is to maximize the throughput of the system. By focusing on the bottleneck resource and letting the other resources follow, more effort can be put into scheduling just the problem resource.

TOC requires that there exist just a few bottleneck resources and that they be well defined. In reality this is often not the case, it is common that the bottleneck resource shifts over time.

Event-based methods

Event-based methods decompose the problem at the operation level. These methods determine which task to be executed in a resource at the operation level. Instead of scheduling all operations included in a job at the same time as in job-based methods, the operations are scheduled separately. The precedence relations between operations in a job must of course be maintained while doing this. This type of scheduling is referred to as vertical loading.

In event-based methods time is considered to be moving forward event by event. The events considered are occurrences that change the state of the system and require some action to be taken. Such events are for example, operations becoming available for execution at a work center, operations being finished at a work center (making resource capacity available) and material becoming available for use by an operation. At each event the current state of the system is considered and actions are taken, such as starting a new operation in a work center. By decomposing the problem at the operation level, potentially more possibilities are available to apply rules that prioritize operations according to different weighted objectives. An example of such a rule can be to schedule the operations in job priority order but if there is available capacity at a work center and current demand exists for that capacity by operations that are not in priority order, then execute those operations even if this makes higher prioritized operations late.

It is knowledge based and decision support systems. Another approach that deserves mention uses knowledge based or decision support systems to perform scheduling. Knowledge-based systems model the production environment and use knowledge elicited from existing scheduling experience to find feasible schedules. These types of system are also called expert systems. The elicited knowledge is formalized as rules that are applied to the model.