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

Minimizing maximum cost for a single machine under uncertainty of processing times

Author

Listed:
  • Fridman, Ilia
  • Pesch, Erwin
  • Shafransky, Yakov

Abstract

One of the most known results in the machine scheduling is Lawler’s algorithm to minimize the maximum cost of jobs processed by a single machine subject to precedence constraints. We consider an uncertain version of the same min-max cost scheduling problem. The cost function of each job depends on the job completion time and on an additional generalized numerical parameter, which may be a tuple of parameters. For each job, both, its processing time and the additional parameter are uncertain, only intervals of possible values of these parameters are known.

Suggested Citation

  • Fridman, Ilia & Pesch, Erwin & Shafransky, Yakov, 2020. "Minimizing maximum cost for a single machine under uncertainty of processing times," European Journal of Operational Research, Elsevier, vol. 286(2), pages 444-457.
    • Handle: RePEc:eee:ejores:v:286:y:2020:i:2:p:444-457
    DOI: 10.1016/j.ejor.2020.03.052
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720302824
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.03.052?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Chanas, Stefan & Kasperski, Adam, 2003. "On two single machine scheduling problems with fuzzy processing times and fuzzy due dates," European Journal of Operational Research, Elsevier, vol. 147(2), pages 281-296, June.
    2. E. L. Lawler, 1973. "Optimal Sequencing of a Single Machine Subject to Precedence Constraints," Management Science, INFORMS, vol. 19(5), pages 544-546, January.
    3. Dimitris Bertsimas & Aurélie Thiele, 2006. "A Robust Optimization Approach to Inventory Theory," Operations Research, INFORMS, vol. 54(1), pages 150-168, February.
    4. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    5. Conde, Eduardo, 2012. "On a constant factor approximation for minmax regret problems using a symmetry point scenario," European Journal of Operational Research, Elsevier, vol. 219(2), pages 452-457.
    6. Laurent El Ghaoui & Maksim Oks & Francois Oustry, 2003. "Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach," Operations Research, INFORMS, vol. 51(4), pages 543-556, August.
    7. Nadia Brauner & Gerd Finke & Yakov Shafransky, 2017. "Lawler’s minmax cost problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 34(1), pages 31-46, July.
    8. Chassein, André & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2018. "On recoverable and two-stage robust selection problems with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 265(2), pages 423-436.
    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. Dung-Ying Lin & Tzu-Yun Huang, 2021. "A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem," Mathematics, MDPI, vol. 9(7), pages 1-20, April.
    2. Matthew Bold & Marc Goerigk, 2025. "Recoverable robust single machine scheduling with polyhedral uncertainty," Journal of Scheduling, Springer, vol. 28(3), pages 269-287, June.

    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. Sarhadi, Hassan & Naoum-Sawaya, Joe & Verma, Manish, 2020. "A robust optimization approach to locating and stockpiling marine oil-spill response facilities," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    2. Qiu, Ruozhen & Sun, Minghe & Lim, Yun Fong, 2017. "Optimizing (s, S) policies for multi-period inventory models with demand distribution uncertainty: Robust dynamic programing approaches," European Journal of Operational Research, Elsevier, vol. 261(3), pages 880-892.
    3. Maillet, Bertrand & Tokpavi, Sessi & Vaucher, Benoit, 2015. "Global minimum variance portfolio optimisation under some model risk: A robust regression-based approach," European Journal of Operational Research, Elsevier, vol. 244(1), pages 289-299.
    4. Jiang, Sheng-Long & Wang, Meihong & Bogle, I. David L., 2023. "Plant-wide byproduct gas distribution under uncertainty in iron and steel industry via quantile forecasting and robust optimization," Applied Energy, Elsevier, vol. 350(C).
    5. Metzker Soares, Paula & Thevenin, Simon & Adulyasak, Yossiri & Dolgui, Alexandre, 2024. "Adaptive robust optimization for lot-sizing under yield uncertainty," European Journal of Operational Research, Elsevier, vol. 313(2), pages 513-526.
    6. Walid Ben-Ameur & Adam Ouorou & Guanglei Wang & Mateusz Żotkiewicz, 2018. "Multipolar robust optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 395-434, December.
    7. Fernando Ordóñez & Nicolás E. Stier-Moses, 2010. "Wardrop Equilibria with Risk-Averse Users," Transportation Science, INFORMS, vol. 44(1), pages 63-86, February.
    8. Asimit, Alexandru V. & Bignozzi, Valeria & Cheung, Ka Chun & Hu, Junlei & Kim, Eun-Seok, 2017. "Robust and Pareto optimality of insurance contracts," European Journal of Operational Research, Elsevier, vol. 262(2), pages 720-732.
    9. Rubing Chen & Jinjiang Yuan, 2020. "Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices," 4OR, Springer, vol. 18(2), pages 177-196, June.
    10. Guanglei Wang & Hassan Hijazi, 2018. "Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches," Computational Optimization and Applications, Springer, vol. 71(2), pages 553-608, November.
    11. Ashrafi, Hedieh & Thiele, Aurélie C., 2021. "A study of robust portfolio optimization with European options using polyhedral uncertainty sets," Operations Research Perspectives, Elsevier, vol. 8(C).
    12. Jiang, Sheng-Long & Peng, Gongzhuang & Bogle, I. David L. & Zheng, Zhong, 2022. "Two-stage robust optimization approach for flexible oxygen distribution under uncertainty in integrated iron and steel plants," Applied Energy, Elsevier, vol. 306(PB).
    13. Viktoryia Buhayenko & Dick den Hertog, 2017. "Adjustable Robust Optimisation approach to optimise discounts for multi-period supply chain coordination under demand uncertainty," International Journal of Production Research, Taylor & Francis Journals, vol. 55(22), pages 6801-6823, November.
    14. Xie, Chen & Wang, Liangquan & Yang, Chaolin, 2021. "Robust inventory management with multiple supply sources," European Journal of Operational Research, Elsevier, vol. 295(2), pages 463-474.
    15. Zhi Chen & Melvyn Sim & Peng Xiong, 2020. "Robust Stochastic Optimization Made Easy with RSOME," Management Science, INFORMS, vol. 66(8), pages 3329-3339, August.
    16. Postek, K.S. & den Hertog, D. & Melenberg, B., 2015. "Computationally Tractable Counterparts of Distributionally Robust Constraints on Risk Measures (revision of CentER DP 2014-031)," Discussion Paper 2015-047, Tilburg University, Center for Economic Research.
    17. Juan Carlos Espinoza Garcia & Laurent Alfandari, 2018. "Robust location of new housing developments using a choice model," Annals of Operations Research, Springer, vol. 271(2), pages 527-550, December.
    18. Cleber D. Rocco & Reinaldo Morabito, 2016. "Robust optimisation approach applied to the analysis of production / logistics and crop planning in the tomato processing industry," International Journal of Production Research, Taylor & Francis Journals, vol. 54(19), pages 5842-5861, October.
    19. Henao, César Augusto & Ferrer, Juan Carlos & Muñoz, Juan Carlos & Vera, Jorge, 2016. "Multiskilling with closed chains in a service industry: A robust optimization approach," International Journal of Production Economics, Elsevier, vol. 179(C), pages 166-178.
    20. Seunghoon Lee & Yongju Cho & Minjae Ko, 2020. "Robust Optimization Model for R&D Project Selection under Uncertainty in the Automobile Industry," Sustainability, MDPI, vol. 12(23), pages 1-15, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:286:y:2020:i:2:p:444-457. 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.