Ten jobs with the processing times and due dates listed in t

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)

Solution

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