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

Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates

Author

Listed:
  • Detienne, Boris
  • Pinson, Éric
  • Rivreau, David

Abstract

This paper presents new elimination rules for the single machine problem with general earliness and tardiness penalties subject to release dates. These rules, based on a Lagrangian decomposition, allow to drastically reduce the execution windows of the jobs. We measure the efficiency of these properties by integrating them in a branch-and-bound. Tests show that instances with up to 70 jobs without release dates, and up to 40 jobs with release dates, can be optimally solved within 1000Â seconds.

Suggested Citation

  • Detienne, Boris & Pinson, Éric & Rivreau, David, 2010. "Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates," European Journal of Operational Research, Elsevier, vol. 201(1), pages 45-54, February.
    • Handle: RePEc:eee:ejores:v:201:y:2010:i:1:p:45-54
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00065-4
    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. Kenneth R. Baker & Gary D. Scudder, 1990. "Sequencing with Earliness and Tardiness Penalties: A Review," Operations Research, INFORMS, vol. 38(1), pages 22-36, February.
    2. J. Carlier & E. Pinson, 1989. "An Algorithm for Solving the Job-Shop Problem," Management Science, INFORMS, vol. 35(2), pages 164-176, February.
    3. Peridy, Laurent & Pinson, Eric & Rivreau, David, 2003. "Using short-term memory to minimize the weighted number of late jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 148(3), pages 591-603, August.
    4. John J. Kanet & V. Sridharan, 2000. "Scheduling with Inserted Idle Time: Problem Taxonomy and Literature Review," Operations Research, INFORMS, vol. 48(1), pages 99-110, February.
    5. Carlier, J. & Pinson, E., 1994. "Adjustment of heads and tails for the job-shop problem," European Journal of Operational Research, Elsevier, vol. 78(2), pages 146-161, October.
    6. Kedad-Sidhoum, Safia & Solis, Yasmin Rios & Sourd, Francis, 2008. "Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1305-1316, September.
    7. Hendel, Yann & Sourd, Francis, 2006. "Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem," European Journal of Operational Research, Elsevier, vol. 173(1), pages 108-119, August.
    Full references (including those not matched with items on IDEAS)

    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. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    2. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    3. Halil Şen & Kerem Bülbül, 2015. "A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 135-150, February.
    4. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    5. Guinet, Alain & Legrand, Marie, 1998. "Reduction of job-shop problems to flow-shop problems with precedence constraints," European Journal of Operational Research, Elsevier, vol. 109(1), pages 96-110, August.
    6. Sheen, Gwo-Ji & Liao, Lu-Wen, 2007. "A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags," European Journal of Operational Research, Elsevier, vol. 181(1), pages 102-116, August.
    7. Jorge M. S. Valente, 2008. "Beam search heuristics for quadratic earliness and tardiness scheduling," FEP Working Papers 279, Universidade do Porto, Faculdade de Economia do Porto.
    8. D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2007. "A branch and bound algorithm for scheduling trains in a railway network," European Journal of Operational Research, Elsevier, vol. 183(2), pages 643-657, December.
    9. Baptiste, Philippe & Peridy, Laurent & Pinson, Eric, 2003. "A branch and bound to minimize the number of late jobs on a single machine with release time constraints," European Journal of Operational Research, Elsevier, vol. 144(1), pages 1-11, January.
    10. Abdelhakim AitZai & Brahim Benmedjdoub & Mourad Boudhar, 2016. "Branch-and-bound and PSO algorithms for no-wait job shop scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(3), pages 679-688, June.
    11. N Nekoiemehr & G Moslehi, 2011. "Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1403-1412, July.
    12. Jorge M. S. Valente & Maria R. A. Moreira & Alok Singh & Rui A. F. S. Alves, 2009. "Genetic algorithms for single machine scheduling with quadratic earliness and tardiness costs," FEP Working Papers 312, Universidade do Porto, Faculdade de Economia do Porto.
    13. Francis Sourd & Wim Nuijten, 2000. "Multiple-Machine Lower Bounds for Shop-Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 341-352, November.
    14. Carlier, Jacques & Rebai, Ismail, 1996. "Two branch and bound algorithms for the permutation flow shop problem," European Journal of Operational Research, Elsevier, vol. 90(2), pages 238-251, April.
    15. 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.
    16. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    17. Baker, Kenneth R., 2014. "Minimizing earliness and tardiness costs in stochastic scheduling," European Journal of Operational Research, Elsevier, vol. 236(2), pages 445-452.
    18. Schaller, Jeffrey E. & Gupta, Jatinder N.D., 2008. "Single machine scheduling with family setups to minimize total earliness and tardiness," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1050-1068, June.
    19. Gueret, Christelle & Jussien, Narendra & Prins, Christian, 2000. "Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems," European Journal of Operational Research, Elsevier, vol. 127(2), pages 344-354, December.
    20. Pan, Yunpeng & Shi, Leyuan, 2006. "Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 168(3), pages 1030-1039, February.

    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:1:p:45-54. 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.