IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v237y2014i2p448-453.html
   My bibliography  Save this article

On the complexity of project scheduling to minimize exposed time

Author

Listed:
  • Pinker, Edieal
  • Szmerekovsky, Joseph
  • Tilson, Vera

Abstract

We consider project scheduling where the project manager’s objective is to minimize the time from when an adversary discovers the project until the completion of the project. We analyze the complexity of the problem identifying both polynomially solvable and NP-hard versions of the problem. The complexity of the problem is seen to be dependent on the nature of renewable resource constraints, precedence constraints, and the ability to crash activities in the project.

Suggested Citation

  • Pinker, Edieal & Szmerekovsky, Joseph & Tilson, Vera, 2014. "On the complexity of project scheduling to minimize exposed time," European Journal of Operational Research, Elsevier, vol. 237(2), pages 448-453.
    • Handle: RePEc:eee:ejores:v:237:y:2014:i:2:p:448-453
    DOI: 10.1016/j.ejor.2014.02.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714001283
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.02.013?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. D. S. Johnson & K. A. Niemi, 1983. "On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees," Mathematics of Operations Research, INFORMS, vol. 8(1), pages 1-14, February.
    2. Salah E. Elmaghraby & Jerzy Kamburowski, 1992. "The Analysis of Activity Networks Under Generalized Precedence Relations (GPRs)," Management Science, INFORMS, vol. 38(9), pages 1245-1263, September.
    3. Gerald G. Brown & W. Matthew Carlyle & Robert C. Harney & Eric M. Skroch & R. Kevin Wood, 2009. "Interdicting a Nuclear-Weapons Project," Operations Research, INFORMS, vol. 57(4), pages 866-877, August.
    4. Edieal Pinker & Joseph Szmerekovsky & Vera Tilson, 2013. "Technical Note---Managing a Secret Project," Operations Research, INFORMS, vol. 61(1), pages 65-72, February.
    5. Averbakh, Igor, 2010. "Nash equilibria in competitive project scheduling," European Journal of Operational Research, Elsevier, vol. 205(3), pages 552-556, September.
    6. You, Byungjun & Yamada, Takeo, 2007. "A pegging approach to the precedence-constrained knapsack problem," European Journal of Operational Research, Elsevier, vol. 183(2), pages 618-632, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Szmerekovsky, Joseph G. & Venkateshan, Prahalad & Simonson, Peter D., 2023. "Project scheduling under the threat of catastrophic disruption," European Journal of Operational Research, Elsevier, vol. 309(2), pages 784-794.
    2. Ben Hermans & Herbert Hamers & Roel Leus & Roy Lindelauf, 2019. "Timely exposure of a secret project: Which activities to monitor?," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(6), pages 451-468, September.
    3. Prabhjot Kaur & Kalpana Dahiya & Vanita Verma, 2021. "Time-cost trade-off analysis of a priority based assignment problem," OPSEARCH, Springer;Operational Research Society of India, vol. 58(2), pages 448-482, June.
    4. Hermans, Ben & Leus, Roel & Looy, Bart Van, 2023. "Deciding on scheduling, secrecy, and patenting during the new product development process: The relevance of project planning models," Omega, Elsevier, vol. 116(C).
    5. Fanrong Xie & Anuj Sharma & Zuoan Li, 2022. "An alternate approach to solve two-level priority based assignment problem," Computational Optimization and Applications, Springer, vol. 81(2), pages 613-656, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Aslan, Ayse & Ursavas, Evrim & Romeijnders, Ward, 2023. "A Precedence Constrained Knapsack Problem with Uncertain Item Weights for Personalized Learning Systems," Omega, Elsevier, vol. 115(C).
    2. George L. Vairaktarakis, 2003. "The Value of Resource Flexibility in the Resource-Constrained Job Assignment Problem," Management Science, INFORMS, vol. 49(6), pages 718-732, June.
    3. Nguyen, Di H. & Smith, J. Cole, 2022. "Network interdiction with asymmetric cost uncertainty," European Journal of Operational Research, Elsevier, vol. 297(1), pages 239-251.
    4. N. Samphaiboon & Y. Yamada, 2000. "Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem," Journal of Optimization Theory and Applications, Springer, vol. 105(3), pages 659-676, June.
    5. Sofie Coene & Frits C. R. Spieksma & Gerhard J. Woeginger, 2011. "Charlemagne's Challenge: The Periodic Latency Problem," Operations Research, INFORMS, vol. 59(3), pages 674-683, June.
    6. Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2000. "A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints," Management Science, INFORMS, vol. 46(10), pages 1365-1384, October.
    7. Karwowski, Jan & Mańdziuk, Jacek, 2019. "A Monte Carlo Tree Search approach to finding efficient patrolling schemes on graphs," European Journal of Operational Research, Elsevier, vol. 277(1), pages 255-268.
    8. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    9. Caramia, Massimiliano & Guerriero, Francesca, 2011. "A note on the modelling of project networks with time constraints," European Journal of Operational Research, Elsevier, vol. 211(3), pages 666-670, June.
    10. van de Leensel, R.L.J.M. & Flippo, O.E. & Koster, Arie M.C.A. & Kolen, A.W.J., 1996. "A dynamic programming algorithm for the local access network expansion problem," Research Memorandum 027, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    11. Ibrahim Kamel & Beizhong Chen, 2009. "A novel memory management scheme for residential gateways," Information Systems Frontiers, Springer, vol. 11(5), pages 491-500, November.
    12. W. Lambert & A. Newman, 2014. "Tailored Lagrangian Relaxation for the open pit block sequencing problem," Annals of Operations Research, Springer, vol. 222(1), pages 419-438, November.
    13. Bakker, Craig & Webster, Jennifer B. & Nowak, Kathleen E. & Chatterjee, Samrat & Perkins, Casey J. & Brigantic, Robert, 2020. "Multi-Game Modeling for Counter-Smuggling," Reliability Engineering and System Safety, Elsevier, vol. 200(C).
    14. Kameshwaran, S. & Narahari, Y. & Rosa, Charles H. & Kulkarni, Devadatta M. & Tew, Jeffrey D., 2007. "Multiattribute electronic procurement using goal programming," European Journal of Operational Research, Elsevier, vol. 179(2), pages 518-536, June.
    15. Lee, Kangbok & Leung, Joseph Y.-T. & Pinedo, Michael L., 2012. "Coordination mechanisms for parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 220(2), pages 305-313.
    16. Frank Gurski & Dominique Komander & Carolin Rehs, 2020. "Solutions for subset sum problems with special digraph constraints," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(2), pages 401-433, October.
    17. He, Zhengwen & Wang, Nengmin & Jia, Tao & Xu, Yu, 2009. "Simulated annealing and tabu search for multi-mode project payment scheduling," European Journal of Operational Research, Elsevier, vol. 198(3), pages 688-696, November.
    18. Simon Micheler & Yee Mey Goh & Niels Lohse, 2021. "A transformation of human operation approach to inform system design for automation," Journal of Intelligent Manufacturing, Springer, vol. 32(1), pages 201-220, January.
    19. Wiesemann, Wolfram & Kuhn, Daniel & Rustem, Berç, 2010. "Maximizing the net present value of a project under uncertainty," European Journal of Operational Research, Elsevier, vol. 202(2), pages 356-367, April.
    20. Kameshwaran, S. & Narahari, Y., 2009. "Nonconvex piecewise linear knapsack problems," European Journal of Operational Research, Elsevier, vol. 192(1), pages 56-68, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:237:y:2014:i:2:p:448-453. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.