표적 할당 및 사격순서결정문제를 위한 최적해 알고리즘 연구
Exact Algorithm for the Weapon Target Assignment and Fire Scheduling Problem
0
조회
0
다운로드
5
인용
0
참고문헌
키워드
초록
We focus on the weapon target assignment and fire scheduling problem (WTAFSP) with the objective of minimizing the makespan, i.e., the latest completion time of a given set of firing operations. In this study, we assume that there are m available weapons to fire at n targets (> m). The artillery attack operation consists of two steps of sequential procedure : assignment of weapons to the targets; and scheduling firing operations against the targets that are assigned to each weapon. This problem is a combination of weapon target assignment problem (WTAP) and fire scheduling problem (FSP). To solve this problem, we define the problem with a mixed integer programming model. Then, we develop exact algorithms based on a dynamic programming technique. Also, we suggest how to find lower bounds and upper bounds to a given problem. To evaluate the performance of developed exact algorithms, computational experiments are performed on randomly generated problems. From the results, we can see suggested exact algorithm solves problems of a medium size within a reasonable amount of computation time. Also, the results show that the computation time required for suggested exact algorithm can be seen to increase rapidly as the problem size grows. We report the result with analysis and give directions for future research for this study. This study is meaningful in that it suggests an exact algorithm for a more realistic problem than existing researches. Also, this study can provide a basis for developing algorithms that can solve larger size problems.
Abstract
We focus on the weapon target assignment and fire scheduling problem (WTAFSP) with the objective of minimizing the makespan, i.e., the latest completion time of a given set of firing operations. In this study, we assume that there are m available weapons to fire at n targets (> m). The artillery attack operation consists of two steps of sequential procedure : assignment of weapons to the targets; and scheduling firing operations against the targets that are assigned to each weapon. This problem is a combination of weapon target assignment problem (WTAP) and fire scheduling problem (FSP). To solve this problem, we define the problem with a mixed integer programming model. Then, we develop exact algorithms based on a dynamic programming technique. Also, we suggest how to find lower bounds and upper bounds to a given problem. To evaluate the performance of developed exact algorithms, computational experiments are performed on randomly generated problems. From the results, we can see suggested exact algorithm solves problems of a medium size within a reasonable amount of computation time. Also, the results show that the computation time required for suggested exact algorithm can be seen to increase rapidly as the problem size grows. We report the result with analysis and give directions for future research for this study. This study is meaningful in that it suggests an exact algorithm for a more realistic problem than existing researches. Also, this study can provide a basis for developing algorithms that can solve larger size problems.
참고문헌 (28)
- Amoura, A. K., "Scheduling independent multiprocessor tasks", Algorithmica, 32(2), pp.247~261 (2002)
- Blazewicz, J., "Scheduling multiprocessor tasks on three dedicated processors", Information Processing Letters, 41(5), pp.275~280 (1992)
- Bozoki, G., "A branch and bound algorithm for the continuous-process job-shop scheduling problems", AIIE Transactions, 2(3), pp.246~252 (1970)
- Cetin, E., "A weapon-target assignment approach to media allocation", Applied Mathematics Computation, 175(2), pp.1266~1275 (2006)
- 차영호, "A Branch-and-Bound Algorithm to Minimize the Makespan in a Fire Scheduling Problem", 한국산업경영시스템학회지, 38(4), pp.132~141 (2015), 한국산업경영시스템학회
- Chang, T., "Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization", Applied Soft Computing, 70, pp.845~863 (2018)
- Chen, J., "General multiprocessor tasks scheduling", Naval Research Logistics, 46(1), pp.57~74 (1999)
- Choi, Y. -B., "Deterministic and robust optimization approach for single artillery unit fire scheduling problem", Applied Sciences, 7(10), pp.1038~ (2017)
- Yu Jun Choi, "A Fire Sequencing Problem to Minimize the Total Weighted Firing Completion Time of the Artillery Weapons", Industrial Engineering & Management Systems, 17(2), pp.249~258 (2018), 대한산업공학회[DOI]
- Day, R. H., "Allocating weapons to target complexes by means of nonlinear programming", Operations Research, 14(6), pp.992~1013 (1966)
- Dell’Olmo, P., "Efficiency and effectiveness of normal schedules on three dedicated processors", Discrete Mathematics, 164(1-3), pp.67~79 (1997)
- Drozdowski, M., "Scheduling multiprocessor tasks-An overview", European Journal of Operational Research, 94(2), pp.215~230 (1996)
- Garey, M.R., "Computers and intractability : a guide to the theory of NP-completeness" (1979), Freeman
- Goemans, M. R., "An approximation algorithm for scheduling on three dedicated machines", Discrete Applied Mathematics, 61(1), pp.49~59 (1995)
- Hall, L.A., "Approximation algorithms for scheduling", pp.1~45 (1997), PWS Publishing Company
- Huang, J., "A simple linear time approximation algorithm for multi-processor job scheduling on four processors", Journal of Combinatorial Optimization, 13(1), pp.33~45 (2007)
- Karasakal, O., "Air defense missile-target allocation models for a naval task group", Computers & Operations Research, 35(6), pp.1759~1770 (2008)
- 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), 한국경영과학회
- Kline, A, "The weapon-target assignment problem", Computers and Operations Research (2018)
- Kwon, O. -J., "Lagrangian relaxation approach to the targeting problem", Naval Research Logistics, 46(6), pp.640~653 (1999)
- Kwon, O. -J., "Targeting and scheduling problem for field artillery", Computers & Industrial Engineering, 33(3-4), pp.693~696 (1997)
- Kwon, O. -J., "A branch-and-price algorithm for a targeting problem", Naval Research Logistics, 54(7), pp.732~741 (2007)
- Lee, C. -Y., "Current trends in deterministic scheduling", Annals of Operations Research, 70, pp.1~41 (1997)
- Li, X., "Weapon-target assignment problem by multiobjective evolutionary algorithm based on decomposition", Complexity, 2018, pp.19~ (2018)
- Lloyd, S.P, "Weapons allocation is NP-complete", Proceedings of the 1986 Summer Conference on Simulation, pp.1054~1058
- Manne, A., "A target assignment problem", Operations Research, 6(3), pp.346~351 (1958)
- Taylor, J. L., "Planning by resource allocation methods-illustrated by military applications", Operations Research, 12(5), pp.693~706 (1964)