A Branch-and-Bound Algorithm to Minimize the Makespan in a Fire Scheduling Problem
0
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (26)
- 안남수, "국방 품질보증 활동 강화를 위한 샘플링 방법 개선: 전투물자 및 탄약 분야 사례 위주", 품질경영학회지, 40(3), pp.245~258 (2012), 한국품질경영학회[DOI]
- 안남수, "다구찌 손실함수 개념을 응용한 국방품질스코어 적용 가능성에 대한 연구 : 군수품 사례 위주", 품질경영학회지, 41(3), pp.443~456 (2013), 한국품질경영학회[DOI]
- Amoura, A. K., "Scheduling independent multiprocessor tasks", Algorithmica, 32, pp.247~261 (2002)
- Bianco, L., "Nonpreemptive scheduling of independent tasks with prespecified processor allocations", Naval Research Logistics, 41, pp.959~971 (1994)
- Blazewicz, J., "Scheduling multiprocessor tasks on three dedicated processors", Information Processing Letters, 41, pp.275~280 (1992)
- Bozoki, G., "A branch and bound algorithm for the continuous-process job-shop scheduling problems", AIIE Transactions, 2, pp.246~252 (1970)
- Brucker, P., "Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems", European Journal of Operational Research, 90, pp.214~216 (1996)
- Cha, Y.-H., "Fire scheduling for planned artillery attack operations under time-dependent destruction probabilities", Omega, 38(5), pp.383~392 (2010)
- Chen, J., "General multiprocessor tasks scheduling", Naval Research Logistics, 46, pp.57~74 (1999)
- Chen, J., "A polynomial time approximation scheme for general multiprocessor job scheduling", SIAM Journal on Computing, 31, pp.1~17 (2001)
- Dell’Olmo, P., "Efficiency and effectiveness of normal schedules on three dedicated processors", Discrete Mathematics, 164, pp.67~79 (1997)
- Drozdowski, M., "Scheduling multiprocessor tasks-An overview", European Journal of Operational Research, 94, pp.215~230 (1996)
- Garey, M.R., "Computers and intractability : a guide to the theory of NP-completeness" (1979), Freeman
- Hall, L.A., "Approximation algorithms for scheduling", pp.1~45 (1997), PWS Publishing Company
- Hoogeveen, J. A., "Complexity of scheduling multiprocessor tasks with prespecified processor allocations", Discrete Applied Mathematics, 55, pp.259~272 (1994)
- Huang, J., "A simple linear time approximation algorithm for multi-processor job scheduling on four processors", Journal of Combinatorial Optimization, 13, pp.33~45 (2007)
- Jansen, K., "General multiprocessor task scheduling : approximate solutions in linear time", SIAM Journal on Computing, 35, pp.519~530 (2005)
- Kim, D.-H., "The heuristic algorithm for the fire target allocation and sequencing problem", Proceedings of the 2008 spring KIIE conference (2008)
- 김태헌, "공유표적을 포함한 사격순서 결정에 관한 연구", 한국경영과학회지, 28(3), pp.123~134 (2003), 한국경영과학회
- Kramer, A., "Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors", OR Spektrum, 19, pp.219~227 (1997)
- Kubale, M., "The complexity of scheduling independent two-processor tasks on dedicated processors", Information Processing Letters, 24, pp.141~147 (1987)
- Kwon, O. -J., "Targeting and scheduling problem for field artillery", Computers and Industrial Engineering, 33, pp.693~696 (1997)
- Lee, C. -Y., "Current trends in deterministic scheduling", Annals of Operations Research, 70, pp.1~41 (1997)
- Nawaz, M., "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem", Omega, 11(1), pp.91~95 (1983)
- 신상식, "분산분석을 활용한 K11 복합형소총 사격통제장치 균열발생 원인 연구", 품질경영학회지, 43(3), pp.289~298 (2015), 한국품질경영학회[DOI]
- 윤상흠, "포병부대 사격순서결정을 위한 분지한계 알고리즘 연구", 산업경영시스템학회지, 33(3), pp.154~161 (2010), 한국산업경영시스템학회