IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v343y2024i1d10.1007_s10479-024-06275-z.html
   My bibliography  Save this article

Two-agent proportionate flowshop scheduling with deadlines: polynomial-time optimization algorithms

Author

Listed:
  • Kuo-Ching Ying

    (National Taipei University of Technology)

  • Pourya Pourhejazy

    (UiT- The Arctic University of Norway)

  • Chuan-En Sung

    (National Taipei University of Technology
    Powertech Technology Inc.)

Abstract

Volatility in the supply chain of critical products, notably the vaccine shortage during the pandemic, influences livelihoods and may lead to significant delays and long waiting times. Considering the capital- and time-intensive nature of capacity expansion plans, strategic operational production decisions are required best to address the supply-demand mismatches given the limited production resources. This research article investigates the production scenarios where the demand of one agent must be completed within a specified due date, hereinafter referred to as the deadline, while minimizing the maximum or total completion time of another agent's demand. For this purpose, the Two-Agent Proportionate Flowshop Scheduling Problem with deadlines is introduced. Two polynomial-time optimization algorithms are developed to solve these optimization problems. This study will serve as a basis for further developing this practical yet understudied scheduling problem.

Suggested Citation

  • Kuo-Ching Ying & Pourya Pourhejazy & Chuan-En Sung, 2024. "Two-agent proportionate flowshop scheduling with deadlines: polynomial-time optimization algorithms," Annals of Operations Research, Springer, vol. 343(1), pages 543-558, December.
    • Handle: RePEc:spr:annopr:v:343:y:2024:i:1:d:10.1007_s10479-024-06275-z
    DOI: 10.1007/s10479-024-06275-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-024-06275-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-024-06275-z?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. Sergey Kovalev & Mikhail Y. Kovalyov & Gur Mosheiov & Enrique Gerstl, 2019. "Semi-V-shape property for two-machine no-wait proportionate flow shop problem with TADC criterion," International Journal of Production Research, Taylor & Francis Journals, vol. 57(2), pages 560-566, January.
    2. Jin Qian & Haiyan Han, 2022. "Improved algorithms for proportionate flow shop scheduling with due-window assignment," Annals of Operations Research, Springer, vol. 309(1), pages 249-258, February.
    3. Baruch Mor & Dana Shapira, 2019. "Improved algorithms for scheduling on proportionate flowshop with job-rejection," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 70(11), pages 1997-2003, November.
    4. C. T. Ng & T. C. E. Cheng & J. J. Yuan, 2006. "A note on the complexity of the problem of two-agent scheduling on a single machine," Journal of Combinatorial Optimization, Springer, vol. 12(4), pages 387-394, December.
    5. Allesandro Agnetis & Pitu B. Mirchandani & Dario Pacciarelli & Andrea Pacifici, 2004. "Scheduling Problems with Two Competing Agents," Operations Research, INFORMS, vol. 52(2), pages 229-242, April.
    6. Xinyu Sun & Xin-Na Geng & Tao Liu, 2020. "Due-window assignment scheduling in the proportionate flow shop setting," Annals of Operations Research, Springer, vol. 292(1), pages 113-131, September.
    7. Ren-Xia Chen & Shi-Sheng Li, 2021. "Proportionate Flow Shop Scheduling with Two Competing Agents to Minimize Weighted Late Work and Weighted Number of Late Jobs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 38(02), pages 1-19, April.
    8. Enrique Gerstl & Baruch Mor & Gur Mosheiov, 2019. "Scheduling on a proportionate flowshop to minimise total late work," International Journal of Production Research, Taylor & Francis Journals, vol. 57(2), pages 531-543, January.
    9. Yoav Ben-Yehoshua & Eyal Hariri & Gur Mosheiov, 2015. "A note on minimising total absolute deviation of job completion times on a two-machine no-wait proportionate flowshop," International Journal of Production Research, Taylor & Francis Journals, vol. 53(19), pages 5717-5724, October.
    10. B Mor & G Mosheiov, 2014. "Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(1), pages 151-157, January.
    11. Daniel Oron, 2019. "Batching and resource allocation decisions on an m-machine proportionate flowshop," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 70(9), pages 1571-1578, September.
    12. Dvir Shabtay & Daniel Oron, 2016. "Proportionate flow-shop scheduling with rejection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(5), pages 752-769, May.
    13. Koulamas, Christos & Kyparisis, George J., 2007. "Single-machine and two-machine flowshop scheduling with general learning functions," European Journal of Operational Research, Elsevier, vol. 178(2), pages 402-407, April.
    14. Baruch Mor & Gur Mosheiov & Dvir Shabtay, 2021. "Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates," Journal of Scheduling, Springer, vol. 24(6), pages 553-567, December.
    15. Joseph Y.-T. Leung & Michael Pinedo & Guohua Wan, 2010. "Competitive Two-Agent Scheduling and Its Applications," Operations Research, INFORMS, vol. 58(2), pages 458-469, April.
    16. S.S. Panwalkar & Christos Koulamas, 2015. "On equivalence between the proportionate flow shop and single‐machine scheduling problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(7), pages 595-603, October.
    17. Koulamas, Christos & Kyparisis, George J., 2009. "A note on the proportionate flow shop with a bottleneck machine," European Journal of Operational Research, Elsevier, vol. 193(2), pages 644-645, March.
    18. S.S. Panwalkar & Christos Koulamas, 2015. "Proportionate flow shop: New complexity results and models with due date assignment," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(2), pages 98-106, March.
    19. Baruch Mor & Gur Mosheiov, 2015. "Minimizing the number of early jobs on a proportionate flowshop," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(9), pages 1426-1429, September.
    20. Koulamas, Christos, 2020. "The proportionate flow shop total tardiness problem," European Journal of Operational Research, Elsevier, vol. 284(2), pages 439-444.
    21. Shi-Sheng Li & De-Liang Qian & Ren-Xia Chen, 2017. "Proportionate Flow Shop Scheduling with Rejection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(04), pages 1-13, August.
    22. Peng Si Ow, 1985. "Focused Scheduling in Proportionate Flowshops," Management Science, INFORMS, vol. 31(7), pages 852-869, July.
    23. Mor, Baruch & Mosheiov, Gur, 2016. "Minsum and minmax scheduling on a proportionate flowshop with common flow-allowance," European Journal of Operational Research, Elsevier, vol. 254(2), pages 360-370.
    24. S.S. Panwalkar & Milton L. Smith & Christos Koulamas, 2013. "Review of the ordered and proportionate flow shop scheduling research," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 46-55, February.
    Full references (including those not matched with items on IDEAS)

    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. S.S. Panwalkar & Christos Koulamas, 2015. "On equivalence between the proportionate flow shop and single‐machine scheduling problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(7), pages 595-603, October.
    2. Jin Qian & Haiyan Han, 2022. "Improved algorithms for proportionate flow shop scheduling with due-window assignment," Annals of Operations Research, Springer, vol. 309(1), pages 249-258, February.
    3. Abdennour Azerine & Mourad Boudhar & Djamal Rebaine, 2022. "A two-machine no-wait flow shop problem with two competing agents," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 168-199, January.
    4. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    5. Shi-Sheng Li & Jin-Jiang Yuan, 2020. "Single-machine scheduling with multi-agents to minimize total weighted late work," Journal of Scheduling, Springer, vol. 23(4), pages 497-512, August.
    6. Byung-Cheon Choi & Myoung-Ju Park, 2016. "An Ordered Flow Shop with Two Agents," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(05), pages 1-24, October.
    7. Shesh Narayan Sahu & Yuvraj Gajpal & Swapan Debbarma, 2018. "Two-agent-based single-machine scheduling with switchover time to minimize total weighted completion time and makespan objectives," Annals of Operations Research, Springer, vol. 269(1), pages 623-640, October.
    8. Ruyan He & Jinjiang Yuan, 2020. "Two-Agent Preemptive Pareto-Scheduling to Minimize Late Work and Other Criteria," Mathematics, MDPI, vol. 8(9), pages 1-18, September.
    9. Mosheiov, Gur & Oron, Daniel & Shabtay, Dvir, 2021. "Minimizing total late work on a single machine with generalized due-dates," European Journal of Operational Research, Elsevier, vol. 293(3), pages 837-846.
    10. Chen, Rubing & Geng, Zhichao & Lu, Lingfa & Yuan, Jinjiang & Zhang, Yuan, 2022. "Pareto-scheduling of two competing agents with their own equal processing times," European Journal of Operational Research, Elsevier, vol. 301(2), pages 414-431.
    11. Shang-Chia Liu & Jiahui Duan & Win-Chin Lin & Wen-Hsiang Wu & Jan-Yee Kung & Hau Chen & Chin-Chia Wu, 2018. "A Branch-and-Bound Algorithm for Two-Agent Scheduling with Learning Effect and Late Work Criterion," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-24, October.
    12. Rubing Chen & Jinjiang Yuan & Yuan Gao, 2019. "The complexity of CO-agent scheduling to minimize the total completion time and total number of tardy jobs," Journal of Scheduling, Springer, vol. 22(5), pages 581-593, October.
    13. Donatas Elvikis & Vincent T’kindt, 2014. "Two-agent scheduling on uniform parallel machines with min-max criteria," Annals of Operations Research, Springer, vol. 213(1), pages 79-94, February.
    14. Zhang Xingong & Wang Yong, 2017. "Two-agent scheduling problems on a single-machine to minimize the total weighted late work," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 945-955, April.
    15. S.S. Panwalkar & Milton L. Smith & Christos Koulamas, 2013. "Review of the ordered and proportionate flow shop scheduling research," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 46-55, February.
    16. Shi-Sheng Li & Ren-Xia Chen & Qi Feng, 2016. "Scheduling two job families on a single machine with two competitive agents," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 784-799, October.
    17. Du-Juan Wang & Yunqiang Yin & Shuenn-Ren Cheng & T.C.E. Cheng & Chin-Chia Wu, 2016. "Due date assignment and scheduling on a single machine with two competing agents," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1152-1169, February.
    18. Wenchang Luo & Lin Chen & Guochuan Zhang, 2012. "Approximation schemes for two-machine flow shop scheduling with two agents," Journal of Combinatorial Optimization, Springer, vol. 24(3), pages 229-239, October.
    19. Baruch Mor, 2023. "Single machine scheduling problems involving job-dependent step-deterioration dates and job rejection," Operational Research, Springer, vol. 23(1), pages 1-19, March.
    20. Ruyan He & Jinjiang Yuan & C. T. Ng & T. C. E. Cheng, 2021. "Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work," Journal of Combinatorial Optimization, Springer, vol. 41(2), pages 504-525, February.

    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:spr:annopr:v:343:y:2024:i:1:d:10.1007_s10479-024-06275-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.