Question:
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 3, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 2
Solution and Explanation
Step 1: Understanding the Concept:
This is a single-machine job sequencing problem.
We must sequence the four programs using the Shortest Processing Time (SPT) rule and then check how many finish after their promised due date.
Step 2: Key Formula or Approach:
Under SPT, jobs are ordered from smallest to largest processing time.
It is easier to work in minutes elapsed since 10:00 am rather than switching between clock times at every step, so convert every due date into "minutes after 10:00 am" first.
A job is tardy if its cumulative completion time (in minutes) exceeds its due time (in minutes).
Step 3: Detailed Explanation:
Processing times: Program 1 = 60, Program 2 = 40, Program 3 = 90, Program 4 = 100 minutes.
SPT order: Program 2, Program 1, Program 3, Program 4.
Convert due dates to minutes after 10:00 am: Program 2 due 11:30 am = 90 min, Program 1 due 12:00 noon = 120 min, Program 3 due 1:00 pm = 180 min, Program 4 due 1:30 pm = 210 min.
Now accumulate processing times in SPT order:
Program 2: completion = 40 min (limit 90 min), on time.
Program 1: completion = 40 + 60 = 100 min (limit 120 min), on time.
Program 3: completion = 100 + 90 = 190 min (limit 180 min), tardy by 10 min.
Program 4: completion = 190 + 100 = 290 min (limit 210 min), tardy by 80 min.
Final Answer:
Programs 3 and 4 finish after their due times, so exactly 2 jobs are tardy.
\[ \boxed{\text{Number of tardy jobs} = 2} \]
This is a single-machine job sequencing problem.
We must sequence the four programs using the Shortest Processing Time (SPT) rule and then check how many finish after their promised due date.
Step 2: Key Formula or Approach:
Under SPT, jobs are ordered from smallest to largest processing time.
It is easier to work in minutes elapsed since 10:00 am rather than switching between clock times at every step, so convert every due date into "minutes after 10:00 am" first.
A job is tardy if its cumulative completion time (in minutes) exceeds its due time (in minutes).
Step 3: Detailed Explanation:
Processing times: Program 1 = 60, Program 2 = 40, Program 3 = 90, Program 4 = 100 minutes.
SPT order: Program 2, Program 1, Program 3, Program 4.
Convert due dates to minutes after 10:00 am: Program 2 due 11:30 am = 90 min, Program 1 due 12:00 noon = 120 min, Program 3 due 1:00 pm = 180 min, Program 4 due 1:30 pm = 210 min.
Now accumulate processing times in SPT order:
Program 2: completion = 40 min (limit 90 min), on time.
Program 1: completion = 40 + 60 = 100 min (limit 120 min), on time.
Program 3: completion = 100 + 90 = 190 min (limit 180 min), tardy by 10 min.
Program 4: completion = 190 + 100 = 290 min (limit 210 min), tardy by 80 min.
Final Answer:
Programs 3 and 4 finish after their due times, so exactly 2 jobs are tardy.
\[ \boxed{\text{Number of tardy jobs} = 2} \]
Was this answer helpful?
0
0
Top GATE PI Production Engineering (Manufacturing) Questions
- Which one of the following pure metals has the hexagonal close packed (HCP) crystal structure at room temperature?
- To create 12 divisions on a disc by using simple indexing and dividing head on a horizontal milling machine, choose the correct option for the rotation of the crank pin.
- Which among the following is/are TRUE for friction stir welding (FSW) process?
- Exit-hole occurrence is common in:
- In a direct current arc welding, the voltage \( V \) (in volt) is related to the arc length \( l \) (in cm) as \[ V = 30 + 30l. \] The open circuit voltage is 80 volts. The maximum possible arc length is ............. (Rounded off to two decimal places)
View More Questions
Top GATE PI Questions
- In an air-standard Otto cycle, the pressure and temperature of air just before the compression stroke are 200 kPa and 26.85 °C, respectively. The combustion process is assumed to be a constant volume process, where 1.02 MJ/kg heat is added. The cycle efficiency is 50%. The adiabatic index \(γ\) and specific heat at constant volume \(C_v\) can be considered to be constant during the process (corresponding values taken at the mean cycle temperature).
Assuming that the ideal gas law is applicable, \(γ = \frac 43\) and \(c_v= 0.85\ kJ/kg-K\), the maximum pressure (in MPa) reached during the cycle is _____ . (Rounded off to 1 decimal place) - A metallic cylindrical pressure vessel, used to store compressed air in a plant, has 1 m mean radius and 4 mm wall thickness. The maximum allowable normal and shear stresses in the cylindrical portion of the vessel are 100 MPa and 40 MPa, respectively. Considering only these data in the design, the maximum allowable internal gauge pressure (in MPa) of the compressed air is ______ . (Rounded off to 2 decimal places)
- A flat belt drive with pulley of r = 20 cm radius is designed to transmit 6.283 kW power at 600 RPM. In the figure, τ is the corresponding torque. If the coefficient of static friction between the belt and the pulley is 0.3, then the minimum value of the tightening force F (in kN) required to prevent the belt slip is _____ . (Rounded off 2 decimal places)
- Mild steel plates are welded to make butt joints by arc welding with 85% heat transfer efficiency ignoring other losses. The first weld joint is made by selecting arc voltage of 30 V and current of 180 A with a welding speed of 6 mm/s. Using identical plates, a second weld joint is made with the same arc voltage and a welding speed of 8 mm/s. If both the welds have the same heat input, then the welding current (in A) for the second weld joint is _____. (Answer in integer)
- In a single pass cold rolling operation, a flat plate is reduced to a thickness of 3 mm. In this operation, two rolls of diameter 400 mm each are rotating in opposite direction at 300 RPM, and the elastic deflection of these rolls is negligible. The angle of bite is 10°. If the neutral point is present at an angle of 7° from the exit side, then the thickness of the plate (in mm) at the neutral point is _____ . (Rounded off to 1 decimal place)
View More Questions