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 numbers of timely deliveries are the highest. Other examples of scheduling include the running of programs at a computing center, 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 with respect to a companyâ€™s objectives. We hope to demonstrate that, by using scientific procedures for scheduling, a company can achieve significantly better performance on stated objectives.
Types and characteristics of alternative production systems were described. While scheduling problems occur to 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, multi-specialty clinics, computer centers, and consulting firms.
A production manager of a job shop will use the result of scheduling in several aspects of decision making. At the broadest 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 specification, 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 creates 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 in shop loading, where the manager must decide on a daily basis how many jobs and which job 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 of several operations is 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. We will therefore focus on the job shop scheduling problem at this level of detail. To illustrate the differences among alternative scheduling procedures and the impact of a choice of a scheduling procedure on a desired performance, measure, here we are examining 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 mangers of the plant has to decide on the scheduling of four products, the production times and due dates in the tables, For example, that a 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 product 4 first, product 2 next then product 1, and finally product 3. In fact, there are 4 x 3 x 2 x 1 = 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:
1. 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.
2. In plants that employ multiple processors, there is often a bottlenecks 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.
3. 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 more complex situations.