무인 운반 차량을 기반으로 하는 물류 시스템은 그 성능을 결정짓는 변수가 많기 때문에 그 설계나 운영에서 고려해야 할 점이 많고 또한 복잡하다. 따라서 시스템의 보다 효율적인 운영을 위해서는 그 설계 단계부터 무인 운반 차량의 수, 무인 운반 차량의 유도경로 및 이동방향, 대기/대피 위치, 물류 흐름 패턴, 차량 할당 정책 등에 대한 주의 깊은 결정이 필요하다. 이들 중 필요한 반송 물량을 처리하기 위한 작업 할당 정책은 반송 시스템 설계나 운영을 위해서 필요한 가장 기본적이고 중요한 변수이다.실제 산업현장에서는 작업 할당 방법으로 대부분 발견적 작업계획 알고리즘(HSA: ...
무인 운반 차량을 기반으로 하는 물류 시스템은 그 성능을 결정짓는 변수가 많기 때문에 그 설계나 운영에서 고려해야 할 점이 많고 또한 복잡하다. 따라서 시스템의 보다 효율적인 운영을 위해서는 그 설계 단계부터 무인 운반 차량의 수, 무인 운반 차량의 유도경로 및 이동방향, 대기/대피 위치, 물류 흐름 패턴, 차량 할당 정책 등에 대한 주의 깊은 결정이 필요하다. 이들 중 필요한 반송 물량을 처리하기 위한 작업 할당 정책은 반송 시스템 설계나 운영을 위해서 필요한 가장 기본적이고 중요한 변수이다.실제 산업현장에서는 작업 할당 방법으로 대부분 발견적 작업계획 알고리즘(HSA: HeuristicScheduling Algorithm)을 많이 사용하고 있다. 왜냐하면, 실제 산업 현장에서는 자동 물류 관리시스템(AMHS: Automated Material Handling System)이 제조 공정내에서 가동되고 있는 모든 반송시스템에 대한 데이터를 처리해야 하고, 또한 실시간으로 발생하는 작업들에 대한 작업할당을 수행해야 하는데, 이러한 규칙들은 이해하기 쉽고 적용하기가 용이하고 계산시간이 적게 소요된다는 장점을 가지고 있기 때문이다. 하지만, 기존의 발견적 작업계획 알고리즘은 각각의 차량이 다음 작업을 선택할 때 자신의 관점에서만 최적의 작업을 선택하기 때문에 전체 물류 시스템 관점에서는 최적의 선택이 아닐 수 있다.본 연구에서 중점을 두고자 하는 부분은 자동 물류 관리시스템에서 사용되는 작업 할당 방법(차량배차규칙)에 관한 것으로서 기존의 발견적 작업계획 알고리즘가 가지고 있는 이러한 문제점을 해결하기 위한 방법으로 유전 알고리즘을 이용하여, 기존의 규칙보다 우수한 성능을 발휘할 수 있는 실시간 작업 할당계획(Real-Time Job-Scheduling) 방법을 제안하였다.본 연구에서 제안한 방식의 우수성을 검증하기 위해서 자체 개발한 시뮬레이터를 사용하였으며, 기존에 산업 현장에서 많이 사용되고 있는 발견적 작업계획 알고리즘중에서 FCFS(First Come First Served), STT/D(Shortest Traveling Time&Distance), NJF(Nearest Job First)와 동일한 조건으로 진행한 시뮬레이션결과를 비교함으로서 제안한 방법의 우수성을 검증하였다.수행 평가로는 이동시간의 평균값 및 해당 표준편차의 3 sigma 값, 반송시간의 평균값 및 해당 표준편차의 3 sigma 값, 시간당 평균 반송량, 무인 반송차량의 가동율을 사용하였으며, 시간당 평균 작업 발생량을 94개, 134개로 두 번에 걸쳐서 실시하였다.
무인 운반 차량을 기반으로 하는 물류 시스템은 그 성능을 결정짓는 변수가 많기 때문에 그 설계나 운영에서 고려해야 할 점이 많고 또한 복잡하다. 따라서 시스템의 보다 효율적인 운영을 위해서는 그 설계 단계부터 무인 운반 차량의 수, 무인 운반 차량의 유도경로 및 이동방향, 대기/대피 위치, 물류 흐름 패턴, 차량 할당 정책 등에 대한 주의 깊은 결정이 필요하다. 이들 중 필요한 반송 물량을 처리하기 위한 작업 할당 정책은 반송 시스템 설계나 운영을 위해서 필요한 가장 기본적이고 중요한 변수이다.실제 산업현장에서는 작업 할당 방법으로 대부분 발견적 작업계획 알고리즘(HSA: Heuristic Scheduling Algorithm)을 많이 사용하고 있다. 왜냐하면, 실제 산업 현장에서는 자동 물류 관리시스템(AMHS: Automated Material Handling System)이 제조 공정내에서 가동되고 있는 모든 반송시스템에 대한 데이터를 처리해야 하고, 또한 실시간으로 발생하는 작업들에 대한 작업할당을 수행해야 하는데, 이러한 규칙들은 이해하기 쉽고 적용하기가 용이하고 계산시간이 적게 소요된다는 장점을 가지고 있기 때문이다. 하지만, 기존의 발견적 작업계획 알고리즘은 각각의 차량이 다음 작업을 선택할 때 자신의 관점에서만 최적의 작업을 선택하기 때문에 전체 물류 시스템 관점에서는 최적의 선택이 아닐 수 있다.본 연구에서 중점을 두고자 하는 부분은 자동 물류 관리시스템에서 사용되는 작업 할당 방법(차량배차규칙)에 관한 것으로서 기존의 발견적 작업계획 알고리즘가 가지고 있는 이러한 문제점을 해결하기 위한 방법으로 유전 알고리즘을 이용하여, 기존의 규칙보다 우수한 성능을 발휘할 수 있는 실시간 작업 할당계획(Real-Time Job-Scheduling) 방법을 제안하였다.본 연구에서 제안한 방식의 우수성을 검증하기 위해서 자체 개발한 시뮬레이터를 사용하였으며, 기존에 산업 현장에서 많이 사용되고 있는 발견적 작업계획 알고리즘중에서 FCFS(First Come First Served), STT/D(Shortest Traveling Time&Distance), NJF(Nearest Job First)와 동일한 조건으로 진행한 시뮬레이션결과를 비교함으로서 제안한 방법의 우수성을 검증하였다.수행 평가로는 이동시간의 평균값 및 해당 표준편차의 3 sigma 값, 반송시간의 평균값 및 해당 표준편차의 3 sigma 값, 시간당 평균 반송량, 무인 반송차량의 가동율을 사용하였으며, 시간당 평균 작업 발생량을 94개, 134개로 두 번에 걸쳐서 실시하였다.
The Job Shop Scheduling Problem is a strongly NP-hard problem of combinatorial optimization and one of the best-known machine scheduling problem. During the last three decades, this problem has captured the interest of a significant number of researchers. A lot of literature has been published, but ...
The Job Shop Scheduling Problem is a strongly NP-hard problem of combinatorial optimization and one of the best-known machine scheduling problem. During the last three decades, this problem has captured the interest of a significant number of researchers. A lot of literature has been published, but no efficient solution algorithm has been found yet for solving this problem optimality in polynomial time. This has led to recent interest in using genetic algorithms to address the problem.However, genetic algorithms are not applicable to real-time job scheduling, so heuristic rules are adopted in manufacturing environments. Since genetic algorithm needs computational efforts.In this paper, we present the problem of scheduling real-time jobs in multiple AGV system and propose a scheduling algorithm to be applicable to real-time job scheduling. The goal of this research is to improve the performance of job scheduling and to develop the efficient scheduling method based on genetic algorithms.
The Job Shop Scheduling Problem is a strongly NP-hard problem of combinatorial optimization and one of the best-known machine scheduling problem. During the last three decades, this problem has captured the interest of a significant number of researchers. A lot of literature has been published, but no efficient solution algorithm has been found yet for solving this problem optimality in polynomial time. This has led to recent interest in using genetic algorithms to address the problem.However, genetic algorithms are not applicable to real-time job scheduling, so heuristic rules are adopted in manufacturing environments. Since genetic algorithm needs computational efforts.In this paper, we present the problem of scheduling real-time jobs in multiple AGV system and propose a scheduling algorithm to be applicable to real-time job scheduling. The goal of this research is to improve the performance of job scheduling and to develop the efficient scheduling method based on genetic algorithms.
주제어
#무인 반송 차량
#물류시스템
#유전자 알고리즘
#genetic algorithms
#실시간 작업할당계획
#AGV system
#real-time job scheduling
학위논문 정보
저자
정승일
학위수여기관
연세대학교 대학원
학위구분
국내석사
학과
전기전자공학과
지도교수
김은태
발행연도
2006
총페이지
x, 49장
키워드
무인 반송 차량,
물류시스템,
유전자 알고리즘,
genetic algorithms,
실시간 작업할당계획,
AGV system,
real-time job scheduling
※ AI-Helper는 부적절한 답변을 할 수 있습니다.