Earticle

초록

영어

Scheduling problems can be classified into offline and online ones. This paper considers an online scheduling problem to minimize makespan on the identical parallel machines. For dynamically arrived jobs with their ready times, we show that the sequencing order according to the ERD (Earliest Ready Date) rule is optimal to minimize makespan. This paper suggests an algorithm by using the MIP(Mixed Integer Programming) formulation periodically to find a good periodic schedule and evaluates the required computational time and resulted makespan of the algorithm. The comparition with an offline scheduling shows our algorithm makes the schedule very fast and the makespan can be reduced as the period time reduction, so we can conclude that our algorithm is useful for scheduling the jobs under online environment even though the number of jobs and machines is large. We expect that the algorithm is invaluable one to find good schedules for the smart factory and online scheduler using the blockchain mechanism.

한국어

일정계획은 오프라인(offline) 일정계획과 온라인(online) 일정계획으로 구분할 수 있고, 본 논문은 온 라인 상황에서 병렬설비의 주기적 일정계획 수립문제를 다룬다. 도착시간(ready time)이 다른 여러 작업들에 대해 makespan을 최소화하기 위한 작업 일정계획 알고리즘 개발이 목적이다. 이를 위해 각 설비에서의 작업 처리 순서는 ERD(Earliest Ready Date) 규칙에 따른 순서가 최적임을 밝혔다. 각 설비 별 배정 작업도 결정 해야하는 병렬설비 문제를 위해서는 혼합정수계획모형(MIP)을 이용하는 알고리즘을 제시하였다. 개발한 알고 리즘의 유용성과 성능분석을 위해 수치 예를 활용하여 오프라인 일정계획과 비교하였다. 비교분석 결과, 오프 라인 일정계획에 비해 매우 빠른 시간에 일정계획을 수립할 수 있음을 보였고, 주기시간의 감소를 통한 makespan의 단축 가능성을 보였다. 본 논문의 주기적 일정계획 방법은 계획수립을 위한 시간이 매우 작으므 로, 설비 및 작업의 수가 많은 온라인 환경에서도 활용할 수 있다. 더불어서 스마트공장이나 블록체인 플랫폼 에서의 작업일정 수행을 위해 활용될 수 있을 것으로 기대한다.

목차

요약
Abstract
1. 서론
1.1 연구 배경 및 필요성
1.2 선행연구
1.3 연구 목적
2. 작업 일정계획 모델
3. 주기적 일정계획 수립 알고리즘
3.1 일정계획 수립 알고리즘
3.2 알고리즘 사용 예
3.3 알고리즘 활용 방안
4. 결론
REFERENCES

키워드

주기적 일정계획 Makespan ERD 혼합정수계획모형 온라인 블록체인 Periodic Scheduling Makespan ERD MIP formulation Online Blockchain

저자

• 주운기 [ Un Gi Joo | 선문대학교 산업경영공학과 교수 ] Corresponding author

참고문헌

발행기관

간행물