Skip to main content
SpringerLink
Log in

New constructive heuristics for the total weighted tardiness problem

  • Technical Note
  • Published:
Journal of the Operational Research Society

Abstract

This note considers the single-machine total weighted tardiness problem. Three new heuristic algorithms are suggested and compared with other competing heuristics from the literature, such as Apparent Tardiness Cost, Weighted Covert and Weighted Modified Due Date. The experimental tests show that the suggested heuristic algorithms outperform the existing heuristics.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abdul-Razaq TS, Potts CN and van Wassenhove LN (1990). A survey of algorithms for the single machine total weighted tardiness scheduling problem . Discrete Appl Math 26: 235–253.

    Article  Google Scholar 

  • Adler LN, Fraiman M, Kobacker E, Pinedo M and Plotnitcoff JC (1993). Wu TP. BPSS: A scheduling system for the packaging industry . Opns Res 41: 641–648.

    Article  Google Scholar 

  • Avci S, Akturk MS and Storer RH (2003). A problem space algorithm for single machine weighted tardiness problems . IIE T 35: 479–486.

    Article  Google Scholar 

  • Baker KR and Bertrand MB (1983). A dynamic priority rule for scheduling against due-dates . J Opns Mngt 3: 37–42.

    Google Scholar 

  • Crauwels HAJ, Potts CN and van Wassenhove LN (1998). Local search heuristics for the single machine total weighted tardiness scheduling problem . Informs J Comput 10: 341–350.

    Article  Google Scholar 

  • Emmons H (1969). One-machine sequencing to minimize certain functions of job tardiness . Opns Res 17: 701–705.

    Article  Google Scholar 

  • Huegler PA and Vasko FJ (1997). A performance comparison of heuristics for the total weighted tardiness problem . Comput IE 32: 753–767.

    Google Scholar 

  • Kanet JJ and Li X (2004). A weighted modified due date rule for sequencing to minimize weighted tardiness . J Sched 7: 261–276.

    Article  Google Scholar 

  • Koulamas CP (1994). The total tardiness scheduling problem: Review and extensions . Opns Research 42: 1025–1041.

    Article  Google Scholar 

  • Lenstra JK, Rinnoy Kan AHG and Brucker P (1977). Complexity of machine scheduling problems . Ann Discrete Math 1: 343–362.

    Article  Google Scholar 

  • Mason SJ, Fowler JW and Carlyle WM (2002). A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops . J Sched 5: 247–262.

    Article  Google Scholar 

  • Morton TE and Pentico DW (1993). Heuristic Scheduling Systems with Applications to Production and Project Management . John Wiley & Sons: New York.

    Google Scholar 

  • Morton TE, Rachamadugu, RM and Vepsalainen A (1984). Accurate myopic heuristics for tardiness scheduling. GSIA technical report, Carnegie-Mellon University.

  • Potts CN and van Wassenhove LN (1991). Single machine tardiness sequencing heuristics . IIE Trans 23: 346–354.

    Article  Google Scholar 

  • Sen T, Sulek JM and Dileepan P (2003). Static scheduling research to minimize weighted and unweighted tardiness: A state-of-the-art survey . Int J Prod Econ 83: 1–12.

    Article  Google Scholar 

  • Vepsalainen AP and Morton TE (1987). Priority rules for job shops with weighted tardiness costs . Mngt Sci 33: 1035–1047.

    Article  Google Scholar 

  • Volgenant A and Teerhuis E (1999). Improved heuristics for the n-job single-machine weighted tardiness problem . Comput Opns Res 26: 35–44.

    Article  Google Scholar 

Download references

Acknowledgements

This study was supported by research funds from Dong-A University.

Author information

Authors and Affiliations

  1. Yeungnam University, Korea

    S H Yoon

  2. Dong-A University, Busan, Korea

    I S Lee

Authors
  1. S H Yoon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. I S Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to I S Lee.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yoon, S., Lee, I. New constructive heuristics for the total weighted tardiness problem. J Oper Res Soc 62, 232–237 (2011). https://doi.org/10.1057/jors.2009.186

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.186

Keywords

Search

Navigation