Scheduling two identical parallel machines with preparation constraints

Wafaa Labbi, Mourad Boudhar and Ammar Oulamara

International Journal of Production Research, 2017, vol. 55, issue 6, 1531-1548

Abstract: In this paper, we consider the problem of scheduling a set of n jobs on two identical machines with preparation constraints. Each job requires before its execution a set of resources and a non-negligible preparation time. The objective is to minimise the makespan. This problem is NP-hard. We prove the NP-hardness of two specific cases where in the first case preparation times take only three values, whereas in the second case preparation times and the release dates take only two values, respectively. Then, we present some special cases and heuristic algorithms along with an experimental study.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2014.978032 (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:taf:tprsxx:v:55:y:2017:i:6:p:1531-1548

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2014.978032

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().