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

An exact algorithm for the single machine problem with unavailability periods

Author

Listed:
  • Anis Gharbi
  • Mohamed Labidi
  • Mohamed Haouari

Abstract

We investigate the single machine scheduling problem with job release dates and due dates, and multiple planned unavailability time periods. This problem arises in the context of machine scheduling with planned preventive maintenance and might be viewed as a generalisation of several fundamental single-machine problems. The contribution of this paper is two-fold. First, we propose a new lower bound that is based on the concept of semi-preemptive scheduling. Second, we propose an exact algorithm that requires solving a sequence of one-machine problems without availability constraints. We report the results of extensive computational experiments that provide evidence that the semi-preemptive lower bound is very tight and that the proposed algorithm consistently delivers optimal solution for instances with up to 1,000 jobs while requiring short CPU times. [Received 21 May 2012; Revised 14 March 2013; Revised 23 September 2013; Accepted 5 January 2014]

Suggested Citation

  • Anis Gharbi & Mohamed Labidi & Mohamed Haouari, 2015. "An exact algorithm for the single machine problem with unavailability periods," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 9(2), pages 244-260.
    • Handle: RePEc:ids:eujine:v:9:y:2015:i:2:p:244-260
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=68654
    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.

    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:9:y:2015:i:2:p:244-260. 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.