유한용량 대규모 유연생산시스템 스케줄링 문제에 대한 효율적인 탐색 알고리즘 연구
A Study on an Efficient Search Algorithm for the Scheduling Problem of Capacitated Flexible Manufacturing Systems (FMS) with Considerable Scale
- 주제(키워드) FMS scheduling , deadlock avoidance , petri nets , FMS scheduling
- 발행기관 아주대학교
- 지도교수 최진영
- 발행년도 2010
- 학위수여년월 2010. 2
- 학위명 석사
- 학과 및 전공 일반대학원 산업공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000010422
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
최근 들어 제조업계에서는 효율성과 유연성을 동시에 갖추고 있는 유연생산시스템(Flexible Manufacturing System: FMS)에 대한 관심이 다시 높아지고 있는 추세이다. 또한 이러한 FMS에서 얼마나 효율적인 스케줄링을 하는가도 주요 이슈가 되고 있으며 지금까지 많은 연구가 많이 진행되어 오고 있다. 하지만 유한용량의 자원을 대상으로 확장성(Scalability)을 고려한 FMS에 대한 논리적 제어를 다룬 연구는 많이 수행되지 않았으며 최근에서야 다양한 연구가 조금씩 진행되고 있는 추세이다. 따라서 본 연구에서는 유한 용량의 대규모 FMS를 대상으로 스케줄링에 대한 연구를 하였다. FMS 스케줄링을 위해서 모델링이 우선되어야 한다. 따라서 본 연구에서 고려하는 FMS 모델은 페트리 네트(Petri Nets)를 사용하였다. 페트리 네트 기반의 모델링이 완료되면, FMS 스케줄링을 위해서 도달가능 그래프(Reachability Graph)가 사용되었다. 도달가능 그래프는 아무리 작은 규모의 FMS라 할지라도 많은 분석과 노드들의 수가 지수(exponential)적으로 증가하기 때문에 도달가능 그래프 전체를 구현하는 것은 많은 어려움이 있다. 따라서 최적의 스케줄을 정하기 위해 최선의 노드만을 탐색하는 알고리즘이 본 연구에서 진행되었다. 또한, 본 연구에서는 유한한 자원을 대상으로 FMS의 확장성(Scalability)을 고려한 효율적인 교착제어정책(Deadlock Avoidance Policy)에 대한 연구 또한 동시에 진행되었다. 이러한 알고리즘 개발을 위한 시뮬레이션 모델은 Visual Studio 2005에서 C언어를 통해 개발되었으며 그 결과를 통해 연구에서 제안한 알고리즘을 검증하였다.
more목차
논문 요약 v
표 목차 viii
그림 목차 ix
1장 서론 1
1절 연구의 배경 1
2절 연구 목적 및 방법 2
3절 논문의 구성 4
2장 기존 연구 5
1절 유한용량 FMS 스케줄링 알고리즘 문제 5
2절 교착 상태 확인 및 방지 방법론 7
3장 모델링 및 가능해 탐색 고려사항 9
1절 페트리 네트 기반 FMS 모델링 9
2절 가능해 탐색을 위한 고려사항 11
1. 효율적인 노드 탐색 11
2. 교착 제어 12
4장 탐색 알고리즘 제안 14
1절 새로운 한계 함수 제안 14
2절 우선순위 규칙의 적용 16
3절 N-Machine 사이클 탐색 방법 17
4절 P 단계 Look-ahead 방법 19
5절 제안된 A* 알고리즘 22
5장 알고리즘 성능 평가 25
1절 소규모 FMS 실험 설계 25
2절 소규모 FMS 실험 결과 분석 27
3절 확장성을 고려한 실험 설계 30
4절 대규모 FMS 실험 결과 분석 34
6장 결론 37
참고문헌 (Bibliography) 39
Abstract 42
Appendix A. 제안된 알고리즘의 모듈별 C코드 43
