ITEM METADATA RECORD
Title: Complexity analysis of the discrete sequential search problem with group activities
Authors: Coolen, Kris
Leus, Roel
Talla Nobibon, Fabrice
Issue Date: 2013
Publisher: IEEE
Host Document: Proceedings of the 2013 IEEE IEEM vol:e-pub
Conference: IEEE International Conference on Industrial Engineering and Engineering Management (IEEM 2013) location:Bangkok (Thailand) date:10-13 December 2013
Article number: IEEM13-P-0199
Abstract: This paper studies the computational complexity of the discrete sequential search problem with group activities, in
which a set of boxes is given and a single object is hidden in one of these boxes. Each box is characterized by a probability that it contains that object and the cost of searching that box. Furthermore, each box may be related to one or more ‘group activities’. For ‘conjunctive’ group activities, a box can be searched only when all the associated group activities have been performed whereas for ‘disjunctive’ group activities, a box can be searched as soon as at least one of the associated group activities
has been executed. A cost is also incurred when performing a
group activity. The goal is to find a sequence in which the boxes are to be searched and the group activities will be executed to minimize the expected total cost while satisfying the precedence constraints imposed by the group activities. In this paper, we prove that this problem is strongly NP-hard both for conjunctive group activities and for disjunctive group activities, and we discuss some special cases that can be solved in polynomial time.
ISBN: 978-1-4799-0985-8
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven

Files in This Item:
File Description Status SizeFormat
extended abstract ieem 2013 (2).pdfComplexity analysis of the discrete sequential search problem with group activities Published 959KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members

 




All items in Lirias are protected by copyright, with all rights reserved.