Slack-based Ordering Heuristic(Precedence constraint-posting slack)

[Cheng&Smith, 1996]

• For two unordered operations I and J

  • Slack(I J) = Lftj – Esti – (Duri + Durj)
  • Bslack(I J) = Slack (I J) / f(S), (f(S) is similarity measure)

• Min-Slack Selection (Variable Ordering)

  • Choose opeations pairs with minimum value of
    Min (Bslack(I J), Bslack(J I) )
    

• Max-Slack Posting (Value Ordering)

  • Select the precedent constraint that leaves maximum remaining slack
    Max(Bslack(I J), Bslack(J I) )
    

• This slack-based heuristic performs competitively with contention-based heuristic

• Significantly improved by combining with consistency enforcement methods (Baptiste, Le Pape, Nuijten, 1995)

  
  

Esti

di

Lfti

Estj

dj

Lftj

Previous slide

Next slide

Back to first slide

View graphic version