IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2002009.html
   My bibliography  Save this paper

The relation of time indexed formulations of single machine scheduling problems to the node packing problem

Author

Listed:
  • WATERER, Hamish
  • JOHNSON, Ellis
  • SAVELSBERGH, Martin

Abstract

The relation of time indexed formulations of nonpreemptive single machine schedulingproblems to the node packing problem is formally established and then used toprovide simple and intuitive alternate proofs of validity and maximality for previouslyknown results on the facial structure of the scheduling problem. Previous work on thefacial structure has focused on describing the convex hull of the set of feasible partialschedules, i.e. schedules in which not all jobs have to be started. The equivalencebetween the characteristic vectors of this set and those of the set of feasible nodepackings in a graph whose structure is determined by the parameters of the schedulingproblem is established. The main contribution of this paper is to show that the facetinducing inequalities for the convex hull of the set of feasible partial schedules thathave integral coefficients and right hand side 1 or 2 are the maximal clique inequalitiesand the maximally and sequentially lifted 5-hole inequalities of the convex hull of theset of feasible node packings in this graph respectively.

Suggested Citation

  • WATERER, Hamish & JOHNSON, Ellis & SAVELSBERGH, Martin, 2002. "The relation of time indexed formulations of single machine scheduling problems to the node packing problem," LIDAM Discussion Papers CORE 2002009, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2002009
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2002.html
    Download Restriction: no
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Louis-Philippe Bigras & Michel Gamache & Gilles Savard, 2008. "Time-Indexed Formulations and the Total Weighted Tardiness Problem," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 133-142, February.
    2. Nurre, Sarah G. & Cavdaroglu, Burak & Mitchell, John E. & Sharkey, Thomas C. & Wallace, William A., 2012. "Restoring infrastructure systems: An integrated network design and scheduling (INDS) problem," European Journal of Operational Research, Elsevier, vol. 223(3), pages 794-806.
    3. Pasquale Avella & Maurizio Boccia & Bernardo D’Auria, 2005. "Near-Optimal Solutions of Large-Scale Single-Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 183-191, May.
    4. Pasquale Avella & Maurizio Boccia & Carlo Mannino & Igor Vasilyev, 2017. "Time-Indexed Formulations for the Runway Scheduling Problem," Transportation Science, INFORMS, vol. 51(4), pages 1196-1209, November.
    5. Kovalyov, Mikhail Y. & Ng, C.T. & Cheng, T.C. Edwin, 2007. "Fixed interval scheduling: Models, applications, computational complexity and algorithms," European Journal of Operational Research, Elsevier, vol. 178(2), pages 331-342, April.
    6. Natashia Boland & Riley Clement & Hamish Waterer, 2016. "A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 14-30, February.
    7. Laureano Escudero & Javier Salmeron, 2005. "On a Fix-and-Relax Framework for a Class of Project Scheduling Problems," Annals of Operations Research, Springer, vol. 140(1), pages 163-188, November.

    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:cor:louvco:2002009. 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.

    We have no bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.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.