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

A note on the single machine scheduling to minimize the number of tardy jobs with deadlines

Author

Listed:
  • He, Cheng
  • Lin, Yixun
  • Yuan, Jinjiang

Abstract

It is known that the single machine scheduling problem of minimizing the number of tardy jobs is polynomially solvable. However, it becomes NP-hard if each job has a deadline. Recently, Huo et al. solved some special cases by a backwards scheduling approach. In this note we present a dual approach--forwards greedy algorithms which may have better running time. For example, in the case that the due dates, deadlines, and processing times are agreeable, the running time of the backwards scheduling algorithm is O(n2), while that of the forwards algorithm is O(nlogn).

Suggested Citation

  • He, Cheng & Lin, Yixun & Yuan, Jinjiang, 2010. "A note on the single machine scheduling to minimize the number of tardy jobs with deadlines," European Journal of Operational Research, Elsevier, vol. 201(3), pages 966-970, March.
    • Handle: RePEc:eee:ejores:v:201:y:2010:i:3:p:966-970
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00345-2
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Burkard, Rainer E., 2007. "Monge properties, discrete convexity and applications," European Journal of Operational Research, Elsevier, vol. 176(1), pages 1-14, January.
    2. Lin, Yixun & Wang, Xiumei, 2007. "Necessary and sufficient conditions of optimality for some classical scheduling problems," European Journal of Operational Research, Elsevier, vol. 176(2), pages 809-818, January.
    3. Huo, Yumei & Leung, Joseph Y.-T. & Zhao, Hairong, 2007. "Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness," European Journal of Operational Research, Elsevier, vol. 177(1), pages 116-134, 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. Cheng He & Hao Lin, 2016. "Hierarchical optimization with double due dates on an unbounded parallel-batching machine to minimize maximum lateness," 4OR, Springer, vol. 14(2), pages 153-164, June.
    2. 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.

    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. Máté Hireš & Monika Molnárová & Peter Drotár, 2020. "Robustness of Interval Monge Matrices in Fuzzy Algebra," Mathematics, MDPI, vol. 8(4), pages 1-16, April.
    2. 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.
    3. Alexander S. Estes & Michael O. Ball, 2021. "Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 785-807, May.
    4. Akamatsu, Takashi & Wada, Kentaro & Iryo, Takamasa & Hayashi, Shunsuke, 2021. "A new look at departure time choice equilibrium models with heterogeneous users," Transportation Research Part B: Methodological, Elsevier, vol. 148(C), pages 152-182.
    5. Osawa, Minoru & Fu, Haoran & Akamatsu, Takashi, 2018. "First-best dynamic assignment of commuters with endogenous heterogeneities in a corridor network," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 811-831.
    6. F. Javier Martinez de Albeniz & Carles Rafels, 2012. "Monge assignment games," Working Papers in Economics 282, Universitat de Barcelona. Espai de Recerca en Economia.
    7. Qi Feng & Chengzhang Li & Mengshi Lu & Jeyaveerasingam George Shanthikumar, 2022. "Dynamic Substitution for Selling Multiple Products under Supply and Demand Uncertainties," Production and Operations Management, Production and Operations Management Society, vol. 31(4), pages 1645-1662, April.
    8. Yakov Shafransky & Viktor Shinkarevich, 2020. "On the complexity of constructing a minmax regret solution for the two-machine flow shop problem under the interval uncertainty," Journal of Scheduling, Springer, vol. 23(6), pages 745-749, December.
    9. Akamatsu, Takashi & Wada, Kentaro & Iryo, Takamasa & Hayashi, Shunsuke, 2018. "Departure time choice equilibrium and optimal transport problems," MPRA Paper 90361, University Library of Munich, Germany.
    10. Della Croce, Federico & T’kindt, Vincent & Ploton, Olivier, 2021. "Parallel machine scheduling with minimum number of tardy jobs: Approximation and exponential algorithms," Applied Mathematics and Computation, Elsevier, vol. 397(C).
    11. Tseytlin, Yulia & Heese, H. Sebastian, 2023. "Inventory allocation with full downward substitution and monotone cost differences," European Journal of Operational Research, Elsevier, vol. 307(1), pages 130-139.
    12. Marjan Akker & Han Hoogeveen & Judith Stoef, 2018. "Combining two-stage stochastic programming and recoverable robustness to minimize the number of late jobs in the case of uncertain processing times," Journal of Scheduling, Springer, vol. 21(6), pages 607-617, December.
    13. Andreas C. Nearchou, 2018. "Multicriteria scheduling optimization using an elitist multiobjective population heuristic: the h-NSDE algorithm," Journal of Heuristics, Springer, vol. 24(6), pages 817-851, December.
    14. Peter Brucker & Natalia V. Shakhlevich, 2016. "Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines," Journal of Scheduling, Springer, vol. 19(6), pages 659-685, December.
    15. Tseytlin, Yulia & Heese, H. Sebastian, 2019. "Allocation under a general substitution structure," European Journal of Operational Research, Elsevier, vol. 277(2), pages 492-506.

    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:201:y:2010:i:3:p:966-970. 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.