An exact algorithm for the single machine problem with unavailability periods

Anis Gharbi, Mohamed Labidi and Mohamed Haouari

European Journal of Industrial Engineering, 2015, vol. 9, issue 2, 244-260

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]

Keywords: single machine scheduling; unavailability constraints; job release dates; delivery times; maximum lateness; due dates; planned preventive maintenance. (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=68654 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:9:y:2015:i:2:p:244-260

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().