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

Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs

Author

Listed:
  • Wan, Long
  • Mei, Jiajie
  • Du, Jiangze

Abstract

In this paper, we revisit a two-agent scheduling problem on a single machine with jobs of unit processing times. In this problem, we have two agents: agent A and agent B. Each agent has his/her own disjoint job set. The objective of agent A is to minimize the total weighted completion time, and the objective of agent B is to minimize the total weighted number of tardy jobs. The complexity of the decision version of the problem was proposed as open in Oron et al. (European Journal of Operational Research 244:86–99, 2015). We construct a reduction from a variant of Even-Odd Partition to show that this problem is NP-complete. Finally, we also propose a pseudo-polynomial algorithm and a dual FPTAS for the problem.

Suggested Citation

  • Wan, Long & Mei, Jiajie & Du, Jiangze, 2021. "Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 290(1), pages 26-35.
    • Handle: RePEc:eee:ejores:v:290:y:2021:i:1:p:26-35
    DOI: 10.1016/j.ejor.2020.07.064
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720306901
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.07.064?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. Jianzhong Du & Joseph Y.-T. Leung, 1990. "Minimizing Total Tardiness on One Machine is NP-Hard," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 483-495, August.
    2. Wan, Long & Yuan, Jinjiang & Wei, Lijun, 2016. "Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost," Applied Mathematics and Computation, Elsevier, vol. 273(C), pages 912-923.
    3. Gao, Yuan & Yuan, Jinjiang & Ng, C.T. & Cheng, T.C.E., 2019. "A further study on two-agent parallel-batch scheduling with release dates and deteriorating jobs to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 273(1), pages 74-81.
    4. Oron, Daniel & Shabtay, Dvir & Steiner, George, 2015. "Single machine scheduling with two competing agents and equal job processing times," European Journal of Operational Research, Elsevier, vol. 244(1), pages 86-99.
    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. N.R. Jennings & P. Faratin & A.R. Lomuscio & S. Parsons & M.J. Wooldridge & C. Sierra, 2001. "Automated Negotiation: Prospects, Methods and Challenges," Group Decision and Negotiation, Springer, vol. 10(2), pages 199-215, March.
    7. 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.
    8. 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.
    9. Shisheng Li & T.C.E. Cheng & C.T. Ng & Jinjiang Yuan, 2017. "Two‐agent scheduling on a single sequential and compatible batching machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 628-641, December.
    10. Cheng He & Joseph Y.-T. Leung, 2017. "Two-agent scheduling of time-dependent jobs," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 362-377, August.
    11. 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.
    12. 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.
    13. Tang, Lixin & Zhao, Xiaoli & Liu, Jiyin & Leung, Joseph Y.-T., 2017. "Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine," European Journal of Operational Research, Elsevier, vol. 263(2), pages 401-411.
    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. Chen, Ke & Cheng, T.C.E. & Huang, Hailiang & Ji, Min & Yao, Danli, 2023. "Single-machine scheduling with autonomous and induced learning to minimize total weighted number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 309(1), pages 24-34.
    2. Shi-Sheng Li & Ren-Xia Chen, 2023. "Competitive two-agent scheduling with release dates and preemption on a single machine," Journal of Scheduling, Springer, vol. 26(3), pages 227-249, June.
    3. 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.
    4. 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.

    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. 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.
    2. Shi-Sheng Li & Ren-Xia Chen, 2023. "Competitive two-agent scheduling with release dates and preemption on a single machine," Journal of Scheduling, Springer, vol. 26(3), pages 227-249, June.
    3. 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.
    4. 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).
    5. Geng, Zhichao & Yuan, Jinjiang, 2023. "Single-machine scheduling of multiple projects with controllable processing times," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1074-1090.
    6. 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.
    7. 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.
    8. 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.
    9. Gao, Yuan & Yuan, Jinjiang & Ng, C.T. & Cheng, T.C.E., 2019. "A further study on two-agent parallel-batch scheduling with release dates and deteriorating jobs to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 273(1), pages 74-81.
    10. Stanisław Gawiejnowicz, 2020. "A review of four decades of time-dependent scheduling: main results, new topics, and open problems," Journal of Scheduling, Springer, vol. 23(1), pages 3-47, February.
    11. 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.
    12. 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.
    13. 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.
    14. Wan, Long & Yuan, Jinjiang & Wei, Lijun, 2016. "Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost," Applied Mathematics and Computation, Elsevier, vol. 273(C), pages 912-923.
    15. Hermelin, Danny & Kubitza, Judith-Madeleine & Shabtay, Dvir & Talmon, Nimrod & Woeginger, Gerhard J., 2019. "Scheduling two agents on a single machine: A parameterized analysis of NP-hard problems," Omega, Elsevier, vol. 83(C), pages 275-286.
    16. Yuan Zhang & Jinjiang Yuan & Chi To Ng & Tai Chiu E. Cheng, 2021. "Pareto‐optimization of three‐agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 68(3), pages 378-393, April.
    17. 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.
    18. 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.
    19. Ren-Xia Chen & Shi-Sheng Li, 2019. "Two-agent single-machine scheduling with cumulative deterioration," 4OR, Springer, vol. 17(2), pages 201-219, June.
    20. Tang, Lixin & Zhao, Xiaoli & Liu, Jiyin & Leung, Joseph Y.-T., 2017. "Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine," European Journal of Operational Research, Elsevier, vol. 263(2), pages 401-411.

    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:290:y:2021:i:1:p:26-35. 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.