IDEAS home Printed from
   My bibliography  Save this paper

Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties


  • Jorge M. S. Valente

    () (LIACC/NIAAD, Faculdade de Economia, Universidade do Porto, Portugal)

  • Rui A. F. S. Alves

    () (Faculdade de Economia, Universidade do Porto, Portugal)


In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule. The computational experiments show that the best results are provided by the heuristics that explicitly consider both early and tardy costs, and the quadratic objective function. Therefore, it is indeed important to specifically address the quadratic feature of the cost function, instead of simply using procedures originally developed for a linear objective function. The heuristics are quite fast, and are capable of quickly solving even very large instances. The use of an improvement step is recommended, since it usually improves the solution quality with little additional computational effort.

Suggested Citation

  • Jorge M. S. Valente & Rui A. F. S. Alves, 2007. "Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties," FEP Working Papers 236, Universidade do Porto, Faculdade de Economia do Porto.
  • Handle: RePEc:por:fepwps:236

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. Rothschild, Michael, 1974. "Searching for the Lowest Price When the Distribution of Prices Is Unknown," Journal of Political Economy, University of Chicago Press, vol. 82(4), pages 689-711, July/Aug..
    2. Hey, John D., 1981. "Are optimal search rules reasonable? and vice versa? (And does it matter anyway?)," Journal of Economic Behavior & Organization, Elsevier, vol. 2(1), pages 47-70, March.
    3. Axel, Bo, 1977. " Search Market Equilibrium," Scandinavian Journal of Economics, Wiley Blackwell, vol. 79(1), pages 20-40.
    4. Diamond, Peter A., 1971. "A model of price adjustment," Journal of Economic Theory, Elsevier, vol. 3(2), pages 156-168, June.
    5. Lippman, Steven A & McCall, John J, 1976. "The Economics of Job Search: A Survey," Economic Inquiry, Western Economic Association International, vol. 14(3), pages 347-368, September.
    6. Tesfatsion, Leigh S., 2002. "Agent-Based Computational Economics: Growing Economies from the Bottom Up," Staff General Research Papers Archive 5075, Iowa State University, Department of Economics.
    Full references (including those not matched with items on IDEAS)

    More about this item


    scheduling; single machine; early/tardy; quadratic penalties; dispatching rules;

    NEP fields

    This paper has been announced in the following NEP Reports:


    Access and download statistics


    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:por:fepwps:236. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (). General contact details of provider: .

    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.

    We have no references for this item. You can help adding them by using 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.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.