15.3 Scheduling Challenges in Manufacturing
The following are different types of sequencing cases that have been discussed in this chapter:
- Scheduling of n jobs on a single machine
- Scheduling of n jobs on two machines
- Scheduling of n jobs on more than 2 machines
Scheduling of n Jobs on a Single Machine
In many manufacturing environments, general-purpose machines are used to perform different operations on various jobs. For example, a single drilling machine may be used to drill different hole sizes in multiple wooden boards. When multiple jobs are queued for the same machine, it becomes essential to determine the optimal processing sequence to improve efficiency and meet delivery deadlines.
Let’s say there are five drilling jobs to be completed. The question becomes: Which job should be processed first, and in what order should the others follow?
Scheduling can be based on several criteria, such as: First Come, First Served (FCFS), Shortest Processing Time (SPT) and Earliest Due Date (EDD).
In this section, we focus on two widely used priority rules:
1. Earliest Due Date (EDD) Rule
Jobs are scheduled in the order of their due dates. The job with the earliest delivery requirement is processed first, followed by the next earliest, and so on.
2. Shortest Processing Time (SPT) Rule
Jobs are scheduled based on their processing time. The job that takes the least time is processed first, followed by the next shortest, and so on.
Manufacturing Firm Example
A manufacturing firm has five drilling jobs, each with a specific processing time and due date. All jobs are to be completed on the same drilling machine.
| 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 |
Example: Using EDD Rule
Jobs are sequenced based on their due dates. Suppose the order is: Cardboards: 1, 2, 4, 3, 5
We calculate the waiting time and completion time for each job. For example:
- Cardboard 1 starts at 0 minutes and takes 8 minutes → completes at 8 minutes.
- Cardboard 2 starts at 8 minutes, takes 6 minutes → completes at 14 minutes.
- And so on…
| 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 |
If a job is completed before its due date, the difference is shown as a negative value, indicating early delivery.
Example: Using SPT Rule
Jobs are sequenced based on processing time. Suppose the order is: Cardboards: 4, 2, 1, 5, 3
- Cardboard 4 starts at 0 minutes, takes 3 minutes → completes at 3 minutes.
- Cardboard 2 starts at 3 minutes, takes 6 minutes → completes at 9 minutes.
- And so on…
| 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 – 22 = 22 |
Comparison of Methods
- Total processing time (makespan) remains the same: 44 minutes
- Average job flow time:
- EDD = (8 + 14 + 17 + 32 + 44) / 5 = 23.0 minutes
- SPT = (3 + 9 + 17 + 29 + 44) / 5 = 20.4 minutes
Since the SPT rule results in a lower average flow time, it is the preferred method in this case.
Scheduling of n Jobs on Two Machines
In this scheduling scenario, multiple jobs must be processed sequentially on two machines, typically labelled Machine A and Machine B. Each job must first be processed on Machine A and then on Machine B, following a fixed technological sequence.
JOBS
→
Machine A
→
Machine B
This situation is commonly addressed using Johnson’s Rule, a method designed to minimize total processing time (makespan) for jobs passing through two machines.
Johnson’s Rule: Steps
- List the processing times of each job on both machines.
- Identify the job with the shortest processing time among all remaining jobs.
-
- If the shortest time is on Machine A, schedule that job as early as possible.
- If the shortest time is on Machine B, schedule that job as late as possible.
- In case of a tie, prioritize the job for early scheduling.
- Repeat the process until all jobs are scheduled.
Example
Four jobs (A, B, C, D) need to be processed on Machines A and B. The processing times are as follows:
| Job | Machine A (min) | Machine B (min) |
| A | 7 | 2 |
| B | 5 | 6 |
| C | 4 | 8 |
| D | 6 | 4 |
Step 1: The shortest processing time is 2 minutes (Job A on Machine B).
→ Schedule Job A last.
Step 2: Among the remaining jobs, the next shortest time is 4 minutes (Job C on Machine A).
→ Schedule Job C first.
Step 3: Next shortest is 5 minutes (Job B on Machine A).
→ Schedule Job B second.
Step 4: Only Job D remains. It is scheduled before Job A.
Final sequence: C → B → D → A
| Jobs | Machine 1 | Machine 2 | Waiting Time | |||||
| Start Time | Process Time | End Time | Start Time | Process 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 |
Waiting Time and Visualization
Once the sequence is determined, the waiting time for each job on Machine B can be calculated by tracking when Machine B becomes available after Machine A finishes processing each job.
A Gantt chart or timeline diagram can be used to visually represent the job flow and idle times on each machine.
Scheduling of n Jobs on More Than Two Machines
In some manufacturing environments, jobs must be processed sequentially on more than two machines. A special case of Johnson’s Rule can be applied in such scenarios, provided certain conditions are met. This approach helps determine the optimal job sequence to minimize the total processing time, or makespan.
Machine 1
Wash
→
Machine 2
Rinse
→
Machine 3
Dry
Car Wash Example
Consider a car wash operation where three machines are arranged in a fixed technological sequence—each dedicated to a specific task. Every car must pass through all machines in the same order. Similarly, in more complex manufacturing settings, jobs may need to be processed on three or more machines (e.g., A → B → C → D).
Let’s examine a case where four jobs (1, 2, 3, and 4) must be processed on four machines (A, B, C, and D) in the fixed sequence A → B → C → D. The processing times (in minutes) for each job on each machine are provided in a table.
| 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 |
Example: Steps for Applying Johnson’s Rule to More Than Two Machines
Step 1: Identify the minimum processing time on the first machine (A) and the last machine (D).
- In this case:
- Minimum on A = 28 minutes
- Minimum on D = 32 minutes
Step 2: Find the maximum processing time on the intermediate machines (B and C).
- Maximum on B = 16 minutes
- Maximum on C = 18 minutes
Step 3: Check the condition:
- If the minimum time on A and D is greater than or equal to the maximum time on B and C, then the problem can be reduced to a two-machine problem.
- Since 28 > 16 and 32 > 18, the condition is satisfied.
Step 4: Create two imaginary machines:
- Machine P = A + B + C (combined processing time for each job)
- Machine Q = B + C + D
Step 5: Apply Johnson’s Rule to the new two-machine problem (P and Q) to determine the optimal job sequence.
- Based on the shortest processing times, the optimal sequence is:
3 → 2 → 1 → 4
| MACHINES | ||
| Jobs | P (Process Time) | Q (Process Time) |
| 1 | 58 + 14 + 14 = 86 | 48 + 14 + 14 = 76 |
| 2 | 58 | 60 |
| 3 | 56 | 72 |
| 4 | 92 | 70 |
Performance Evaluation
After sequencing, calculate the waiting times and idle times for each machine. The results are as follows:
| Machines | Idle Time | |||||||||||
| Jobs | A | B | C | D | A | B | C | D | ||||
| Start | End | Start | End | Start | End | Start | End | |||||
| 3. | 0 | 28 | 28 | 40 | 40 | 56 | 56 | 100 | 0 | 28 | 40 | 56 |
| 2. | 28 | 58 | 58 | 68 | 68 | 86 | 100 | 132 | 0 | 58 – 40 = 18 | 68 – 56 = 12 | 100 – 100 = 0 |
| 1. | 58 | 116 | 116 | 130 | 130 | 144 | 144 | 192 | 0 | 116 – 68 = 48 | 130 – 86 = 44 | 144 – 132 = 12 |
| 4. | 116 | 180 | 180 | 196 | 196 | 208 | 208 | 250 | 0 | 180 – 130 = 50 | 196 – 144 = 52 | 208 – 192 = 16 |
- Total idle time:
- Machine A: 70 minutes
- Machine B: 198 minutes
- Machine C: 190 minutes
- Machine D: 84 minutes
- Total flow time (makespan): 250 minutes
This approach demonstrates how a complex multi-machine scheduling problem can be simplified using Johnson’s Rule, provided the necessary conditions are met.
“18 Scheduling: Importance and Methods in Manufacturing” from Operations Management by Vikas Singla is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License, except where otherwise noted.
