IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i4p1013-d1070715.html
   My bibliography  Save this article

Scheduling of Jobs with Multiple Weights on a Single Machine for Minimizing the Total Weighted Number of Tardy Jobs

Author

Listed:
  • Shuen Guo

    (School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China)

  • Hao Lang

    (Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong SAR, China)

  • Hanxiang Zhang

    (Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong SAR, China)

Abstract

We consider the scheduling of jobs with multiple weights on a single machine for minimizing the total weighted number of tardy jobs. In this setting, each job has m weights (or equivalently, the jobs have m weighting vectors), and thus we have m criteria, each of which is to minimize the total weighted number of tardy jobs under a corresponding weighting vector of the jobs. For this scheduling model, the feasibility problem aims to find a feasible schedule such that each criterion is upper bounded by its threshold value, and the Pareto scheduling problem aims to find all the Pareto-optimal points and for each one a corresponding Pareto-optimal schedule. Although the two problems have not been studied before, it is implied in the literature that both of them are unary NP-hard when m is an arbitrary number. We show in this paper that, in the case where m is a fixed number, the two problems are solvable in pseudo-polynomial time, the feasibility problem admits a dual-fully polynomial-time approximation scheme, and the Pareto-scheduling problem admits a fully polynomial-time approximation scheme.

Suggested Citation

  • Shuen Guo & Hao Lang & Hanxiang Zhang, 2023. "Scheduling of Jobs with Multiple Weights on a Single Machine for Minimizing the Total Weighted Number of Tardy Jobs," Mathematics, MDPI, vol. 11(4), pages 1-19, February.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:4:p:1013-:d:1070715
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/4/1013/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/4/1013/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. E. L. Lawler & J. M. Moore, 1969. "A Functional Equation and its Application to Resource Allocation and Sequencing Problems," Management Science, INFORMS, vol. 16(1), pages 77-84, September.
    2. Yi-Chun Wang & Si-Han Wang & Ji-Bo Wang, 2023. "Resource Allocation Scheduling with Position-Dependent Weights and Generalized Earliness–Tardiness Cost," Mathematics, MDPI, vol. 11(1), pages 1-11, January.
    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. Jinjiang Yuan, 2017. "Unary NP-hardness of minimizing the number of tardy jobs with deadlines," Journal of Scheduling, Springer, vol. 20(2), pages 211-218, April.
    5. 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.
    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. Adrian Marius Deaconu & Daniel Tudor Cotfas & Petru Adrian Cotfas, 2023. "Advanced Optimization Methods and Applications," Mathematics, MDPI, vol. 11(9), pages 1-7, May.

    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. Rubing Chen & Jinjiang Yuan, 2020. "Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices," 4OR, Springer, vol. 18(2), pages 177-196, June.
    3. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    4. 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.
    5. 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.
    6. 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.
    7. Shi-Sheng Li & Ren-Xia Chen, 2022. "Minimizing total weighted late work on a single-machine with non-availability intervals," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1330-1355, September.
    8. Shabtay, Dvir & Steiner, George & Zhang, Rui, 2016. "Optimal coordination of resource allocation, due date assignment and scheduling decisions," Omega, Elsevier, vol. 65(C), pages 41-54.
    9. Prabuddha De & Jay B. Ghosh & Charles E. Wells, 1994. "Due‐date assignment and early/tardy scheduling on identical parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(1), pages 17-32, February.
    10. Willem E. de Paepe & Jan Karel Lenstra & Jiri Sgall & René A. Sitters & Leen Stougie, 2004. "Computer-Aided Complexity Classification of Dial-a-Ride Problems," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 120-132, May.
    11. Dunstall, Simon & Wirth, Andrew, 2005. "A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines," European Journal of Operational Research, Elsevier, vol. 167(2), pages 283-296, December.
    12. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    13. Huynh Tuong, Nguyen & Soukhal, Ameur & Billaut, Jean-Charles, 2010. "A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines," European Journal of Operational Research, Elsevier, vol. 202(3), pages 646-653, May.
    14. Azizoglu, Meral & Kirca, Omer, 1999. "On the minimization of total weighted flow time with identical and uniform parallel machines," European Journal of Operational Research, Elsevier, vol. 113(1), pages 91-100, February.
    15. Daniel Kowalczyk & Roel Leus, 2018. "A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 768-782, November.
    16. Cai, X. & Lum, V. Y. S. & Chan, J. M. T., 1997. "Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties," European Journal of Operational Research, Elsevier, vol. 98(1), pages 154-168, April.
    17. Reha Uzsoy & Chung‐Yee Lee & Louis A. Martin‐Vega, 1992. "Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(3), pages 369-388, April.
    18. Tian, Z. J. & Ng, C. T. & Cheng, T. C. E., 2005. "On the single machine total tardiness problem," European Journal of Operational Research, Elsevier, vol. 165(3), pages 843-846, September.
    19. Zhi-Long Chen & Nicholas G. Hall, 2010. "The Coordination of Pricing and Scheduling Decisions," Manufacturing & Service Operations Management, INFORMS, vol. 12(1), pages 77-92, April.
    20. Rabia Nessah & Chengbin Chu, 2010. "Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods," Annals of Operations Research, Springer, vol. 181(1), pages 359-375, December.

    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:gam:jmathe:v:11:y:2023:i:4:p:1013-:d:1070715. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.