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

Heuristic constructive algorithms for open shop scheduling to minimize mean flow time

Author

Listed:
  • Bräsel, Heidemarie
  • Herms, André
  • Mörig, Marc
  • Tautenhahn, Thomas
  • Tusch, Jan
  • Werner, Frank

Abstract

In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.

Suggested Citation

  • Bräsel, Heidemarie & Herms, André & Mörig, Marc & Tautenhahn, Thomas & Tusch, Jan & Werner, Frank, 2008. "Heuristic constructive algorithms for open shop scheduling to minimize mean flow time," European Journal of Operational Research, Elsevier, vol. 189(3), pages 856-870, September.
    • Handle: RePEc:eee:ejores:v:189:y:2008:i:3:p:856-870
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00661-3
    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. Brasel, Heidemarie & Hennes, Holger, 2004. "On the open-shop problem with preemption and minimizing the average completion time," European Journal of Operational Research, Elsevier, vol. 157(3), pages 607-619, September.
    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. Mejía, Gonzalo & Yuraszeck, Francisco, 2020. "A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times," European Journal of Operational Research, Elsevier, vol. 285(2), pages 484-496.
    2. Guillermo Campos Ciro & Frédéric Dugardin & Farouk Yalaoui & Russell Kelly, 2016. "Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4854-4881, August.
    3. Naderi, B. & Zandieh, M., 2014. "Modeling and scheduling no-wait open shop problems," International Journal of Production Economics, Elsevier, vol. 158(C), pages 256-266.
    4. Pempera, Jaroslaw & Smutnicki, Czeslaw, 2018. "Open shop cyclic scheduling," European Journal of Operational Research, Elsevier, vol. 269(2), pages 773-781.
    5. Mohamed Amine Abdeljaoued & Nour El Houda Saadani & Zied Bahroun, 2020. "Heuristic and metaheuristic approaches for parallel machine scheduling under resource constraints," Operational Research, Springer, vol. 20(4), pages 2109-2132, December.

    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.

      More about this item

      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:eee:ejores:v:189:y:2008:i:3:p:856-870. 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.