Single Machine Schedulling

Question 1

Whats an active schedule?

Answer 1

Schedule is active if no schedule can be constructed by changing the order of
jobs on machines where at least one operation finishes earlier and no operation finishes later

Question 2

Whats a semi-active schedule

Answer 2

semi-active if no operation can be completed earlier without
changing the order of jobs on any of the machines

Question 3

basic assumptions of the single machine environment?

Answer 3

• n single-operation jobs are simultaneously available for processing
• Machines only process one job at a time
• Setup times are part of the processing times
• Machines are continuously available
• Once an operation begins, it proceeds without interruption

Question 4

Whats the procedure of SPT

Answer 4

Schedule jobs with the shortest processing time first

Question 5

Whats the procedure or WSPT?

Answer 5

Jobs are sequenced in decreasing order of wj/pj

Question 6

how does SRPT Rule (Shortest Remaining Processing Time First) and for which environment its more effective

Answer 6

Whenever a job is completed or released, process the job with the shortest
remaining processing time among the jobs available.
Ideal for 1|rj,prmp|sum(Cj)

Question 7

How does the EDD Rule work?

Answer 7

Process jobs in increasing order of their due dates.

Question 8

How does the Lowest Cost Last Algorithm work and for which environment does it work better?

Answer 8

Check notes, and for 1|prec|hmax

Question 9

How does the Moores Algorithm work and for which environment does it work better?

Answer 9

Check notes, and for 1||Sum(Uj)

Question 10

How does the travelling salesman (TSP) algorithm work? For which environment does it work better?

Answer 10

Check notes, and for 1|sjk|Cmax