IDEAS home Printed from https://ideas.repec.org/p/por/fepwps/129.html
   My bibliography  Save this paper

An Exact Approach to Early/Tardy Scheduling with Release Dates

Author

Listed:
  • Jorge M. S. Valente

    (Faculdade de Economia da Universidade do Porto)

  • Rui A. F. S. Alves

    (Faculdade de Economia da Universidade do Porto)

Abstract

In this paper we consider the single machine earliness/tardiness scheduling problem with di?erent release dates and no unforced idle time. The problem is decomposed into a weighted earliness subproblem and a weighted tardiness subproblem. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is then simply the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.

Suggested Citation

  • Jorge M. S. Valente & Rui A. F. S. Alves, 2003. "An Exact Approach to Early/Tardy Scheduling with Release Dates," FEP Working Papers 129, Universidade do Porto, Faculdade de Economia do Porto.
    • Handle: RePEc:por:fepwps:129
    as

    Download full text from publisher

    File URL: http://www.fep.up.pt/investigacao/workingpapers/wp129.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Potts, C. N. & Van Wassenhove, L. N., 1983. "An algorithm for single machine sequencing with deadlines to minimize total weighted completion time," European Journal of Operational Research, Elsevier, vol. 12(4), pages 379-387, April.
    2. Akturk, M. Selim & Ozdemir, Deniz, 2001. "A new dominance rule to minimize total weighted tardiness with unequal release dates," European Journal of Operational Research, Elsevier, vol. 135(2), pages 394-412, December.
    3. Jorge M. S. Valente & Rui A. F. S. Alves, 2003. "Improved Heuristics for the Early/Tardy Scheduling Problem with No Idle Time," FEP Working Papers 126, Universidade do Porto, Faculdade de Economia do Porto.
    4. George Li, 1997. "Single machine earliness and tardiness scheduling," European Journal of Operational Research, Elsevier, vol. 96(3), pages 546-558, 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. Mário Rui Silva & Hermano Rodrigues, 2004. "Competitiveness and Public-Private Partnerships: Towards a More Decentralised Policy," ERSA conference papers ersa04p299, European Regional Science Association.
    2. Cristina Barbot, 2004. "Low cost carriers, secondary airports and State aid: an economic assessment of the Charleroi affair," FEP Working Papers 159, Universidade do Porto, Faculdade de Economia do Porto.
    3. Jorge M. S. Valente & Rui A. F. S. Alves, 2004. "Beam search algorithms for the early/tardy scheduling problem with release dates," FEP Working Papers 143, Universidade do Porto, Faculdade de Economia do Porto.
    4. Ana Paula Delgado & Isabel Maria Godinho, 2004. "The evolution of city size distribution in Portugal: 1864-2001," FEP Working Papers 151, Universidade do Porto, Faculdade de Economia do Porto.
    5. Filipe J. Sousa & Luis M. de Castro, 2004. "The strategic relevance of business relationships: a preliminary assessment," FEP Working Papers 163, Universidade do Porto, Faculdade de Economia do Porto.
    6. Rosa Forte, 2004. "The relationship between foreign direct investment and international trade. Substitution or complementarity? A survey," FEP Working Papers 140, Universidade do Porto, Faculdade de Economia do Porto.
    7. Pedro Cosme Costa Vieira, 2005. "Multi Product Market Equilibrium with Sequential Search," FEP Working Papers 166, Universidade do Porto, Faculdade de Economia do Porto.
    8. Rui Henrique Alves, 2004. "Europe: Looking for a New Model," FEP Working Papers 154, Universidade do Porto, Faculdade de Economia do Porto.
    9. Mário Rui Silva & Hermano Rodrigues, 2005. "Public-Private Partnerships and the Promotion of Collective Entrepreneurship," FEP Working Papers 172, Universidade do Porto, Faculdade de Economia do Porto.
    10. Pedro Cosme Costa Vieira, 2005. "The importance in the papers' impact of the number of pages and of co-authors - an empirical estimation with data from top ranking economic journals," FEP Working Papers 169, Universidade do Porto, Faculdade de Economia do Porto.

    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. Jouglet, Antoine & Savourey, David & Carlier, Jacques & Baptiste, Philippe, 2008. "Dominance-based heuristics for one-machine total cost scheduling problems," European Journal of Operational Research, Elsevier, vol. 184(3), pages 879-899, February.
    2. Jorge M. S. Valente & Rui A. F. S. Alves, 2003. "Improved Lower Bounds for the Early/Tardy Scheduling Problem with No Idle Time," FEP Working Papers 125, Universidade do Porto, Faculdade de Economia do Porto.
    3. Philippe Baptiste & Ruslan Sadykov, 2009. "On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(6), pages 487-502, September.
    4. Pei-Chann Chang & Shih-Hsin Chen & Chin-Yuan Fan & V. Mani, 2010. "Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems," Annals of Operations Research, Springer, vol. 180(1), pages 197-211, November.
    5. Jorge M. S. Valente & Rui A. F. S. Alves, 2003. "Heuristics for the Early/Tardy Scheduling Problem with Release Dates," FEP Working Papers 130, Universidade do Porto, Faculdade de Economia do Porto.
    6. Valente, Jorge M.S. & Alves, Rui A.F.S., 2007. "Heuristics for the early/tardy scheduling problem with release dates," International Journal of Production Economics, Elsevier, vol. 106(1), pages 261-274, March.
    7. Jorge M. S. Valente, 2004. "Local and global dominance conditions for the weighted earliness scheduling problem with no idle time," FEP Working Papers 156, Universidade do Porto, Faculdade de Economia do Porto.
    8. Jorge M. S. Valente & Rui A. F. S. Alves, 2004. "Filtered and Recovering beam search algorithms for the early/tardy scheduling problem with no idle time," FEP Working Papers 142, Universidade do Porto, Faculdade de Economia do Porto.
    9. Fernando Jaramillo & Busra Keles & Murat Erkoc, 2020. "Modeling single machine preemptive scheduling problems for computational efficiency," Annals of Operations Research, Springer, vol. 285(1), pages 197-222, February.
    10. Yalaoui, F. & Chu, C., 2006. "New exact method to solve the Pm/rj/[summation operator]Cj schedule problem," International Journal of Production Economics, Elsevier, vol. 100(1), pages 168-179, March.
    11. Cristina Barbot, 2004. "Low cost carriers, secondary airports and State aid: an economic assessment of the Charleroi affair," FEP Working Papers 159, Universidade do Porto, Faculdade de Economia do Porto.
    12. Rosa Forte, 2004. "The relationship between foreign direct investment and international trade. Substitution or complementarity? A survey," FEP Working Papers 140, Universidade do Porto, Faculdade de Economia do Porto.
    13. 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.
    14. Maria do Rosario Correia & Scott C. Linn & Andrew Marshall, 2004. "An Empirical Investigation of Debt Contract Design: The Determinants of the Choice of Debt Terms in Eurobond Issues," FEP Working Papers 148, Universidade do Porto, Faculdade de Economia do Porto.
    15. Ana Paula Delgado & Isabel Maria Godinho, 2004. "The evolution of city size distribution in Portugal: 1864-2001," FEP Working Papers 151, Universidade do Porto, Faculdade de Economia do Porto.
    16. Cheng, Jinliang & Steiner, George & Stephenson, Paul, 2001. "A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times," European Journal of Operational Research, Elsevier, vol. 130(3), pages 559-575, May.
    17. J M S Valente & R A F S Alves, 2005. "Improved lower bounds for the early/tardy scheduling problem with no idle time," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(5), pages 604-612, May.
    18. Chen, Shih-Hsin & Chen, Min-Chih, 2013. "Addressing the advantages of using ensemble probabilistic models in Estimation of Distribution Algorithms for scheduling problems," International Journal of Production Economics, Elsevier, vol. 141(1), pages 24-33.
    19. Ronconi, Débora P. & Henriques, Luís R.S., 2009. "Some heuristic algorithms for total tardiness minimization in a flowshop with blocking," Omega, Elsevier, vol. 37(2), pages 272-281, April.
    20. George Li, 1997. "Single machine earliness and tardiness scheduling," European Journal of Operational Research, Elsevier, vol. 96(3), pages 546-558, February.

    More about this item

    Keywords

    scheduling; early/tardy; release dates; lower bounds; branch-and-bound;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:por:fepwps:129. 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: the person in charge (email available below). General contact details of provider: https://edirc.repec.org/data/fepuppt.html .

    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.