일정계획은 다양한 산업 분야에서 응용되는 핵심 기술로 적용 영역에 따라 승무원 일증계획(Crew Scheduling), 작업 일정계획(Job Scheduling), 할당 문제(Allocation Problem) 등으로 구분할 수 있다. 전통적으로 이런 일정계획 문제를 해결하기 위해서 수학적 프로그래밍 기법을 사용해왔으나, 최근에는 이러한 문제를 풀기 위해 제약조건 프로그래밍(Constraint Programing), 정수 계획법(Integer Programming), 선형 계획법(Linear Pro요ramming), ...
일정계획은 다양한 산업 분야에서 응용되는 핵심 기술로 적용 영역에 따라 승무원 일증계획(Crew Scheduling), 작업 일정계획(Job Scheduling), 할당 문제(Allocation Problem) 등으로 구분할 수 있다. 전통적으로 이런 일정계획 문제를 해결하기 위해서 수학적 프로그래밍 기법을 사용해왔으나, 최근에는 이러한 문제를 풀기 위해 제약조건 프로그래밍(Constraint Programing), 정수 계획법(Integer Programming), 선형 계획법(Linear Pro요ramming), Lagrangian Relaxation[B], 휴리스틱 방법 등을 적용한 연구가 활발히 이루어지고 있다. 본 연구의 대상인 승무일정계획은 주어진 승무원 근로제약조건을 모두 만족하고 최소의 승무원으로 기 수립된 열차운행 계획을 모두 처리해야 하는 복잡한 승무원 배정 문제이다. 현재 이러한 작업은 일정계획 전문가에 의해 수작업으로 이루어지고 있으며 복잡한 제약조건으로 인해 많은 시간 소요와 비상시와 같은 예외적인 상황에 신속하게 대처하기 어려운 문제점을 가지고 있다. 본 연구에서는 이러한 문제점을 해결하기 위해 제약조건프로그래밍(Constraint Programming)과 Set Partitioning 기법을 적용하여 승무일정계획을 수립하였다. 또한, 실험을 통하여 현업에서 사용하고있는 기존의 승무일정계획의 여러 통계자료와 비교·분석하여 개선된 점과 추후 연구의 필요성을 파악하였다.
일정계획은 다양한 산업 분야에서 응용되는 핵심 기술로 적용 영역에 따라 승무원 일증계획(Crew Scheduling), 작업 일정계획(Job Scheduling), 할당 문제(Allocation Problem) 등으로 구분할 수 있다. 전통적으로 이런 일정계획 문제를 해결하기 위해서 수학적 프로그래밍 기법을 사용해왔으나, 최근에는 이러한 문제를 풀기 위해 제약조건 프로그래밍(Constraint Programing), 정수 계획법(Integer Programming), 선형 계획법(Linear Pro요ramming), Lagrangian Relaxation[B], 휴리스틱 방법 등을 적용한 연구가 활발히 이루어지고 있다. 본 연구의 대상인 승무일정계획은 주어진 승무원 근로제약조건을 모두 만족하고 최소의 승무원으로 기 수립된 열차운행 계획을 모두 처리해야 하는 복잡한 승무원 배정 문제이다. 현재 이러한 작업은 일정계획 전문가에 의해 수작업으로 이루어지고 있으며 복잡한 제약조건으로 인해 많은 시간 소요와 비상시와 같은 예외적인 상황에 신속하게 대처하기 어려운 문제점을 가지고 있다. 본 연구에서는 이러한 문제점을 해결하기 위해 제약조건프로그래밍(Constraint Programming)과 Set Partitioning 기법을 적용하여 승무일정계획을 수립하였다. 또한, 실험을 통하여 현업에서 사용하고있는 기존의 승무일정계획의 여러 통계자료와 비교·분석하여 개선된 점과 추후 연구의 필요성을 파악하였다.
This paper considers the problem of subway crew scheduling. Crew Scheduling is concerned with finding a minimum number of assignments of crews to a given train schedule satisfying various restrictions. Traditionally, crew scheduling problem has been formulated as a Linear Programming, but even the L...
This paper considers the problem of subway crew scheduling. Crew Scheduling is concerned with finding a minimum number of assignments of crews to a given train schedule satisfying various restrictions. Traditionally, crew scheduling problem has been formulated as a Linear Programming, but even the LP relaxation of the problem is hard to solve due to exponential number of variables. In this paper, we propose two basic techniques that solve the problem in a reasonable time and solution. A generalized set partitioning model and a method using constraint satisfaction programming (CSP) have been used. The experimental results show that our method is an effective way of improving the crew scheduling in terms of scheduling time and quality more than those of expert.
This paper considers the problem of subway crew scheduling. Crew Scheduling is concerned with finding a minimum number of assignments of crews to a given train schedule satisfying various restrictions. Traditionally, crew scheduling problem has been formulated as a Linear Programming, but even the LP relaxation of the problem is hard to solve due to exponential number of variables. In this paper, we propose two basic techniques that solve the problem in a reasonable time and solution. A generalized set partitioning model and a method using constraint satisfaction programming (CSP) have been used. The experimental results show that our method is an effective way of improving the crew scheduling in terms of scheduling time and quality more than those of expert.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.