|
|
제 목 |
Backtracking error... |
|
작성자 |
김대경 |
작성일 |
2002-01-30 |
조회수 |
1535 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
안녕하세요?
Flow-shop의 Sequence problem을 모델링하고자 합니다.
매뉴얼의 Job-shop예제처럼 대개 unary resource를 사용한 모델링의 rank goal에 비춰보면,
1. unary reource로 line을 구성하고,
2. 각 resource에 해당하는 activity를 정의하고,resource간 선후관계를 설정하며,
3. goal로써 critical resource를 선택하고, 이 resource에 대해 activity들의 순서를 rank하는 재귀골을 만들어서 사용하려합니다.
그러면
ILCGOAL0(solver) {
res = 기계선택함수();
rc = RC선택함수(res);
return IlcAnd(IlcOr(TryRankFirst(rc),TryNotRankFirst(rc),this);
}처럼 표현할 수 있고,
IlcGoal TryRankFirst(rc) { rc.rankFirst(); return 0 };
IlcGoal TryNotRankFirst(rc) { rc.rankNotFirst(); return 0 };
처럼 나타낼 수가 있을텐데,
predefined된 IloRankForward처럼 이렇게하면 activity들이 flow-shop의 가장 기본적인 성격인 FIFO를 위배하는 경우가 생깁니다. unary resource간에 가상의 버퍼가 있다고 가정하는 것 같은데, 암튼 기본적으로 selector가 activity의 일률적인 빠르고 느림으로 판단하기 때문에 FIFO를 만족하지 않습니다..
그래서, 첫번째 기계 혹은 critical resource의 기계에서 activity들의 순서를 정한 후, 이러한 순서를 다른 기계에도 적용하거나, 혹은 정해진 resource constraint의 순서를 외부변수 등에 기억을 하고, 다음 기계에서 resource constraint가 불려질때 이 rc에 연결되어있고 기억된 변수를 참조하여 할당하거나 하려고 합니다. 문제는 한 번의 해, 즉 choice point나 backtracking없이 해를 구성하는 것은 될지모르나, backtracking의 구현이 쉽지가 않고, 예를 들어 하나의 activity의 순서가 바뀌어지면 다른 모든 기계에서도 적용이 되어야 하기 때문에 backtracking, jump등이 일어나야 할 것 같기도 하구요..
reversiblity가 모든 객체에 적용이 된다고 하는데, IlcInt가 아닌 IlcRevInt객체의 존재와 SetObject(),그리고 골에서 다른 함수의 호출 등은 reversibility가 잘 되지 않는 것 같습니다..
이런 문제의 경우 backtracking에 대해 설명을 부탁드립니다...
이러한 backtracking 및 선택에 대한 goal 아이디어등...
남은 2002년 1월의 30, 31일 잘 보내시고,
한국의 ilog의 활성화를 바라며...
감사드립니다! 안녕히계세요!
Ilog Solver/Scheduler 5.1 for Windows.
|
|
|
|
