Advanced Search
MyIDEAS: Login to save this paper or follow this series

Beam search heuristics for quadratic earliness and tardiness scheduling

Contents:

Author Info

  • Jorge M. S. Valente

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

Registered author(s):

    Abstract

    In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small to medium size instances. For larger instances, however, this procedure requires excessive computation times, and the recovering beam search algorithm then becomes the heuristic of choice.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: http://www.fep.up.pt/investigacao/workingpapers/08.06.12_wp279.pdf
    Download Restriction: no

    Bibliographic Info

    Paper provided by Universidade do Porto, Faculdade de Economia do Porto in its series FEP Working Papers with number 279.

    as in new window
    Length: 31 pages
    Date of creation: Jun 2008
    Date of revision:
    Handle: RePEc:por:fepwps:279

    Contact details of provider:
    Postal: Rua Dr. Roberto Frias, 4200 PORTO
    Phone: 351-22-5571100
    Fax: 351-22-5505050
    Email:
    Web page: http://www.fep.up.pt/
    More information through EDIRC

    Related research

    Keywords: scheduling; heuristics; beam search; single machine; quadratic earliness; quadratic tardiness;

    This paper has been announced in the following NEP Reports:

    References

    References listed on IDEAS
    Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
    as in new window
    1. Esteve, B. & Aubijoux, C. & Chartier, A. & T'kindt, V., 2006. "A recovering beam search algorithm for the single machine Just-in-Time scheduling problem," European Journal of Operational Research, Elsevier, Elsevier, vol. 172(3), pages 798-813, August.
    2. Hoogeveen, Han, 2005. "Multicriteria scheduling," European Journal of Operational Research, Elsevier, Elsevier, vol. 167(3), pages 592-623, December.
    3. Jorge M. S. Valente, 2007. "An exact approach for single machine scheduling with quadratic earliness and tardiness penalties," FEP Working Papers, Universidade do Porto, Faculdade de Economia do Porto 238, Universidade do Porto, Faculdade de Economia do Porto.
    4. Schaller, Jeffrey, 2002. "Minimizing the sum of squares lateness on a single machine," European Journal of Operational Research, Elsevier, Elsevier, vol. 143(1), pages 64-79, November.
    5. George Li, 1997. "Single machine earliness and tardiness scheduling," European Journal of Operational Research, Elsevier, Elsevier, vol. 96(3), pages 546-558, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    When requesting a correction, please mention this item's handle: RePEc:por:fepwps:279. 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: ().

    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 references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link 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 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.