18 Scheduling: Importance and Methods in Manufacturing
Vikas Singla
18.1 OBJECTIVES
This chapter would help students to understand:
- Importance of scheduling jobs in manufacturing operations
- Different cases of scheduling
- Priority criteria of scheduling
- Scheduling various jobs on single machine
- Scheduling various jobs on two machines
- Scheduling various jobs on more than two machines
18.2 INTRODUCTION
Scheduling refers to assigning sequence of jobs to various machines involved in manufacturing process. For instance, one part of dressing of a doll is to wear pants, wear socks and wearing of shoes. Three machines each doing one kind of job namely, machine 1 is used for wearing of pants, machine 2 for wearing socks and machine 3 does wearing of shoes. Also, there are three dolls A, B and C to be dressed. Figure 18.1.1 shows the process when all three dolls are same and they undergo same process of dressing up. A decision has to be made about the sequence in which dolls should enter the system. In this case as all dolls are same and adopt same procedure so sequencing might not be that difficult. But sequencing becomes difficult if products require different operations.
Figure 18.1.2 shows such a scenario when three dolls require different processes to get dressed. In this case A and B adopts a sequence of pants—-socks—-shoes whereas C adopts socks—-pants—-shoes (as shown by line curve). Now first question is out of A and B which doll should enter the process first. Suppose A enters the process first and takes 30 seconds for wearing pants followed by B whereas at same time C is assigned to machine 2 for wearing socks which takes 20 seconds. Now after 20 seconds doll C gets free and waits for machine 1. Should machine 1 be accessed by doll C after A gets processed on it or should it wait for processing of both A and B? If it waits only for completion of A then waiting time is 10 seconds whereas if it waits for both A and B then waiting time increases to 50 seconds.
Imagine the scenario when number of dolls to be dressed increases. Thus scheduling or sequence of assigning of jobs becomes important and it predominantly depends on:
- Sequence of processing. In doll example, sequence can be pants—-socks—-shoes or socks—-pants—- shoes. Sequencing problem increases if variety of jobs asks for different operations. Variety of jobs increases in batch production system. In mass production system as in car wash example where each car goes through same process of washing, rinsing and drying variety of operations is minimal. Thus, assigning of jobs is much easier in mass production system as compared to batch system.
- Number of jobs to be processed: A batch system of production is characterized by variety of jobs each being produced at low volume. Each job would be different in terms of sequence of operation and processing time taken at each machine. Cake manufacturing is an example of batch system of production. A chocolate cake is different from a vanilla cake in terms of raw material and sequence of operations used on same machines. Processing time of each operation of each type of cake would be different. Also variety of operations impacts set up time. Machines have to be prepared for different operations for different cakes increasing waiting time and decreasing productivity. Thus, variety of jobs using same machines but in different sequence increases scheduling problem.
- Number of machines used in processing: If operating system has only one machine in the system and all jobs need to be processed on that machine then scheduling requires assigning of jobs to that single machine. But generally one machine cannot carry out all operations. So, a job might use multiple machines before getting completed. A manager has to deduce whether operations can be clubbed together and performed on a single machine or is operations are so different that they would be processed on different machines. Multiple jobs being processed on a set of similar multiple machines is another variant of scheduling being discussed.
Taking into consideration above discussed decision points regarding multiplicity of jobs, machines and their sequence of operations scheduling can be categorized as workforce and operation scheduling. Determining which employee work when is called as workforce scheduling. Should a worker be assigned night shift or day shift? Which employee should be asked to work on which airline route? Such questions are answered in workforce scheduling. Other type of scheduling studies assignment of jobs to machines or workers to jobs. Such scheduling is called as operations scheduling. This chapter discusses various quantitative methods of assigning jobs to machines.
18.3 SCHEDULING PROBLEMS
Following are different types of sequencing cases have been discussed in this chapter:
- Scheduling of n jobs on single machine
- Scheduling of n jobs on two machines
- Scheduling of n jobs on more than 2 machines
- Scheduling of 2 jobs on n machines (discussed in module 19)
18.2.1 eduling of n jobs on single machine
The operations using general purpose machines generally use single machine for operating different jobs. For instance, a drilling machine might be used to drill different size of holes in different wooden cardboards. Then if there are five different holes to be drilled in five different cardboards then it has to be decided out of these five jobs which cardboard would be processed first and then in what sequence others would follow. Such cases can be resolved by using either of following two priority criteria:
- Earliest Due Date rule (EDD): In this method job which has to be dispatched or supplied to the customer at the earliest is processed first. Other jobs are also arranged according to this criterion.
- Shortest Processing Time rule (SPT): In this method job with shortest processing time enters the operating system first and then other jobs follow according to processing time criteria.
These priority rules have been explained by following example.
Example 18.2.1.1: Table 18.2.1.1 shows processing time and scheduled supply time to the customer of five cardboards requiring different drilling operation on same drilling machine. Sequence the jobs based on (i) EDD rule and (ii) SPT rule. Table 18.2.1.1
| Processing time (hrs.) | Scheduled supply time (hrs.) | |
| Cardboard 1 | 8 | 10 |
| Cardboard 2 | 6 | 12 |
| Cardboard 3 | 15 | 20 |
| Cardboard 4 | 3 | 18 |
| Cardboard 5 | 12 | 22 |
EDD rule: The sequence of jobs processing depend on time required to supply to the customer. Cardboard 1 is to deliver at the earliest so it would be processed first followed by cardboard 2 and so on. The complete sequence of operations would be:
Cardboard: 1, 2, 4, 3, 5
Table 18.2.2 by using identified sequence calculates the waiting time for each job.
| Table 18.2.1.2 | |||||
| Cardboard | Start time | Processing time | End time | Supply time | Waiting time |
| 1. | 0 | 8 | 8 | 10 | 8-10= -2 |
| 2. | 8 | 6 | 14 | 12 | 14-12= 2 |
| 4. | 14 | 3 | 17 | 18 | 17-18= -1 |
| 3. | 17 | 15 | 32 | 20 | 32-20= 12 |
| 5. | 32 | 12 | 44 | 22 | 44-22= 22 |
Cardboard 1 enters processing system at the earliest so its starting operation time is considered as base time. Thus, it started its operation at 0 hours. It takes 8 hours to get processed on single machine and then gets out of processing system. So machine becomes free to process cardboard 2 after 8 hours. It takes 6 more hours for processing. Cardboard 2 gets out of processing system after 8 hours (waiting time) + 6 hours (processing time) i.e. 14 hours. Similarly for other jobs start and end time is calculated. Now, supply time of cardboard 1 was after 10 hours but it got processed after 8 hours so the job is supplied to customer 2 hours early. Thus, negative sign indicates job being processed before supply date. In this example job 1 and 4 are supplied before due date.
SPT rule: The sequence of jobs depends on processing time taken by each job. Job which takes least time on machine would enter system first and then others would follow. By using this criteria sequence of jobs is:
Cardboard: 4, 2, 1, 5, 3
Table 18.2.3 calculates time a job has to wait before getting processed.
| Table 18.2.1.3 | |||||
| Cardboard | Start time | Processing time | End time | Supply time | Waiting time |
| 4. | 0 | 3 | 3 | 18 | 3-18 = -15 |
| 2. | 3 | 6 | 9 | 12 | 9-12 = -3 |
| 1. | 9 | 8 | 17 | 10 | 17-10 = 7 |
| 5. | 17 | 12 | 29 | 22 | 29-22 = 7 |
| 3. | 29 | 15 | 44 | 20 | 44-20 = 22 |
By using SPT rule cardboard 4 enters the system first and takes 3 hours for processing. It has to be delivered after 18 hours but is delivered only after 3 hours. Similarly waiting time for other jobs is also calculated.
Important points:
- By using same total time to process five jobs i.e. makespan is same of 44 hours.
- Which method is better?
| Average job flow time in case of EDD | = (8 + 14 +17 + 32 + 44)/5 = | 23 hours |
| Average job flow time in case of SPT | = (3 + 9 + 17 + 29 + 44)/5 = | 20.4 hours |
As average flow time for processing five jobs by using SPT rule is lesser than EDD rule so sequencing should be done by using SPT rule.
18.2.2 Scheduling of n jobs on two machines
In this case several jobs are arranged in a sequence to be operated on two machines. It is assumed that all jobs are operated on two machines. Machines are arranged in a sequence. For instance, suppose there are two machines A and B. according to technological sequence machine B is placed after machine A. A particular job then enters the processing system by going first through machine A and exits after getting processed at machine B Fig. 18.2.2.1).
The sequencing of several jobs on two machines is solved by using Johnson’s Rule which is based on Shortest Processing Time rule by following given steps:
Step 1: List the processing time of each job on each machine. Select the lowest processing time.
Step 2: If selected lowest processing time is for the first machine then that job is processed first. But if shortest processing time of a particular job is for second machine then that job is processed last. In case of a tie job is processed first.
Step 3: Repeat above steps and schedule all the jobs.
Example 18.2.2.1: For the following data given in table 18.2.2.1 sequence the operations and calculate their waiting times.
Table 18.2.2.1
| Jobs | Processing time on Machine 1 | Processing time on Machine 2 |
| A | 3 | 2 |
| B | 6 | 8 |
| C | 5 | 6 |
| D | 7 | 4 |
Step 1: Select the shortest processing time. From the table it can be seen that SPT is 2 minutes.
Step 2: Selected SPT is for job A so it would be processed last.
Step 3: Repeat the process. After scheduling A out of remaining jobs SPT is for job D which is 4 minutes. This would be processed again last but before A. Job C has SPT of remaining jobs. As it is for machine 1 so it would be processed first. B would occupy the only remaining second position. So, final sequencing order would be:
C, B, D, A
Calculation of waiting time for each job:
| Machine 1 | Machine 2 | Waiting time | ||||||
| Jobs | Start time | Processing
time |
End time | Start time | Processing
time |
End time | Machine 1 | Machine 2 |
| C | 0 | 5 | 5 | 5 | 6 | 11 | 0 | 5 |
| B | 5 | 6 | 11 | 11 | 8 | 19 | 5-5 = 0 | 11-11 = 0 |
| D | 11 | 7 | 18 | 19 | 4 | 23 | 11-11 = 0 | 19-19 = 0 |
| A | 18 | 3 | 21 | 23 | 2 | 25 | 18-18 = 0 | 23-23 = 0 |
- Job C enters the operation system and gets processed at Machine 1 for 5 minutes. For same time period machine 2 remains idle waiting for job C. When job C gets finished after 5 minutes next job i.e. job B enters the system. So machine 2 does not have to sit idle or wait for next job. Machine 2 gets free after processing job C after 11 minutes. But at same time job B gets processed from machine 1 and is ready for processing at machine 2.
- Total flow time or time taken to process four jobs on two machines = 25 minutes
- Machine 1 gets free from processing four jobs after 21 minutes but job is still in the system and is getting processed at machine 2. So, Total waiting time for machine 1 = 25-21 = 4 minutes
- Total waiting time for machine 2 = 5 minutes
18.2.3 Scheduling of n jobs on more than 2 machines
A special case of Johnson’s rule is applied when there are several jobs that need to be processed on more than 2 machines arranged sequentially. For instance, in car washing example three machines are arranged according to technological sequence where each machine is dedicated to perform one particular operation shown in Fig.18.2.3.1). In such a process all the cars have to go through all machines for processing.
Example 18.2.3.1: Following table shows processing time in minutes of four jobs to be processed on four machines
A, B, C and D. All these machines are arranged in sequence of A—-B—-C—-D. Also, a job has to adopt this sequence to get processed fully. Find the sequence of jobs and idle time for each machine.
Table 18.2.3.1
| Machines | ||||
| Jobs | A | B | C | D |
| 1. | 58 | 14 | 14 | 48 |
| 2. | 30 | 10 | 18 | 32 |
| 3. | 28 | 12 | 16 | 44 |
| 4. | 64 | 16 | 12 | 42 |
Step 1: Find minimum processing time on first machine (machine A) and last machine (machine D). In this case minimum time on machine A is 28 minutes and on machine D is 32 minutes.
Step 2: Find maximum processing time of remaining machines. In this case maximum processing time on machine B is 16 minutes and on machine C is 18 minutes.
Step 3: If minimum time on first machine i.e. A and on last machine i.e. D is greater than maximum time of remaining machines i.e. B and C then machines can be clubbed together.
In this case Minimum A = 28 is greater than maximum B and C i.e. 16 and 18 minutes.
Minimum D = 32 is greater than maximum B and C i.e. 16 and 18 minutes.
Step 4: Now, the problem can be converted into a 2 machine and 4 job problem by. The processing times of B and C are added to that of A to create an imaginary machine P. Also processing times of B and C are added to D to create an imaginary second machine Q.
Step 5: Scheduling of n jobs and 2 machines now can be solved by using Johnson’s Rule.
Table 18.2.3.2
| Machines | ||
| Jobs | P (processing time) | Q (processing time) |
| 1. | 58+14+14 = 86 | 48+14+14 = 76 |
| 2. | 58 | 60 |
| 3. | 56 | 72 |
| 4. | 92 | 70 |
Sequence of jobs to be processed on Machine P and Q based on SPT would be 3, 2, 1, 4
Calculation of waiting times for all machines is shown in Table 18.2.3.3
- Total idle time for machine A = 250-180 = 70
- Total idle time for machine B = 28 + 18 + 48 + 50 + (250-196) = 198
- Total idle time for machine C = 40 + 12 + 44 + 52 + (250-208) = 190
- Total idle time for machine D = 56 + 0 + 12 + 16 = 84
- Total flow time or time taken to complete processing of given number of jobs (makespan) = 250 minutes
18.3 SUMMARY
Scheduling of jobs becomes immensely important aspect in operations management if a firm is involved in manufacturing variety of jobs using multiple machines. Batch shop production system which is characterized by general purpose machines used to manufacture high variety of jobs at low volumes asks for assigning sequence of each job on different machines. The solution of scheduling problem carries importance as it directly impacts waiting or idle time of machines. Machines sitting idle for longer period of times have detrimental effect on efficiency of operations. Three scenarios of scheduling have been discussed in this chapter: processing of variety of jobs on single machine, processing of variety of jobs on two machines and processing of variety of jobs on more than two machines. Scheduling of jobs in each case is done on certain priority criteria. Two criteria namely Shortest Processing time and Earliest Due Date have been discussed. Predominantly a criterion of Shortest Processing Time is used in sequencing of jobs. Illustrations of all the cases discussed have been done on the criteria of SPT.
18.4 GLOSSARY
- Scheduling: is the process of assigning jobs in a particular sequence.
- Earliest Due Date: is a priority criteria used based on which a job which has to be supplied first to the customer is processed at the earliest.
- Shortest Processing Time: is a priority criteria used based on which a job which requires lowest time to process is processed at the earliest.
- Johnson’s Rule: based on SPT is used to sequence variety of jobs to be processed on two machines.
18.5 REFERENCES/ SUGGESTED READINGS
- Chase, B.R., Shankar, R., Jacobs, F.R. and Aquilano, N.J., Operations & Supply Chain Management, 12th Edition, McGraw Hill.
- Stevenson, W.J., Operations Management, 9th Edition, Tata McGraw Hill.
- Lee J. Krajewski, Operations Management, Prentice-Hall of India, New Delhi, 8th Edition.
18.6 SHORT ANSWER QUESTIONS
1. EDD criteria selects a job for processing based on its smallest processing time
(a) True (b) False
Answer: False
2. In SPT criteria jobs are sequenced based on their processing times.
(a) True (b) False
Answer: True
3. Johnson’s Rule is used to sequence jobs to be processed on machines arranged in
(a) sequence (b) parallel
Answer: a
18.7 MODEL QUESTIONS
1. Five teachers teaching five different subjects need to be scheduled to teach a first year management class. Which priority criteria should be used in formulating such a time table?
2. The following table gives processing time and due date of supply of five jobs. Sequence them based on SPT and EDD.
| Jobs | 1. | 2. | 3. | 4. | 5. |
| Processing time (days) | 6 | 7 | 4 | 9 | 5 |
| Due Date (days) | 5 | 3 | 4 | 7 | 2 |
3. Seven jobs must be processed in two operations A and B. All jobs goes through the operation in an order of first A and then B. Sequence the jobs processing time of which on each machine is given in the following table.
| Jobs | 1. | 2. | 3. | 4. | 5. | 6. | 7. |
| Processing time on A | 9 | 8 | 7 | 6 | 1 | 2 | 4 |
| Processing time on B | 6 | 5 | 7 | 3 | 2 | 6 | 7 |
4. Sequence the following three jobs to be processed on three machines in the sequence of Machine A, Machine B and then machine C.
| Jobs | 1. | 2. | 3. |
| Processing time on A | 11 | 8 | 9 |
| Processing time on B | 14 | 10 | 12 |
| Processing time on C | 6 | 11 | 7 |