에너지 제약 하에서 지속적인 작업 수행을 위한 예비 드론 일정 조정

이 논문은 에너지 한계 하에서 다중 드론 작업의 지속적인 실행을 가능하게 하는 문제를 고려한다. 드론은 일련의 위치를 부여받고, 그들의 작업은 주어진 시간에 각 위치에서 최소한 하나의 드론이 존재하도록 보장하는 것이다, 예를 들어 모니터링을 위해. 에너지 제약으로 인해, 드론은 정기적으로 교체되어야 하며, 배터리를 교체할 수 있는 본사로 돌아가야 한다. 우리의 목표는 드론 배터리가 소모되지 않으면서 작업을 완료하는 데 필요한 최소한의 예비 드론 수를 식별하고, 드론 교체 전략을 제공하는 것이다. 우리는 주어진 작업에 대해 하나의 예비 드론이 충분한지 계산하는 효율적인 절차를 제시하고 최적의 교체 전략을 제공한다. 하나 이상의 드론이 필요할 경우, 우리는 필요한 최소한의 예비 드론 수를 찾는 것을 목표로 하며, 새로운 이진 포장 변형인 이진 최대 아이템 이중 포장(BMIDP)을 도입하여 다수의 예비 드론에 대한 교체 전략을 확장한다. 이 문제는 계산적으로 어려운 것으로 추정되므로 BMIDP 문제를 효율적으로 해결하기 위한 첫 번째 적합 그리디 근사 알고리즘을 제공한다. 모든 위치가 미리 알려진 오프라인 버전의 경우, 우리는 1.5의 근사 계수 상한을 증명하고, 위치가 하나씩 주어지는 온라인 버전의 경우, 광범위한 시뮬레이션을 통해 근사치가 평균 1.7의 계수를 제공함을 보여준다.