Ten jobs with the processing times and due dates listed in the table below are t
ID: 409717 • Letter: T
Question
Ten jobs with the processing times and due dates listed in the table below are to be processed on a single machine. 1 23 45 67 8910 Processing 23 10 Time 1612 17 14 27 13 Due Date 99 46 193101 24 112 20 8 326 128 a) Find the schedule that minimizes the mean flowtime and report the minimum mean b) Find the schedule that minimizes the maximum lateness and report the minimurm c) Find the schedule that minimizes the number of tardy jobs. Report the number of tardy d) Use the critical ratio rule to minimize the total tardiness. Report the resulting schedule e) Find the schedule that minimizes the mean flowtime such that no jobs are tardy. (20 f) Suppose now that these ten jobs are to be processed on two identical machines running flowtime. (10 points) maximum lateness value. (10 points) jobs in this schedule. (10 points) and the corresponding total tardiness value. (10 points) points) in parallel. Find the schedule on each one of the machines to minimize the mean flowtime. Report the corresponding mean flowtime value. (10 points)Explanation / Answer
a.
The Shortest processing time (SPT) rule minimizes the mean flowtime of schedule. According to SPT rule, the task with shortest processing time is sequenced first. Thus sequence is as follows:
Sequence
Job
PT
DD
Completion time
1
6
7
112
7
2
2
10
46
17
3
4
12
101
29
4
9
13
326
42
5
7
14
209
56
6
3
16
193
72
7
5
17
24
89
8
10
22
128
111
9
1
23
99
134
10
8
27
58
161
Total Flow time
718
Mean flowtime
71.8
The mean flowtime is 71.8
b. The Earliest Due Date rule is used to minimize the maximum lateness of schedule. According to EDD rule, the jobs are sequenced from earliest to latest due date of job. The sequence is obtained as follows:
Sequence
Job
PT (pj)
DD (dj)
Completion time (Cj)
Lateness (Lj)
Lj = Cj – dj
1
5
17
24
17
-7
2
2
10
46
27
-19
3
8
27
58
54
-4
4
1
23
99
77
-22
5
4
12
101
89
-12
6
6
7
112
96
-16
7
10
22
128
118
-10
8
3
16
193
134
-59
9
7
14
209
148
-61
10
9
13
326
161
-165
The maximum lateness is -4, thus none of the job is delayed beyond due date.
c.
Steps for reducing the number of tardy jobs:
From part b, there is no lateness in scheduling, thus number of tardy jobs are zero.
d.
Critical ratio = Due date/Processing time
Job
PT
DD
Critical Ratio
1
23
99
99/23
= 4.3
2
10
46
4.6
3
16
193
12.1
4
12
101
8.4
5
17
24
1.4
6
7
112
16.0
7
14
209
14.9
8
27
58
2.1
9
13
326
25.1
10
22
128
5.8
The job with lowest CR is sequenced first, the sequence is as follows:
Sequence
Job
PT (pj)
DD (dj)
CR
Completion time (Cj)
Lateness (Lj)
Lj = Cj – dj
Tardiness
= Max(0, Lj)
1
5
17
24
1.4
17
-7
0
2
8
27
58
2.1
44
-14
0
3
1
23
99
4.3
67
-32
0
4
2
10
46
4.6
77
31
31
5
10
22
128
5.8
99
-29
0
6
4
12
101
8.4
111
10
10
7
3
16
193
12.1
127
-66
0
8
7
14
209
14.9
141
-68
0
9
6
7
112
16.0
148
36
36
10
9
13
326
25.1
161
-165
0
Total tardiness = 31 +10 +36 = 77
Sequence
Job
PT
DD
Completion time
1
6
7
112
7
2
2
10
46
17
3
4
12
101
29
4
9
13
326
42
5
7
14
209
56
6
3
16
193
72
7
5
17
24
89
8
10
22
128
111
9
1
23
99
134
10
8
27
58
161
Total Flow time
718
Mean flowtime
71.8
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.