Question

Processing times and due dates of 9 ¡obs are given as follows: Job Proc Time Due Date 9 10 38 15 43 35 40 25 20 40 Assume that all jobs arrive at time 0 a) (3 points) Generate a schedule that minimizes the mean flow time. Break ties with the smallest job number first (i.e, if 3 and 8 have identical parameters, 3 should be scheduled first). b) (3 points) Calculate mean flow time, mean tardiness, and maximum tardiness of the schedule obtained in a)

Answer 1

Minimum Flow Time is achieved with the SPT (shortest processing time) method. Mimimising maximum tardiness is with the EDD (earliest due date method). workings as follows :

a and b
Shortest Processing Time (SPT)
Job	In	Out	Due Date	Tardiness
2	0	3	40	-37
1	3	7	35	-28
7	7	13	40	-27
3	13	20	44	-24
8	20	27	22	5
5	27	35	20	15
4	35	44	25	19
9	44	54	38	16
6	54	69	43	26
Mean Flow Time		30.22222
Mean Tardiness		-3.88889
Maximum Tardiness		26 days
c and d
Earliest Due Date Method
Job	Start	End	Due Date	Tardiness
5	0	8	20	-12
8	8	15	22	-7
4	15	24	25	-1
1	24	28	35	-7
9	28	38	38	0
2	38	41	40	1
7	41	47	40	7
6	47	62	43	19
3	62	69	44	25
Mean Flow Time		36.88889
Mean Tardiness		2.777778
Maximum Tardiness		25 days