Machine scheduling

Machine scheduling

1. Single machine scheduling

   • 1//Cmean & ΣCj
     • SPT
       • Increase of processing time
   • 1//ΣwjCj
     • WSPT
       • Decrease of wj/pj
   • 1//Tmax & Lmax
     • EDD
       • Increase of due date
   • 1//ΣUj Number of Tardy job
     • Moor’s algorithm
       • Initial order = EDD
         • Compare Cj and Dj
   • 1//ΣTj & 1//ΣwjTj
     • Branch and bound
       • Dividing to small node
       • Comparing the lowest number to different level
   • 1/prec/Tmax
     • Lawler’s algorithm
       • Choose lowest Tardiness to be last job
       • Choose jobs have no predecessor

2. Other scheduling method

   • FCFS
     • First come first serve
   • HWF
     • Heavy weight first

3. Notation

   • Prec
     • Precedence constraints
   • Initial order
     • Order before assigned or selected
   • Prmu
     • Permutation
       • The queues in front of each machine operates according to the FIFO discipline
       • All jobs have unchaged order on machines
   • Flow shop
     • Same order on machines
   • Job shop
     • Different order on machines

4. More than 1 machine

   • Pm /Cmax
     • LPT
       • assigns the m longest jobs to the m machines
       • The next longest job for freed machine
   • Pm /ΣCj
     • McNaughton algorithm
       • Initial order = SPT
       • Assign jobs to m machines in rotation
   • F2|prmu|Cmax (Flow shop)
     • Johnson’s rule (only for 2 machines)
       • 2 set
         • Set 1 = p1j<p2j
           • SPT of machine 1
         • Set 2 = p1j>p2j
           • LPT of machines 2
       • Set 1 go first then set 2

5. Remember to find both order and objective

6. Rotation

Images and files in the map