Chapter 16, Problem 17P

Given the following information on job times and due dates, determine the optimal processing sequence using (1) FCFS, (2) SPT, (3) EDD, and (4) CR. For each method, find the average job flow time and the average job tardiness. Jobs are listed in order of arrival.

Summary Introduction

To determine: Sequence of jobs based on decision rule First Come First Served (FCFS).

Introduction: First Come First Served is the scheduling rule, which helps to arrange the sequence in the order. Here, the first come would be served first.

Answer to Problem 17P

The sequence is a-b-c-d-e-f.

Explanation of Solution

Given information:

Job	Job time (hours)	Due date (hours)
a	3.5	7
b	2.0	6
c	4.5	18
d	5.0	22
e	2.5	4
f	6.0	20

Determine the sequence using FCFS:

According to FCFS, the first come would be served first. Hence, the jobs should be sequenced in the order as per its arrival.

Hence, the sequence of jobs using FCFS is a-b-c-d-e.

Summary Introduction

To determine: Sequence of jobs based on decision rule Shortest Processing Time (SPT).

Introduction: Shortest Processing Tine is the scheduling rule, which helps to arrange the sequence in the order. Here, job with the shortest duration would be served first. Then, the process would be going on from shortest to largest duration.

Answer to Problem 17P

The sequence is b-e-a-c-d-f.

Explanation of Solution

Given information:

Job	Job time (hours)	Due date (hours)
a	3.5	7
b	2.0	6
c	4.5	18
d	5.0	22
e	2.5	4
f	6.0	20

Determine the sequence using SPT:

According to SPT, the job that has the shortest processing would be served first and it goes on as the processing time increase. Duration should be assembled in the ascending order

Hence, the sequence of jobs using SPT is b-e-a-c-d-f.

Summary Introduction

To determine: Sequence of jobs based on decision rule Earliest Due Date (EDD).

Introduction: Earliest Due Date is the scheduling rule, which helps to arrange the sequence in the order. Here, job with the earliest due date would be served first. Then, the process would be going on from earliest due date to latest due date.

Answer to Problem 17P

The sequence is e-b-a-c-f-d.

Explanation of Solution

Given information:

Job	Job time (hours)	Due date (hours)
a	3.5	7
b	2.0	6
c	4.5	18
d	5.0	22
e	2.5	4
f	6.0	20

Determine the sequence using EDD:

According to EDD, the job that has the earliest due date would be served first and it goes on as the due date increases. The job should be arranged based on due date. Due date should be assembled in the ascending order

Hence, the sequence of jobs using EDD is e-b-a-c-f-d.

Summary Introduction

To determine: Sequence of jobs based on decision rule critical ratio.

Introduction: Critical ratio is kind of scheduling rule that helps to identify that, the task or job is on the correct track. It would help to identify if the task is behind or ahead of the schedule.

Answer to Problem 17P

The sequence is e-a-b-f-c-d.

Explanation of Solution

Given information:

Job	Job time (hours)	Due date (hours)
a	3.5	7
b	2.0	6
c	4.5	18
d	5.0	22
e	2.5	4
f	6.0	20

Determine the sequence using critical ratio:

Initial critical ratio should be determined at day 0:

Job	Job time (hours)	Due date (hours)	Critical ratio
a	3.5	7	2.
b	2.0	6	3
c	4.5	18	4
d	5.0	22	4.4
e	2.5	4	1.6
f	6.0	20	3.33

Critical ratio for Job a:

It is can be determined by dividing the value attained by subtracting the completion day of previous job from the due date of current job with the processing time.

$\begin{array}{c}\text{Critical ratio}=\frac{\text{Due date}-\text{Completion day of completed job}}{\text{Processing time}}\\ =\frac{7-0}{3.5}\\ =2\end{array}$

Note: The procedure continues for all the jobs.

Job e has the lowest critical ratio. Thus, it will be completed first. Hence, Job e would be completed first in the sequence of jobs.

Determine the critical ratio after the completion of Job a:

As the processing time of job a is 2.5 hours, completion day of completed day would be 2.5.

Job	Job time (hours)	Due date (hours)	Critical ratio
a	3.5	7	1.29
b	2.0	6	1.75
c	4.5	18	3.44
d	5.0	22	3.90
e
f	6.0	20	2.90

Critical ratio for Job a:

It is can be determined by dividing the value attained by subtracting the completion day of completed job from the due date of current job with the processing time.

$\begin{array}{c}\text{Critical ratio}=\frac{\text{Due date}-\text{Completion day of completed job}}{\text{Processing time}}\\ =\frac{7-2.5}{3.5}\\ =1.29\end{array}$

