IDEAS home Printed from https://ideas.repec.org/a/ids/eujine/v12y2018i1p24-42.html
   My bibliography  Save this article

A branch and bound algorithm for solving large-scale single-machine scheduling problems with non-identical release dates

Author

Listed:
  • Seyed Hessameddin Zegordi
  • Mohammad Yavari

Abstract

In this paper, we have examined minimising the total completion times in a single-machine scheduling problem with non-identical job release dates. This problem is known to be strongly NP-hard. We have proposed an effective lower bound-based. Also, a near optimal heuristic has been presented that has an average gap of less than 0.077% from the optimum solution. Additionally, in 18% of the problem instances with up to 60 jobs, the upper bound value is equal to the lower bound value. Then we provide two dominance properties. Subsequently, the proposed lower bound, upper bound and dominance properties have been applied in the branch and bound method and have been tested in a wide range of instances. Computational experiments demonstrate the ability of the proposed method to solve hard and large-size problems with up to 130 jobs within a reasonable time. [Received 19 June 2015; Revised 26 November 2016; Revised 24 January 2017; Accepted 5 September 2017]

Suggested Citation

  • Seyed Hessameddin Zegordi & Mohammad Yavari, 2018. "A branch and bound algorithm for solving large-scale single-machine scheduling problems with non-identical release dates," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 12(1), pages 24-42.
    • Handle: RePEc:ids:eujine:v:12:y:2018:i:1:p:24-42
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=89879
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

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


    Cited by:

    1. Chin-Chia Wu & Jatinder N. D. Gupta & Win-Chin Lin & Shuenn-Ren Cheng & Yen-Lin Chiu & Juin-Han Chen & Long-Yuan Lee, 2022. "Robust Scheduling of Two-Agent Customer Orders with Scenario-Dependent Component Processing Times and Release Dates," Mathematics, MDPI, vol. 10(9), pages 1-17, May.

    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:ids:eujine:v:12:y:2018:i:1:p:24-42. 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: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=210 .

    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.