Zusammenfassung der Ressource
Machine
scheduling
- 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
- Other scheduling method
- FCFS
- First come first serve
- HWF
- Heavy weight first
- 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
- 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
- Remember to find both order and objective
- Rotation