Machine scheduling

Single machine scheduling
1. 1//Cmean & ΣCj
  1. SPT
    1. Increase of processing time
2. 1//ΣwjCj
  1. WSPT
    1. Decrease of wj/pj
3. 1//Tmax & Lmax
  1. EDD
    1. Increase of due date
4. 1//ΣUj Number of Tardy job
  1. Moor’s algorithm
    1. Initial order = EDD
      1. Compare Cj and Dj
5. 1//ΣTj & 1//ΣwjTj
  1. Branch and bound
    1. Dividing to small node
    2. Comparing the lowest number to different level
6. 1/prec/Tmax
  1. Lawler’s algorithm
    1. Choose lowest Tardiness to be last job
    2. Choose jobs have no predecessor
Other scheduling method
1. FCFS
  1. First come first serve
2. HWF
  1. Heavy weight first
Notation
1. Prec
  1. Precedence constraints
2. Initial order
  1. Order before assigned or selected
3. Prmu
  1. Permutation
    1. The queues in front of each machine operates according to the FIFO discipline
    2. All jobs have unchaged order on machines
4. Flow shop
  1. Same order on machines
5. Job shop
  1. Different order on machines
More than 1 machine
1. Pm /Cmax
  1. LPT
    1. assigns the m longest jobs to the m machines
    2. The next longest job for freed machine
2. Pm /ΣCj
  1. McNaughton algorithm
    1. Initial order = SPT
    2. Assign jobs to m machines in rotation
3. F2|prmu|Cmax (Flow shop)
  1. Johnson’s rule (only for 2 machines)
    1. 2 set
      1. Set 1 = p1j<p2j
        SPT of machine 1
      2. Set 2 = p1j>p2j
        LPT of machines 2
    2. Set 1 go first then set 2
Remember to find both order and objective
Rotation

Next up

Machine scheduling

Description

Resource summary

Media attachments

0 comments

Similar

	Created by hoàng đậu over 9 years ago