IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v33y2017i4d10.1007_s10878-016-0049-1.html
   My bibliography  Save this article

A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance

Author

Listed:
  • Baruch Mor

    (Ariel University)

  • Gur Mosheiov

    (The Hebrew University)

Abstract

We study a single-machine scheduling model combining two competing agents and due-date assignment. The basic setting involves two agents who need to process their own sets of jobs, and compete on the use of a common processor. Our goal is to find the joint schedule that minimizes the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. The scheduling measure considered in this paper is minimum total (earliness, tardiness and due-date) cost, based on common flow allowance, i.e., due-dates are defined as linear functions of the job processing times. We introduce a simple polynomial time solution for this problem (linear in the number of jobs), as well as to its extension to a multi-agent setting. We further extend the model to that of a due-window assignment based on common flow allowance.

Suggested Citation

  • Baruch Mor & Gur Mosheiov, 2017. "A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance," Journal of Combinatorial Optimization, Springer, vol. 33(4), pages 1454-1468, May.
    • Handle: RePEc:spr:jcomop:v:33:y:2017:i:4:d:10.1007_s10878-016-0049-1
    DOI: 10.1007/s10878-016-0049-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-016-0049-1
    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/s10878-016-0049-1?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. 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.
    2. Alan Washburn & Moshe Kress, 2009. "Search," International Series in Operations Research & Management Science, in: Combat Modeling, chapter 0, pages 133-160, Springer.
    3. Mosheiov, Gur & Oron, Daniel, 2007. "Minmax scheduling with job-classes and earliness-tardiness costs," European Journal of Operational Research, Elsevier, vol. 177(1), pages 612-622, February.
    4. Mor, Baruch & Mosheiov, Gur, 2010. "Scheduling problems with two competing agents to minimize minmax and minsum earliness measures," European Journal of Operational Research, Elsevier, vol. 206(3), pages 540-546, November.
    5. 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.
    6. Gordon, Valery & Proth, Jean-Marie & Chu, Chengbin, 2002. "A survey of the state-of-the-art of common due date assignment and scheduling research," European Journal of Operational Research, Elsevier, vol. 139(1), pages 1-25, May.
    7. S Gawiejnowicz & W-C Lee & C-L Lin & C-C Wu, 2011. "Single-machine scheduling of proportionally deteriorating jobs by two agents," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(11), pages 1983-1991, November.
    8. 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.
    9. Dvir Shabtay & George Steiner, 2007. "Optimal Due Date Assignment and Resource Allocation to Minimize the Weighted Number of Tardy Jobs on a Single Machine," Manufacturing & Service Operations Management, INFORMS, vol. 9(3), pages 332-350, March.
    10. Alessandro Agnetis & Dario Pacciarelli & Andrea Pacifici, 2007. "Multi-agent single machine scheduling," Annals of Operations Research, Springer, vol. 150(1), pages 3-15, March.
    11. 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.
    12. Kejun Zhao & Xiwen Lu, 2016. "Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan," Journal of Combinatorial Optimization, Springer, vol. 31(1), pages 260-278, January.
    13. Mor, Baruch & Mosheiov, Gur, 2011. "Single machine batch scheduling with two competing agents to minimize total flowtime," European Journal of Operational Research, Elsevier, vol. 215(3), pages 524-531, December.
    14. Mosheiov, Gur & Sarig, Assaf, 2009. "Due-date assignment on uniform machines," European Journal of Operational Research, Elsevier, vol. 193(1), pages 49-58, February.
    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. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    2. Long Zhang & Yuzhong Zhang & Qingguo Bai, 0. "An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-13.
    3. Yunqiang Yin & Yongjian Yang & Dujuan Wang & T.C.E. Cheng & Chin‐Chia Wu, 2018. "Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(5), pages 393-409, August.
    4. Long Zhang & Yuzhong Zhang & Qingguo Bai, 2019. "Two-stage medical supply chain scheduling with an assignable common due window and shelf life," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 319-329, January.
    5. Dvir Shabtay, 2023. "A new perspective on single-machine scheduling problems with late work related criteria," Annals of Operations Research, Springer, vol. 322(2), pages 947-966, March.
    6. Baruch Mor, 2022. "Minmax common flow-allowance problems with convex resource allocation and position-dependent workloads," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 79-97, January.
    7. Baruch Mor & Gur Mosheiov, 2021. "A note on the single machine CON and CONW problems with lot scheduling," Journal of Combinatorial Optimization, Springer, vol. 42(2), pages 327-338, August.
    8. Shabtay, Dvir & Mosheiov, Gur & Oron, Daniel, 2022. "Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work," European Journal of Operational Research, Elsevier, vol. 303(1), pages 66-77.
    9. Li-Han Zhang & Dan-Yang Lv & Ji-Bo Wang, 2023. "Two-Agent Slack Due-Date Assignment Scheduling with Resource Allocations and Deteriorating Jobs," Mathematics, MDPI, vol. 11(12), pages 1-12, June.
    10. Byung-Cheon Choi & Myoung-Ju Park, 2020. "Scheduling two projects with controllable processing times in a single-machine environment," Journal of Scheduling, Springer, vol. 23(5), pages 619-628, October.
    11. Long Zhang & Yuzhong Zhang & Qingguo Bai, 2022. "An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2167-2179, November.

    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. 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.
    2. Byung-Gyoo Kim & Byung-Cheon Choi & Myoung-Ju Park, 2017. "Two-Machine and Two-Agent Flow Shop with Special Processing Times Structures," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(04), pages 1-17, August.
    3. Perez-Gonzalez, Paz & Framinan, Jose M., 2014. "A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 1-16.
    4. 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.
    5. 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.
    6. 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.
    7. Fan, B.Q. & Cheng, T.C.E., 2016. "Two-agent scheduling in a flowshop," European Journal of Operational Research, Elsevier, vol. 252(2), pages 376-384.
    8. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    9. Koulamas, Christos, 2015. "A note on scheduling problems with competing agents and earliness minimization objectives," European Journal of Operational Research, Elsevier, vol. 245(3), pages 875-876.
    10. Ren-Xia Chen & Shi-Sheng Li, 2019. "Two-agent single-machine scheduling with cumulative deterioration," 4OR, Springer, vol. 17(2), pages 201-219, June.
    11. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    12. Enrique Gerstl & Baruch Mor & Gur Mosheiov, 2017. "Scheduling with two competing agents to minimize total weighted earliness," Annals of Operations Research, Springer, vol. 253(1), pages 227-245, June.
    13. Jun Pei & Jinling Wei & Baoyu Liao & Xinbao Liu & Panos M. Pardalos, 2020. "Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent," Annals of Operations Research, Springer, vol. 294(1), pages 191-223, November.
    14. Yunqiang Yin & T. C. E. Cheng & Du-Juan Wang & Chin-Chia Wu, 2017. "Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs," Journal of Scheduling, Springer, vol. 20(4), pages 313-335, August.
    15. Zhang, Xingong, 2021. "Two competitive agents to minimize the weighted total late work and the total completion time," Applied Mathematics and Computation, Elsevier, vol. 406(C).
    16. Manzhan Gu & Jinwei Gu & Xiwen Lu, 2018. "An algorithm for multi-agent scheduling to minimize the makespan on m parallel machines," Journal of Scheduling, Springer, vol. 21(5), pages 483-492, October.
    17. 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.
    18. Cheng, Shuenn-Ren, 2014. "Some new problems on two-agent scheduling to minimize the earliness costs," International Journal of Production Economics, Elsevier, vol. 156(C), pages 24-30.
    19. 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.
    20. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.

    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:jcomop:v:33:y:2017:i:4:d:10.1007_s10878-016-0049-1. 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.