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

Min–max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty

Author

Listed:
  • Choi, Byung-Cheon
  • Chung, Kwanghun

Abstract

We consider the min-max regret version of a single-machine scheduling problem to determine which jobs are processed by outsourcing under processing time uncertainty. The performance measure is expressed as the total cost for processing some jobs in-house and outsourcing the rest. Processing time uncertainty is described through two types of scenarios: either an interval scenario or a discrete scenario. The objective is to minimize the maximum deviation from optimality over all scenarios. We show that when the cost for in-house jobs is expressed as the makespan, the problem with an interval scenario is polynomially solvable, while the one with a discrete scenario is NP-hard. Thus, for the discrete scenario case, we develop a 2-approximation algorithm and investigate when the problem is polynomially solvable. Since the problem minimizing the total completion time as a performance measure for in-house jobs is known to be NP-hard for both scenarios, we consider the problem with a special structure for the processing time uncertainty and develop a polynomial-time algorithm for both scenarios.

Suggested Citation

  • Choi, Byung-Cheon & Chung, Kwanghun, 2016. "Min–max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty," European Journal of Operational Research, Elsevier, vol. 252(2), pages 367-375.
    • Handle: RePEc:eee:ejores:v:252:y:2016:i:2:p:367-375
    DOI: 10.1016/j.ejor.2015.12.046
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715011856
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.12.046?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. Jian Yang & Gang Yu, 2002. "On the Robust Single Machine Scheduling Problem," Journal of Combinatorial Optimization, Springer, vol. 6(1), pages 17-33, March.
    2. Qi, Xiangtong, 2011. "Outsourcing and production scheduling for a two-stage flow shop," International Journal of Production Economics, Elsevier, vol. 129(1), pages 43-50, January.
    3. Kasperski, Adam & Kurpisz, Adam & Zieliński, Paweł, 2012. "Approximating a two-machine flow shop scheduling under discrete scenario uncertainty," European Journal of Operational Research, Elsevier, vol. 217(1), pages 36-43.
    4. Chung, Dae-Young & Choi, Byung-Cheon, 2013. "Outsourcing and scheduling for two-machine ordered flow shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 226(1), pages 46-52.
    5. Richard L. Daniels & Panagiotis Kouvelis, 1995. "Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production," Management Science, INFORMS, vol. 41(2), pages 363-376, February.
    6. Chung, Daeyoung & Lee, Kichang & Shin, Kitae & Park, Jinwoo, 2005. "A new approach to job shop scheduling problems with due date constraints considering operation subcontracts," International Journal of Production Economics, Elsevier, vol. 98(2), pages 238-250, November.
    7. Gérard P. Cachon & Patrick T. Harker, 2002. "Competition and Outsourcing with Scale Economies," Management Science, INFORMS, vol. 48(10), pages 1314-1333, October.
    8. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2007. "Approximation of min-max and min-max regret versions of some combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 179(2), pages 281-290, June.
    9. Wang, J.-B. & Ng, C.T. & Cheng, T.C.E. & Liu, L.L., 2008. "Single-machine scheduling with a time-dependent learning effect," International Journal of Production Economics, Elsevier, vol. 111(2), pages 802-811, February.
    10. R. G. Vickson, 1980. "Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine," Operations Research, INFORMS, vol. 28(5), pages 1155-1167, October.
    11. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    12. Lee, Ik Sun & Sung, C.S., 2008. "Single machine scheduling with outsourcing allowed," International Journal of Production Economics, Elsevier, vol. 111(2), pages 623-634, February.
    13. Choi, Byung-Cheon & Chung, Jibok, 2011. "Two-machine flow shop scheduling problem with an outsourcing option," European Journal of Operational Research, Elsevier, vol. 213(1), pages 66-72, August.
    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. Lingfa Lu & Liqi Zhang & Jie Zhang & Lili Zuo, 2020. "Single Machine Scheduling with Outsourcing Under Different Fill Rates or Quantity Discount Rates," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 37(01), pages 1-15, January.
    2. Zhong, Xueling & Fan, Jie & Ou, Jinwen, 2022. "Coordinated scheduling of the outsourcing, in-house production and distribution operations," European Journal of Operational Research, Elsevier, vol. 302(2), pages 427-437.
    3. Lingfa Lu & Liqi Zhang & Jinwen Ou, 2021. "In-house production and outsourcing under different discount schemes on the total outsourcing cost," Annals of Operations Research, Springer, vol. 298(1), pages 361-374, March.
    4. Schroeder, Pascal & Kacem, Imed, 2020. "Competitive difference analysis of the cash management problem with uncertain demands," European Journal of Operational Research, Elsevier, vol. 283(3), pages 1183-1192.
    5. Seddik, Yasmina & Hanzálek, Zdenek, 2017. "Match-up scheduling of mixed-criticality jobs: Maximizing the probability of jobs execution," European Journal of Operational Research, Elsevier, vol. 262(1), pages 46-59.

    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. Thürer, Matthias & Stevenson, Mark & Qu, Ting & Godinho Filho, Moacir, 2014. "The design of simple subcontracting rules for make-to-order shops: An assessment by simulation," European Journal of Operational Research, Elsevier, vol. 239(3), pages 854-864.
    2. Zhong, Xueling & Fan, Jie & Ou, Jinwen, 2022. "Coordinated scheduling of the outsourcing, in-house production and distribution operations," European Journal of Operational Research, Elsevier, vol. 302(2), pages 427-437.
    3. Chung, Dae-Young & Choi, Byung-Cheon, 2013. "Outsourcing and scheduling for two-machine ordered flow shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 226(1), pages 46-52.
    4. Lingfa Lu & Liqi Zhang & Jinwen Ou, 2021. "In-house production and outsourcing under different discount schemes on the total outsourcing cost," Annals of Operations Research, Springer, vol. 298(1), pages 361-374, March.
    5. Choi, Byung-Cheon & Chung, Jibok, 2011. "Two-machine flow shop scheduling problem with an outsourcing option," European Journal of Operational Research, Elsevier, vol. 213(1), pages 66-72, August.
    6. Lee, Kangbok & Choi, Byung-Cheon, 2011. "Two-stage production scheduling with an outsourcing option," European Journal of Operational Research, Elsevier, vol. 213(3), pages 489-497, September.
    7. Kasperski, Adam & Kurpisz, Adam & Zieliński, Paweł, 2012. "Approximating a two-machine flow shop scheduling under discrete scenario uncertainty," European Journal of Operational Research, Elsevier, vol. 217(1), pages 36-43.
    8. Shabtay, Dvir & Gilenson, Miri, 2023. "A state-of-the-art survey on multi-scenario scheduling," European Journal of Operational Research, Elsevier, vol. 310(1), pages 3-23.
    9. Alireza Amirteimoori & Simin Masrouri, 2021. "DEA-based competition strategy in the presence of undesirable products: An application to paper mills," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 5-21.
    10. Adam Kasperski & Paweł Zieliński, 2019. "Risk-averse single machine scheduling: complexity and approximation," Journal of Scheduling, Springer, vol. 22(5), pages 567-580, October.
    11. Miri Gilenson & Dvir Shabtay & Liron Yedidsion & Rohit Malshe, 2021. "Scheduling in multi-scenario environment with an agreeable condition on job processing times," Annals of Operations Research, Springer, vol. 307(1), pages 153-173, December.
    12. Gang Xuan & Win-Chin Lin & Shuenn-Ren Cheng & Wei-Lun Shen & Po-An Pan & Chih-Ling Kuo & Chin-Chia Wu, 2022. "A Robust Single-Machine Scheduling Problem with Two Job Parameter Scenarios," Mathematics, MDPI, vol. 10(13), pages 1-17, June.
    13. Li, Gang & Wang, Xiao-Yuan & Wang, Ji-Bo & Sun, Lin-Yan, 2013. "Worst case analysis of flow shop scheduling problems with a time-dependent learning effect," International Journal of Production Economics, Elsevier, vol. 142(1), pages 98-104.
    14. Silva, Marco & Poss, Michael & Maculan, Nelson, 2020. "Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty," European Journal of Operational Research, Elsevier, vol. 283(1), pages 70-82.
    15. Fabrice Talla Nobibon & Roel Leus, 2014. "Complexity Results and Exact Algorithms for Robust Knapsack Problems," Journal of Optimization Theory and Applications, Springer, vol. 161(2), pages 533-552, May.
    16. Pei, Zhi & Lu, Haimin & Jin, Qingwei & Zhang, Lianmin, 2022. "Target-based distributionally robust optimization for single machine scheduling," European Journal of Operational Research, Elsevier, vol. 299(2), pages 420-431.
    17. Subhash C. Sarin & Balaji Nagarajan & Sanjay Jain & Lingrui Liao, 2009. "Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability," Journal of Combinatorial Optimization, Springer, vol. 17(4), pages 400-416, May.
    18. Lung-Yu Li & Jian-You Xu & Shuenn-Ren Cheng & Xingong Zhang & Win-Chin Lin & Jia-Cheng Lin & Zong-Lin Wu & Chin-Chia Wu, 2022. "A Genetic Hyper-Heuristic for an Order Scheduling Problem with Two Scenario-Dependent Parameters in a Parallel-Machine Environment," Mathematics, MDPI, vol. 10(21), pages 1-22, November.
    19. Mina Roohnavazfar & Daniele Manerba & Lohic Fotio Tiotsop & Seyed Hamid Reza Pasandideh & Roberto Tadei, 2021. "Stochastic single machine scheduling problem as a multi-stage dynamic random decision process," Computational Management Science, Springer, vol. 18(3), pages 267-297, July.
    20. Qi, Xiangtong, 2011. "Outsourcing and production scheduling for a two-stage flow shop," International Journal of Production Economics, Elsevier, vol. 129(1), pages 43-50, 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:252:y:2016:i:2:p:367-375. 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.