Please use this identifier to cite or link to this item:
Title: A note on 'Efficient scheduling of periodic information monitoring requests'.
Authors: Short, Michael J.
First Published: 2009
Publisher: Elsevier
Citation: European Journal of Operational Research, 2009, article in press.
Abstract: 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.
DOI Link: 10.1016/j.ejor.2009.03.011
ISSN: 0377-2217
Type: Article
Rights: This is the author's final draft of the paper in press in European Journal of Operational Research, 2009. The corrected proof is available from Doi: 10.1016/j.ejor.2009.03.011
Appears in Collections:Published Articles, Dept. of Engineering

Files in This Item:
File Description SizeFormat 
MJS - EJOR - 2009 v02.pdf124.78 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.