Note: The procedure continues for all the jobs.

Job a has the lowest critical ratio. Hence, Job a would be completed next in the sequence of jobs after Job e.

Determine the critical ratio after the completion of Job e and Job a:

As the processing time of job e is 2.5 hours and Job a is 3.5, completion day of completed day would be 6 (2.5+3.5).

Job	Job time (hours)	Due date (hours)	Critical ratio
a
b	2.0	6	0
c	4.5	18	2.67
d	5.0	22	3.20
f	6.0	20	2.33

Critical ratio for Job b:

It is can be determined by dividing the value attained by subtracting the completion day of completed job from the due date of current job with the processing time.

$\begin{array}{c}\text{Critical ratio}=\frac{\text{Due date}-\text{Completion day of completed job}}{\text{Processing time}}\\ =\frac{6-6}{2}\\ =0\end{array}$

Note: The procedure continues for all the jobs.

Job b has the lowest critical ratio. Hence, Job b would be completed next in the sequence of jobs after Job e and Job a.

Determine the critical ratio after the completion of Job e, Job a, and Job b:

As the processing time of job e is 2.5 hours, Job a is 3.5, and Job b is 2. Completion day of completed day would be 8 (2.5+3.5+2).

Job	Job time (hours)	Due date (hours)	Critical ratio
a
b
c	4.5	18	2.22
d	5.0	22	2.80
f	6.0	20	2.00

Critical ratio for Job c:

It is can be determined by dividing the value attained by subtracting the completion day of completed job from the due date of current job with the processing time.

$\begin{array}{c}\text{Critical ratio}=\frac{\text{Due date}-\text{Completion day of completed job}}{\text{Processing time}}\\ =\frac{18-8}{4.5}\\ =2.22\end{array}$

Note: The procedure continues for all the jobs.

Job f has the lowest critical ratio. Hence, Job f would be completed next in the sequence of jobs.

Determine the critical ratio after the completion of Job e, Job a, Job b, and Job f:

As the processing time of job e is 2.5 hours, Job a is 3.5, Job b is 2, and Job f is 6.0. Completion day of completed day would be 14 (2.5+3.5+2+6).

Job	Job time (hours)	Due date (hours)	Critical ratio
a
b
c	4.5	18	2.22
d	5.0	22	2.80
f

Critical ratio for Job c:

It is can be determined by dividing the value attained by subtracting the completion day of completed job from the due date of current job with the processing time.

$\begin{array}{c}\text{Critical ratio}=\frac{\text{Due date}-\text{Completion day of completed job}}{\text{Processing time}}\\ =\frac{18-14}{4.5}\\ =0.89\end{array}$

Note: The procedure continues for all the jobs.

Job c has the lowest critical ratio. Hence, Job c would be completed next in the sequence of jobs.

As Job d is the remaining job, it will be completed next.

Hence, the sequence of jobs using critical ratio is e-a-b-f-c-d.

Determine the average flow time and average tardiness:

First Come First Served:

Job	Job time (hours)	Due date (hours)	Flow time	Tardiness
a	3.5	7	3.5
b	2.0	6	5.5
c	4.5	18	10.0
d	5.0	22	15.0
e	2.5	4	17.5	13.5
f	6.0	20	23.5	3.5
Total	23.5		75.0	17.0

Supporting calculation:

Processing time and due date are given for each job. Flow time is the cumulative of the processing time.

Tardiness of Job a, Job, b, Job c, and Job d:

Flow time of Job a, Job b, Job c, and Job d is less than its respective due date. Hence, there would be no tardiness.

Tardiness of Job e:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job e is 13.5.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =17.5-4\\ =13.5\end{array}$

Tardiness of Job f:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job f is 3.5.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =23.5-20\\ =3.5\end{array}$

Average flow time:

It is calculated by dividing the total flow time and number of jobs.

$\begin{array}{c}\text{Average flow time}=\frac{\text{Total flow time}}{\text{Number of jobs}}\\ =\frac{75}{6}\\ =12.5\text{ hours}\end{array}$

Hence, average flow time is 12.5 hours.

Average tardiness:

It is calculated by dividing the total tardiness and number of jobs.

$\begin{array}{c}\text{Average tardiness}=\frac{\text{Total tardiness}}{\text{Number of jobs}}\\ =\frac{17}{6}\\ =2.83\text{}\text{ hours}\end{array}$

Hence, average tardiness is 2.83 hours

Shortest processing time:

