a. Consider the single-machine total tardiness minimization problem below. Job 1

Question

a. Consider the single-machine total tardiness minimization problem below.

Job

1

2

3

4

Processing Time

2

5

3

2

Due Date

3

7

9

19

(a) Consider the sequence 1 – 2 – 3 – 4 as the initial seed, and apply the neighborhood search with adjacent
pairwise interchange (API). Stop when you find a new seed.

(b) Let the total tardiness value of the EDD schedule be an upper bound on the total tardiness. To find the optimal
schedule of jobs, apply the branch-and-bound algorithm using the best-first approach.

Job

1

2

3

4

Processing Time

2

5

3

2

Due Date

3

7

9

19

Explanation / Answer

A,

So 1-2-3-4 is the best case.

Job Processing Time Due Date Start Finish Tardiness Job Processing Time Due Date Start Finish Tardiness 1 2 3 0 2 0 1 2 3 0 2 0 2 5 7 2 7 0 3 3 9 2 5 0 3 3 9 7 10 1 2 5 7 5 10 3 4 2 19 10 12 0 4 2 19 10 12 0 0.25 0.75 Job Processing Time Due Date Start Finish Tardiness 1 2 3 0 2 0 2 5 7 2 7 0 4 2 19 7 9 0 3 3 9 9 12 3 0.75 Job Processing Time Due Date Start Finish Tardiness 1 2 3 0 2 4 2 19 2 4 2 5 7 4 9 2 3 3 9 9 12 3 2.5 Job Processing Time Due Date Start Finish Tardiness 1 2 3 0 2 0 4 2 19 2 4 0 3 3 9 4 7 0 2 5 7 7 12 5 1.25

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.