Weeks 7-8: Job Shop Scheduling

Question 1

Job-Shop Scheduling

Answer 1

This is an NP-Hard problem of assigning tasks to machines, with each task belonging to a job. Tasks within jobs have a defined order of completion regardless of which machine they’re assigned to.

Question 2

Makespan

Answer 2

The length of the longest path you can take in a valid job shop schedule.

Question 3

NH_1 for Job Shop Scheduling

Answer 3

This involves swapping a random pair of consecutive tasks in a machine. Note that not all swaps are valid.

Question 4

NH_2 for Job Shop Scheduling

Answer 4

This involves swapping 2 consecutive tasks in a machine, with this pair being part of the makespan. Note that not all swaps are valid.

Question 5

Homogeneous Markov Chains

Answer 5

This approach is used in the module’s implementation of Simulated Annealing. The probability of transitioning from one state to another depends only on the current state and doesn’t change over time.

Essentially, the transition probabilities are invariant to time.

Question 6

Inhomogenous Markov Chains

Answer 6

The probability of transitioning from one state to another depends on the current state and how much time has passed since the last iteration.