A note on 'Efficient scheduling of periodic information monitoring requests'

A recently published paper by Zeng et al. [Zeng, D.D., Dror, M., Chen, H., 2006. Efficient scheduling of periodic information monitoring requests. European Journal of Operational Research 173, 583-599] considers the non-preemptive scheduling of periodic server information requests for mission-critical monitoring applications such as policing and homeland security. In their paper, it was claimed that the decision version of the considered Periodic Monitoring (PM) problem was NP-Complete, and several greedy heuristics were developed to 'efficiently' solve the problem. The standard argument of polynomial-time solution verification was employed in their complexity proof. However, the present note points out that the PM problem is actually -Complete, and verification of a PM solution is coNP-Complete, in the strong sense. A consequence of these results is that the greedy heuristics proposed by Zeng et al. are all strongly coNP-Hard, invalidating the authors' claims of efficiency; since their algorithms are implemented on-line in a mission-critical application, this clearly needs to be taken into account. The final contributions of the present note are the description of an efficient algorithm for the underlying peak server load problem, and showing that equivalence classes in request start times can be efficiently detected and pruned prior to searching. These former elements - if incorporated into the original heuristics - can potentially improve stability and efficiency by large orders of magnitude.