Job	Job time (hours)	Due date (hours)	Flow time	Tardiness
b	2.0	6	2.0
e	2.5	4	4.5	0.5
a	3.5	7	8.0	1.0
c	4.5	18	12.5
d	5.0	22	17.5
f	6.0	20	23.5	3.5
Total	23.5		68.0	5.0

Supporting calculation:

Processing time and due date are given for each job. Flow time is the cumulative of the processing time.

Tardiness of Job b, Job c, and Job d:

Flow time of Job b, Job c, and Job d is less than its respective due date. Hence, there would be no tardiness.

Tardiness of Job e:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job e is 0.5.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =4.5-4\\ =0.5\end{array}$

Tardiness of Job a:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job a is 1.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =8-7\\ =1\end{array}$

Tardiness of Job f:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job f is 3.5.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =23.5-20\\ =3.5\end{array}$

Average flow time:

It is calculated by dividing the total flow time and number of jobs.

$\begin{array}{c}\text{Average flow time}=\frac{\text{Total flow time}}{\text{Number of jobs}}\\ =\frac{68}{6}\\ =11.33\text{}\text{ hours}\end{array}$

Hence, average flow time is 11.33 hours.

Average tardiness:

It is calculated by dividing the total tardiness and number of jobs.

$\begin{array}{c}\text{Average tardiness}=\frac{\text{Total tardiness}}{\text{Number of jobs}}\\ =\frac{5}{6}\\ =0.83\text{ hours}\end{array}$

Hence, average tardiness is 0.83 hours

Earliest Due Date:

Job	Job time (hours)	Due date (hours)	Flow time	Tardiness
e	2.5	4	2.5
b	2.0	6	4.5
a	3.5	7	8.0	1.0
c	4.5	18	12.5
f	6.0	20	18.5
d	5.0	22	23.5	1.5
Total	23.5		69.5	2.5

Supporting calculation:

Processing time and due date are given for each job. Flow time is the cumulative of the processing time.

Tardiness of Job e, Job b, Job c, and Job f:

Flow time of Job e, Job b, Job c, and Job f is less than its respective due date. Hence, there would be no tardiness.

Tardiness of Job a:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job a is 1.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =8-7\\ =1\end{array}$

Tardiness of Job d:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job d is 1.5.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =23.5-22\\ =1.5\end{array}$

Average flow time:

It is calculated by dividing the total flow time and number of jobs.

$\begin{array}{c}\text{Average flow time}=\frac{\text{Total flow time}}{\text{Number of jobs}}\\ =\frac{69.5}{6}\\ =11.58\text{ hours}\end{array}$

Hence, average flow time is 11.58 hours.

Average tardiness:

It is calculated by dividing the total tardiness and number of jobs.

$\begin{array}{c}\text{Average tardiness}=\frac{\text{Total tardiness}}{\text{Number of jobs}}\\ =\frac{2.5}{6}\\ =0.42\text{ hours}\end{array}$

Hence, average tardiness is 0.42 hours

Critical ratio:

Job	Job time (hours)	Due date (hours)	Flow time	Tardiness
e	2.5	4	2.5
a	3.5	7	6.0
b	2.0	6	8.0	2.0
f	6.0	20	14.0
c	4.5	18	18.5	0.5
d	5.0	22	23.5	1.5
Total	23.5		72.5	4.0

Supporting calculation:

Processing time and due date are given for each job. Flow time is the cumulative of the processing time.

Tardiness of Job e, Job a, and Job f:

Flow time of Job e, Job a, and Job f is less than its respective due date. Hence, there would be no tardiness.

Tardiness of Job b:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job b is 2.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =8-6\\ =2\end{array}$

Tardiness of Job c:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job c is 0.5.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =18.5-18\\ =0.5\end{array}$

Tardiness of Job d:

It is calculated by subtracting the flow time of the job from the due date of the project. Hence, the lateness of Job d is 1.5.

$\begin{array}{c}\text{Tardiness}=\text{Flow time}-\text{Due date}\\ =23.5-22\\ =1.5\end{array}$

Average flow time:

It is calculated by dividing the total flow time and number of jobs.

$\begin{array}{c}\text{Average flow time}=\frac{\text{Total flow time}}{\text{Number of jobs}}\\ =\frac{72.5}{6}\\ =12.08\text{ hours}\end{array}$

Hence, average flow time is 12.08 hours.

Average tardiness:

It is calculated by dividing the total tardiness and number of jobs.

$\begin{array}{c}\text{Average tardiness}=\frac{\text{Total tardiness}}{\text{Number of jobs}}\\ =\frac{4}{6}\\ =0.67\text{hours}\end{array}$

Hence, average tardiness is 0.67 hours.