Scheduling

Question 1

What type of problem is Johnson’s algorithm for, and what is its purpose?

Answer 1

Flow shop scheduling (jobs must be done in the same order on different machines)

Minimise makespan

Question 2

What type of problem is Moore’s algorithm for, and what is its purpose?

Answer 2

Job shop scheduling (identical machines)

Minimise number of tardy jobs.

Question 3

What is ‘makespan’

Answer 3

Total time taken to complete all jobs

Question 4

What is the critical ratio?

Answer 4

Time until due / processing time

Schedule the job with the smallest critical ratio first.

NB: 0/11 = 0, -27 is smaller than -14

Question 5

What is slack?

Answer 5

The length of time that a job can be delayed by but still be completed by it’s due date

Question 6

Describe Moore’s algorithm

Answer 6

1. Schedule jobs using Earliest Due Date
2. Find the first tardy job, if none, finish.
3. Reject the job with the longest processing time that is between the first scheduled job and the first tardy job (inclusive)
4. Reproduce the schedule but with rejected jobs after scheduled jobs
5. Complete when no scheduled jobs are tardy.

Question 7

How do you use Moore’s algorithm on multiple machines?

Answer 7

Same process as for a single machine but always allocate the next job description on the machine with the least amount of assigned time.

Draw a Gantt to describe.

Question 8

How do you use Johnson’s algorithm on multiple machines?

Answer 8

1. Apply Johnson’s algorithm to the first and last machines. Record the order.
2. Apply Johnson’s algorithm to the sum of the first 2 machines vs. the sum of the last 2 machines. Record the order.
3. Repeat until the sum of the first n-1 machines vs. the sum of the last n-1 machines. Record the order.
4. Draw a Gantt chart of each schedule to determine which has the shortest makespan.

Question 9

Describe Johnson’s algorithm

Answer 9

1. Select the shortest processing time of all values.
2. If it’s on machine 1, schedule the job first, if machine 2, schedule it last
3. Repeat. Resolve ties randomly.
4. Draw a Gantt to calculate the makespan.

B _ _ _ _
B _ _ _ A
B D_ _ A

etc

Question 10

Name 5 algorithms for scheduling

Answer 10

1. Earliest due date
2. Shortest processing time
3. Longest processing time
4. Critical ratio (time until due/processing time)
5. First come first served