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

Parallel Machine Scheduling by Column Generation

Author

Listed:
  • VAN DEN AKKER, Janna M.

    (Center for Operations Research and Econometrics (CORE), Université catholique de Louvain (UCL), Louvain la Neuve, Belgium)

  • HOOGEVEEN, J.A.

    (Department of Mathematics and Computing Science, Eindhoven University of)

  • VAN DE VELDE, Steef L.

    (Department of Mechanical Engineering, University of Twente, Tbe Netherlands)

Abstract

Parallel machine scheduling problems concern the scheduling of n jobs on m machines to minimize some function of the job completion times. If preemption is not allowed, then most problems are not only NP-hard, but also very hard from a practical point of view. In this paper, we show that strong and fast linear programming lower bounds can be computed for an important class of machine scheduling problems with additive objective functions. Characteristic of these problems is that on each machine the order of the jobs in the relevant part of the schedule is obtained through some priority rule. To that end, we formulate these parallel machine scheduling problems as a set covering problems with an exponential number of binary variables, n covering constraints, and a single side constraint. We show that the linear programming relaxation can be solved efficiently by column generation, since the pricing problem is solvable in pseudo-polynomial time. We display this approach on the problem of minimizing total weighted completion time on m identical machines. Our computational results show that the lower bound is singularly strong and that the outcome of the linear program is often integral Moreover, they show that our branch-and-bound algorithm that uses the linear programming lower bound outperforms the previously best algorithm.

Suggested Citation

  • VAN DEN AKKER, Janna M. & HOOGEVEEN, J.A. & VAN DE VELDE, Steef L., 1996. "Parallel Machine Scheduling by Column Generation," LIDAM Discussion Papers CORE 1996013, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:1996013
    as

    Download full text from publisher

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

    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:1996013. 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.