Question

Two students, Jim and Kim, are planning all-nighter to prepare for their interviews the following morning. Between them, they have only one set of materials in the following 5 subjects: OM, PS, MKT, FIN, ACC. Based on their previous experience, they estimate that they will need the following amount of time (in hours) with each set of materials.

Subject	Job	JIM	KIM
Contracts	1	1.8	1.2
Torts	2	0.8	2.2
Civil	3	3.1	0.7
Corporate	4	1.1	0.5
Patents	5	2.3	1.5

They agree that Kim will get the opportunity to see each set of notes before Jim. Assume that they start their study at 8:00 pm. Determine the exact times that each will begin and end by studying each subject in order to maximize combined sleep they can get before the interview. Give the rule used.

Answer 1

This is a classic "2" machine "n" job scheduling problem. Here Kim and Jim act as machine and the materials serve as the jobs. Now we have to maximize their sleeping hour we can achieve that by minimizing their study hour. For that we can use Johnson's rule.

Johnson's rule:

This method is applicable when the machine orders are fixed, here too each set will go to Kim first then it will go to Jim.

Step 1: Find the minimum study time from all the subjects.

Step 2: If the minimum study time belongs to Kim, then the corresponding subject will be studied/chosen first, if the minimum study time belongs to Jim then the the corresponding subject will be chosen last. In case there is tie between the minimum study time then choose any subject arbitrarily and assign it first.

Step 3: After one subject is assigned, remove that particular subject from the table and repeat step 1 and step 2 till all the subjects are assigned.

Solution:

Let the sequence of the subjects be _ _ _ _ _

i) From the table the lowest study time is 0.5 hour, this belongs to Kim so this subject will be studied first.

Now, The sequence become 4_ _ _ _ , and remove job 4 from the table.

ii) Now from the revised table 0.7 is the lowest study time this also belongs to Kim ,so the particular subject 3 will also be studied first but after 4 as 4 has already been assigned.

Now, The sequence becomes 4 3 _ _ _.

Remove job 3 from the table

iii) Form the revised table the lowest study time is 0.8 which belongs to Jim, so the corresponding subject i.e "2" will be studied last , so now the sequence become 4 3 _ _ 2.

iv) the lowest value is 1.2, which is for subject 1 and it belongs to Kim, so as usual it will be processed first, now the sequence becomes 4 3 1 _ 2.

v) As only one subject left, that particular subject will go with the blank.

The final sequence is 4 3 1 5 2.

The time schedule is given in the following table.

Job/Subject	Study hour for kim(hour)		Study hour for Jim(hour)
	Start	Finish	Start	Finish
4	8:00 AM	8.5 AM	8.5 AM	9.6 AM
3	8.5 AM	9.2 AM	9.6 AM	0.7 AM
1	9.2 AM	10.4 AM	0.7 AM	2.5 AM
5	10.4 AM	11.9 AM	2.5 AM	4.8 AM
2	11.9 AM	2.1 AM	4.8 AM	5.6 AM

P.S: Subject names are bit confusing, so I have taken subject number for the entire calculation.