Journal of Korean Society of Industrial and Systems Engineering (산업경영시스템학회지)

Society of Korea Industrial and System Engineering (한국산업경영시스템학회)
권호 표지
DOI QR코드

DOI QR Code

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

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

  • 차영호 (대한민국 육군 50사단) ;
  • 방준영 (성결대학교 산업경영학부)
  • Received : 2015.10.08
  • Accepted : 2015.12.07
  • Published : 2015.12.31
Download PDF
⟨ Previous Next ⟩

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.

Keywords

References

  1. Ahn, N.-S., Jeong, J.-S., Jeong, W.-K., Hwang, W.-Y., and Park, S.-W., Sampling Procedures Enhancement in Government Defense Quality Assurance Procedures : Case Studies in Combat Force Support Material and Ammunition Areas. Journal of the Korean Society for Quality Management, 2012, Vol. 40, No. 3, pp. 245-258. https://doi.org/10.7469/JKSQM.2012.40.3.245
  2. Ahn, N.-S., Park, S.-W., Chae, J.-M., Lee, Y.-W., and Oh, B.-I., Suggestion of Using Defense Quality Score based on Taguchi Loss Function in Korea Defense Area. Journal of the Korean Society for Quality Management, 2013, Vol. 41, No. 3, pp. 443-456. https://doi.org/10.7469/JKSQM.2013.41.3.443
  3. Amoura, A.K., Bampis, E., Kenyon, C., and Manoussakis, Y., Scheduling independent multiprocessor tasks. Algorithmica, 2002, Vol. 32, pp. 247-261. https://doi.org/10.1007/s00453-001-0076-9
  4. Bianco, L., Dell'Olmo, P., and Speranza, M.G., Nonpreemptive scheduling of independent tasks with prespecified processor allocations. Naval Research Logistics, 1994b, Vol. 41, pp. 959-971. https://doi.org/10.1002/1520-6750(199412)41:7<959::AID-NAV3220410708>3.0.CO;2-K
  5. Blazewicz, J., Dell'Olmo, P., Drozdowski, M., and Speranza, M., Scheduling multiprocessor tasks on three dedicated processors. Information Processing Letters, 1992, Vol. 41, pp. 275-280. https://doi.org/10.1016/0020-0190(92)90172-R
  6. Bozoki, G. and Richard, J.P., A branch and bound algorithm for the continuous-process job-shop scheduling problems. AIIE Transactions, 1970, Vol. 2, pp. 246-252. https://doi.org/10.1080/05695557008974759
  7. Brucker, P. and Kramer, A., Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. European Journal of Operational Research, 1996, Vol. 90, pp. 214-216. https://doi.org/10.1016/0377-2217(95)00350-9
  8. Cha, Y.-H. and Kim, Y.-D., Fire scheduling for planned artillery attack operations under time-dependent destruction probabilities. Omega, 2010, Vol. 38, No. 5, pp. 383-392. https://doi.org/10.1016/j.omega.2009.10.003
  9. Chen, J. and Lee, C.-Y., General multiprocessor tasks scheduling. Naval Research Logistics, 1999, Vol. 46, pp. 57-74. https://doi.org/10.1002/(SICI)1520-6750(199902)46:1<57::AID-NAV4>3.0.CO;2-H
  10. Chen, J. and Miranda, A., A polynomial time approximation scheme for general multiprocessor job scheduling. SIAM Journal on Computing, 2001, Vol. 31, pp. 1-17. https://doi.org/10.1137/S0097539798348110
  11. Dell'Olmo, P., Speranza, M.G., and Tuza, Z., Efficiency and effectiveness of normal schedules on three dedicated processors. Discrete Mathematics, 1997, Vol. 164, pp. 67-79. https://doi.org/10.1016/S0012-365X(97)84781-4
  12. Drozdowski, M., Scheduling multiprocessor tasks-An overview. European Journal of Operational Research, 1996, Vol. 94, pp. 215-230. https://doi.org/10.1016/0377-2217(96)00123-3
  13. Garey, M.R. and Johnson, D.S., Computers and intractability : a guide to the theory of NP-completeness, San Francisco : Freeman, 1979.
  14. Hall, L.A., Approximation algorithms for scheduling, PWS Publishing Company, 1997, pp. 1-45.
  15. Hoogeveen, J.A., Van de Velde, S.L., and Veltman, B., Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Applied Mathematics, 1994, Vol. 55, pp. 259-272. https://doi.org/10.1016/0166-218X(94)90012-4
  16. Huang, J., Chen, J., Chen, S., and Wang, J., A simple linear time approximation algorithm for multi-processor job scheduling on four processors. Journal of Combinatorial Optimization, 2007, Vol. 13, pp. 33-45.
  17. Jansen, K. and Porkolab, L., General multiprocessor task scheduling : approximate solutions in linear time. SIAM Journal on Computing, 2005, Vol. 35, pp. 519-530. https://doi.org/10.1137/S0097539799361737
  18. Kim, D.-H. and Lee, Y.-H., The heuristic algorithm for the fire target allocation and sequencing problem. Proceedings of the 2008 spring KIIE conference, Pohang, Korea, 2008.
  19. Kim, T.-H. and Lee, Y.-H., Fire sequencing problem with shared targets. Korean Operations Research and Management Society, 2003, Vol. 28, No. 3, pp. 123-134.
  20. Kramer, A., Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors. OR Spektrum, 1997, Vol. 19, pp. 219-227. https://doi.org/10.1007/BF01545591
  21. Kubale, M., The complexity of scheduling independent two-processor tasks on dedicated processors. Information Processing Letters, 1987, Vol. 24, pp. 141-147. https://doi.org/10.1016/0020-0190(87)90176-1
  22. Kwon, O.-J., Lee, K.-S., and Park, S.-S., Targeting and scheduling problem for field artillery. Computers and Industrial Engineering, 1997, Vol. 33, pp. 693-696. https://doi.org/10.1016/S0360-8352(97)00224-6
  23. Lee, C.-Y., Lei, L., and Pinedo, M., Current trends in deterministic scheduling. Annals of Operations Research, 1997, Vol. 70, pp. 1-41. https://doi.org/10.1023/A:1018909801944
  24. Nawaz, M., Enscore, E.E., and Ham, I.-Y., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 1983, Vol. 11, No. 1, pp. 91-95. https://doi.org/10.1016/0305-0483(83)90088-9
  25. Shin, S.-S., Kim, B.-K., and Sim, C.-B., A Study on Crack Formation in the K11 Objective Individual Combat Weapon Fire Control System using Analysis of Variance. Journal of the Korean Society for Quality Management, 2015, Vol. 43, No. 3, pp. 67-73. https://doi.org/10.7469/JKSQM.2015.43.1.067
  26. Yoon, S.-H., Hwang, W.-S., Juhn, J.-H., and Lee, I.-S., A branch-and-bound algorithm on the fire sequencing for planned artillery operations. Journal of the Society of Korea Industrial and Systems Engineering, 2010, Vol. 33, No. 3, pp. 154-161.

Cited by

  1. 표적 할당 및 사격순서결정문제를 위한 최적해 알고리즘 연구 vol.42, pp.1, 2015, https://doi.org/10.11627/jkise.2019.42.1.143