Question:medium
The computer centre (CC) in an institute manages the central server for which researchers queue to run their computer programs. CC processes programs only one at a time. Four computer programs are available at 10:00 am on a given day. The time required to run each program on the central server and their respective promised time of completion (i.e., due date) on that same day are given in the table.
Program 1 2 3 4 Processing time (in minutes) 60 40 90 100 Promised time (i.e., due date) 12 noon 11:30 am 1:00 pm 1:30 pm
If the CC follows shortest processing time (SPT) rule to sequence the computer programs, then number of tardy jobs is ______.
Note: Ignore program change-over times.
The computer centre (CC) in an institute manages the central server for which researchers queue to run their computer programs. CC processes programs only one at a time. Four computer programs are available at 10:00 am on a given day. The time required to run each program on the central server and their respective promised time of completion (i.e., due date) on that same day are given in the table.
| Program | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Processing time (in minutes) | 60 | 40 | 90 | 100 |
| Promised time (i.e., due date) | 12 noon | 11:30 am | 1:00 pm | 1:30 pm |
If the CC follows shortest processing time (SPT) rule to sequence the computer programs, then number of tardy jobs is ______.
Note: Ignore program change-over times.
Show Hint
Arrange the programs in increasing order of processing time, compute each program's completion time by adding processing times cumulatively from 10:00 am, and compare each with its due date.
Updated On: Aug 5, 2026
Show Solution
Correct Answer: 2
Solution and Explanation
Step 1: Understanding the Concept:
We need to build the actual clock-time schedule that results from the SPT rule and then compare each program's finish time with its promised due date.
Step 2: Key Formula or Approach:
SPT rule: sort programs in increasing order of processing time.
Processing times: Program 2 (40) $<$ Program 1 (60) $<$ Program 3 (90) $<$ Program 4 (100).
So the run sequence is: 2, then 1, then 3, then 4.
A program is tardy only if its actual completion clock time is later than its promised due date.
Step 3: Detailed Explanation:
The server starts at 10:00 am and runs one program after another with no gaps.
Program 2 runs first: starts 10:00 am, takes 40 minutes, finishes at 10:40 am. Due date is 11:30 am, so it is on time.
Program 1 runs next: starts 10:40 am, takes 60 minutes, finishes at 11:40 am. Due date is 12:00 noon, so it is on time.
Program 3 runs next: starts 11:40 am, takes 90 minutes, finishes at 1:10 pm. Due date is 1:00 pm, so it is 10 minutes late, tardy.
Program 4 runs last: starts 1:10 pm, takes 100 minutes, finishes at 2:50 pm. Due date is 1:30 pm, so it is 1 hour 20 minutes late, tardy.
Final Answer:
Two programs, numbers 3 and 4, finish after their promised times.
\[ \boxed{\text{Number of tardy jobs} = 2} \]
We need to build the actual clock-time schedule that results from the SPT rule and then compare each program's finish time with its promised due date.
Step 2: Key Formula or Approach:
SPT rule: sort programs in increasing order of processing time.
Processing times: Program 2 (40) $<$ Program 1 (60) $<$ Program 3 (90) $<$ Program 4 (100).
So the run sequence is: 2, then 1, then 3, then 4.
A program is tardy only if its actual completion clock time is later than its promised due date.
Step 3: Detailed Explanation:
The server starts at 10:00 am and runs one program after another with no gaps.
Program 2 runs first: starts 10:00 am, takes 40 minutes, finishes at 10:40 am. Due date is 11:30 am, so it is on time.
Program 1 runs next: starts 10:40 am, takes 60 minutes, finishes at 11:40 am. Due date is 12:00 noon, so it is on time.
Program 3 runs next: starts 11:40 am, takes 90 minutes, finishes at 1:10 pm. Due date is 1:00 pm, so it is 10 minutes late, tardy.
Program 4 runs last: starts 1:10 pm, takes 100 minutes, finishes at 2:50 pm. Due date is 1:30 pm, so it is 1 hour 20 minutes late, tardy.
Final Answer:
Two programs, numbers 3 and 4, finish after their promised times.
\[ \boxed{\text{Number of tardy jobs} = 2} \]
Was this answer helpful?
0
