In this article we discuss methods of scheduling tasks or operations on available resources so as to achieve some specified objectives. An example of a scheduling problem is to determine the order in which jobs in a manufacturing plant will be completed so that the number of on time deliveries is maximized. Other examples of scheduling include the running of programs at a computing centre, the processing of loan applications by a bank, the landing of aircraft at an airstrip, and performing medical tests on a patient. An arbitrary procedure such as “first come first served” or scheduling by default may lead to solutions that are far from optimal.
While scheduling problems occur in varying degrees in all types of systems, they are particularly salient in job shops. A job shop is a process focused production system that employs general purpose processors. Production is to order, and a large number of different products are produced, each in relatively small volume. Examples of job shops include machining shops, multispecialty clinics, computer centres, and consulting firms.
A production manager of a job shop will use the results of scheduling in several aspects of decision making. At the broadcast level is capacity planning, in which the need for additional capacity and the type of capacity needed are identified. A simulation analysis of forecasted order patterns could reveal bottlenecks and the requirements for additional capacity. In some cases, efficient scheduling can improve the utilization of existing processors (machines) so that expensive additions to capacity can be postponed.
The next level at which the results of scheduling are useful is in decisions concerning order acceptance, due date specifications, and product mix considerations. For example, scheduling may reveal that, given the nature of the processors in a job shop, accepting a mix of smaller volume and larger volume orders and quoting similar due dates for both types of orders create bottlenecks and late deliveries. Management may then wish either to focus on one type of order or to quote differential due dates to avoid bottlenecks and late deliveries.
Further down in the level of detail is shop loading, where the manager must decide on a daily basis how many jobs and which jobs to release to the shop for processing. The criteria of machine utilization and customer service will be important.
Finally, the manager must develop procedures for deciding the order in which the operations of different jobs should be performed on a processor if several operations are competing for the same processor. Simple, procedures such as “first come first served” or random selection will often produce unacceptable solutions, resulting in delayed deliveries, the unbalanced utilization of processors, and the like. A clear understanding of the nature of scheduling problems at this most detailed level and of the procedures of scheduling will provide inputs to the higher level decisions discussed earlier. To illustrate the differences among alternative scheduling procedures and the impact of a choice of a scheduling procedure on a desired performance measure, we will examine single processor scheduling in some detail.
Consider, a hypothetical automated chemical plant that produces several different products, but only one product can be produced at a time. Suppose that the production manager of the plant has to decide on the scheduling of four products, the production times and due dates for which are shown. For example, that product 4 will require 8 days in manufacturing and that it is due to be delivered in 17 days. The production manager has several alternatives for scheduling the production of these products. For example, he could produce product 1 first and then product 2, followed by product 3 and finally product 4. Alternatively, he could produce 4 first product 2 next, then product 2 next, then product 1 and finally product 3. In fact, there are 4x3x2x1 = 24 distinct ways of scheduling the production of these four products. The decision facing the production manager is which one of these possible 24 schedules should be chosen?
This simplified example illustrates the problem of scheduling on a single processor. Single processor or single machine scheduling is of interest for the following reasons:
There are many situations where an entire plant can be viewed as a single processor, as is the case in chemical manufacturing, paint manufacturing and the manufacturing of products in automated plants.
In a plant that employs multiple processors, there is often a bottleneck processor that controls the output of the plant because of its limited capacity. The analysis of this bottleneck processor may determine the decisions for the entire plant.
The analysis of a single processor illustrates many important problems that arise in more complex scheduling situations therefore it serves as a building block for understanding the decision problems in these complex situations.