A note on 'Discrete sequential search with group activities'
AbstractThis note comments on a paper published by Wagner and Davis (Decision Sciences (2001), 32(4), 557–573). These authors present an integer-programming model for the single-item discrete sequential search problem with group activities. Based on their experiments, they conjecture that the problem can be solved as a linear program. In this note, we provide a counterexample for which the optimal value of the linear program they propose is different from the optimal value of the integer-programming model, hence contradicting their conjecture for the specific linear program that they specify. Furthermore, we show that the discrete sequential search problem is equivalent to scheduling a set of jobs on a single machine to minimize the sum of weighted completion times with a special bipartite graph representing the precedence constraints amongst jobs. The latter type of problems is well-studied in the field of operations research and operations management. Finally, we prove that the scheduling problem equivalent to the discrete sequential search problem studied by Wagner and Davis is strongly NP-hard. This complexity result implies that, unless P = NP, it is impossible that there exists any (compact-size) linear program for solving the discrete sequential search problem studied. To the best of our knowledge, the conjecture settled in this note was still an open question.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Katholieke Universiteit Leuven in its series Open Access publications from Katholieke Universiteit Leuven with number urn:hdl:123456789/334357.
Date of creation: Jan 2012
Date of revision:
Contact details of provider:
Web page: http://www.kuleuven.be
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Carl Demeyere).
If references are entirely missing, you can add them using this form.