https://www.optaplanner.org/docs/optaplanner/latest/construction-heuristics/construction-heuristics.html

1. First fit

• default order로 모든 planning entities를 순회한다.
• 각 planning entity를 사용 가능한 가장 최적의 planning value에 배정한다.
• Move 후 score가 나빠지지 않으면 바로 pick 한다.
• Score가 나빠진 경우에는 그나마 가장 좋은 Score를 가진 경우를 pick하고, 가장 첫번째 것을 pick한다.
  

2. First fit decreasing

• 기본적으로 first fit 가 동일하나, 가장 어려운 planning entity를 먼저 계산한다.
• 그 이유는 그들을 마지막에 배정하는 경우, short 발생의 확률이 높기 때문이다.
• planning entity difficulty comparision 정의는 별도로 지정한다.
• 일반적으로 많은 경우에, first fit보다 낫다고 평가받는다. (그러나 모든 경우는 아니다.)
  

3. Weakest fit

• first fit과 거의 동일하나, 가장 약한(Weakest) planning variables에 배정한다.
• strong planning variable은 나중에도 배정되기 쉽기 때문이다.
• planning value strength comparision은 별도로 지정한다.

4. Weakest fit decreasing

• First fit decreasing과 weakest fit을 혼합하였다.
• planning entity는 planning entity difficulty 정의에 따라 배정하고, planning value는 planning value strength 에 따라 배정한다.

5. Strong fit

• weakest fit과 반대 개념이다.
• 가장 강한 planning variable에 먼저 배정한다.

6. Strong fit decreasing

• first fit decreasing과 strong fit을 혼합한다.
• difficulty가 낮은 planning entity와 strength가 높은 planning variable을 먼저 배정한다.

7. Allocate entity from queue

1 put all entities in a queue.
2 assign first entity (from that queue) to the best value
3 repeat until all entities are assigned.

9. Cheapest Insertion

• 한 step에 모든 planning entities를 다 시도한다.
  

10. Regrest Insertion

• Cheapest insertion과 유사
• 그러나 best score를 가진 planning entity-value 쌍을 찾는 것이 아니라, 개선 효과가 가장 큰 entity-value 쌍을 찾는다.
• 하나의 planning entity에서 best score를 가진 planning value와 second score를 가진 planning value의 score 차이가 가장 큰 것
• 현재 optaplanner에서 아직 구현 전임

11. Allocate from pool

• Cheapest insertion과 regret insertion을 응용

1. Put all entity-value combinations in a pool
2. Assign the best entity th best value.
3. repeat until all entities are assigned