IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v273y2016icp912-923.html
   My bibliography  Save this article

Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost

Author

Listed:
  • Wan, Long
  • Yuan, Jinjiang
  • Wei, Lijun

Abstract

This paper investigates the Pareto optimization scheduling problem on a single machine with two competing agents A and B in which agent A wants to minimize the number of tardy A-jobs and agent B wants to minimize the maximum cost of B-jobs. In the literature, the constrained optimization problem of minimizing the number of tardy A-jobs under the restriction that the maximum cost of B-jobs is bounded is solved in polynomial time. This implies that the corresponding Pareto optimization scheduling problem can be solved in a weakly polynomial time. In this paper, by presenting a new algorithm for the constrained optimization problem, we provide a strongly polynomial-time algorithm for the corresponding Pareto optimization scheduling problem. Experimentation results show that the proposed algorithm for the considered problem is efficient.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:apmaco:v:273:y:2016:i:c:p:912-923
    DOI: 10.1016/j.amc.2015.10.059
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300315014101
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2015.10.059?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. Hoogeveen, Han, 2005. "Multicriteria scheduling," European Journal of Operational Research, Elsevier, vol. 167(3), pages 592-623, December.
    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. 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.
    4. 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.
    5. Yuan, Jinjiang & Lin, Yixun, 2005. "Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria," European Journal of Operational Research, Elsevier, vol. 164(3), pages 851-855, August.
    6. Cheng, T.C.E. & Ng, C.T. & Yuan, J.J., 2008. "Multi-agent scheduling on a single machine with max-form criteria," European Journal of Operational Research, Elsevier, vol. 188(2), pages 603-609, July.
    7. J. Michael Moore, 1968. "An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs," Management Science, INFORMS, vol. 15(1), pages 102-109, September.
    8. 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.
    9. Van Wassenhove, Luc N. & Gelders, Ludo F., 1980. "Solving a bicriterion scheduling problem," European Journal of Operational Research, Elsevier, vol. 4(1), pages 42-48, January.
    10. 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.
    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, 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. Yuan Zhang & Zhichao Geng & Jinjiang Yuan, 2020. "Two-Agent Pareto-Scheduling of Minimizing Total Weighted Completion Time and Total Weighted Late Work," Mathematics, MDPI, vol. 8(11), pages 1-17, November.
    3. Xiaoling Cao & Wen-Hsing Wu & Wen-Hung Wu & Chin-Chia Wu, 2018. "Some two-agent single-machine scheduling problems to minimize minmax and minsum of completion times," Operational Research, Springer, vol. 18(2), pages 293-314, July.
    4. 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.
    5. 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.
    6. 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.
    7. 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.

    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. 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.
    2. 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.
    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. 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.
    5. 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.
    6. Ren-Xia Chen & Shi-Sheng Li, 2019. "Two-agent single-machine scheduling with cumulative deterioration," 4OR, Springer, vol. 17(2), pages 201-219, June.
    7. 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.
    8. Chen, Rubing & Yuan, Jinjiang & Ng, C.T. & Cheng, T.C.E., 2021. "Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion," European Journal of Operational Research, Elsevier, vol. 293(1), pages 79-92.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. Yaodong Ni & Zhaojun Zhao, 2017. "Two-agent scheduling problem under fuzzy environment," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 739-748, March.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. 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).
    20. 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.

    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:apmaco:v:273:y:2016:i:c:p:912-923. 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: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.