Parallel Machine Schedulling

Question 1

What are the basic assumptions of Parallel Machine Schedulling

Answer 1

General assumption is again p1 ≥ p2 ≥ ⋯ ≥ pn
* Mj specifies the set of machines suitable for processing job j

Question 2

Describe the two types of bounds in this type of schedulling

Answer 2

Job based bounds
- The makespan must be at least as long as the processing time of the longest job

Machine based bounds
- At best, all processing time is spread evenly among the machines

Question 3

Whats the theoretical bound for Pm||Cmax?

Answer 3

(Cmax(LPT)/Cmax(OPT)) <= (4/3) - (1/3m))

Question 4

Whats the theoretical bound for Pm|prec|Cmax?

Answer 4

(Cmax(LIST)/Cmax(OPT)) <= 2 - (1/m)

Question 5

Whats the Critical Path rule?

Answer 5

The job at the head of the longest string of jobs in the
precedence graph is given highest priority. Optimal for Pm|pj= 1, tree| Cmax

Question 6

How does Largest Number of Successors (LNS) work?

Answer 6

The job with the highest
number of successors in the precedence graph is given priority.

Question 7

Describe how does LFJ works

Answer 7

Every time a machine is freed, the job with the
smallest number of compatible machines is selected.

Question 8

If Mj are nested, describe the 4 condiitions that should hold?

Answer 8

Mj = Mk
* Mj ⊂ Mk
* Mk ⊂ Mj
* Mj ∩ Mk = ∅

Question 9

How does the Least Flexible Machine Rule works?

Answer 9

Prioritize the least flexible machine,
i.e., the machine with the lowest number of remaining jobs

Question 10

How does the Least Flexible Machine – Least Flexible Job (LFM-LFJ) heuristic work?

Answer 10

At each point
in time, consider the least flexible machine and assign the least flexible job which
may be processed on it.

Question 11

Formulate the Linear Programming Formulation for: Pm|prmp|Cmax

Answer 11

Check notes

Question 12

Whats the algorithm that goes best with Pm|prmp|Cmax? Describe it

Answer 12

LRPT First Rule

Question 13

How does the Longest Remaining Processing Time (LRPT) First Rule work?

Answer 13

Prioritize job with
longest remaining processing time.

Question 14

For which environments does Longest Remaining Processing Time on Fastest Machine (LRPT-FM) Rule work?

Answer 14

Qm|prmp|Cmax or Qm|prmp,rj|Cmax

Question 15

Which algorithm should be used when dealing with Pm||Sum(Cj)?

Answer 15

SPT

Question 16

Which algorithm should be used when dealing with Pm||Sum(wjCj)?

Answer 16

WSPT

Question 17

Formulate the integer program for Rm||sum(Cj)

Answer 17

Check notes

Question 18

Whats the ideal algorithm to use when Pm|prmp|sum(Cj)

Answer 18

Non-preemtive SPT

Question 19

Whats the ideal algorithm to use when Qm|prmp|sum(Cj)

Answer 19

SRPT on the Fastest Machine
Assign at any given point in time the job with the shortest remaining
processing time to the fastest machine, the job with the second
shortest remaining processing time to the second fastest machine,
and so on.