University of Leicester
Browse

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

Download (124.78 kB)
journal contribution
posted on 2009-07-15, 14:42 authored by Michael J. Short
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 Σ2 p-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.

History

Citation

European Journal of Operational Research, 2009, article in press.

Published in

European Journal of Operational Research

Publisher

Elsevier

issn

0377-2217

Copyright date

2009

Available date

2009-07-15

Publisher version

http://www.sciencedirect.com/science/article/pii/S0377221709001520

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC