논문 상세보기

최소 종료시간 사격 스케줄을 위한 분지계획법 알고리즘 연구 KCI 등재

A Branch-and-Bound Algorithm to Minimize the Makespan in a Fire Scheduling Problem

  • 언어ENG
  • URLhttps://db.koreascholar.com/Article/Detail/319942
구독 기관 인증 시 무료 이용이 가능합니다. 4,000원
한국산업경영시스템학회지 (Journal of Society of Korea Industrial and Systems Engineering)
한국산업경영시스템학회 (Society of Korea Industrial and Systems Engineering)
초록

We focus on the fire scheduling problem (FSP), the problem of determining the sequence of targets to be fired at, for the objective of minimizing makespan to achieve tactical goals. In this paper, we assume that there are m available weapons to fire at n targets (> m) and the weapons are already allocated to targets. One weapon or multiple weapons can fire at one target and these fire operations should start simultaneously while the finish time of them may be different. We develop several dominance properties and a lower bound for the problem, and suggest a branch and bound algorithm implementing them. Also, In addition, heuristic algorithms that can be used for obtaining an initial upper bound in the B&B algorithm and for obtaining good solutions in a short time were developed. Computational experiments are performed on randomly generated test problems and results show that the suggested algorithm solves problems of a medium size in a reasonable amount of computation time. The proposed lower bound, the dominance properties, and the heuristics for upper bound are tested in B&B respectively, and the result showed that lower bound is effective to fathoming nodes and the dominance properties and heuristics also worked well. Also, it is showed that the CPU time required by this algorithm increases rapidly as the problem size increases. Therefore, the suggested B&B algorithm would be limited to solve large size problems. However, the employed heuristic algorithms can be effectively used in the B&B algorithm and can give good solutions for large problems within a few seconds.

목차
1. Introduction
 2. Problem Description
 3. Dominance Properties
 4. Branch and Bound Algorithm
 5. Computational Experiments
 6. Summary
 References
저자
  • Young-Ho Cha(50th Division, Republic of Korea Army, Korea) | 차영호
  • June-Young Bang(Sungkyul University, Gyeonggi-do, Korea) | 방준영 Corresponding Author