Scheduling with arranged multi-purpose machines

Mourad Boudhar and Hamza Tchikou

International Journal of Operational Research, 2010, vol. 8, issue 3, 379-397

Abstract: In the present study, we consider a special case of multi-purpose machines (MPMs) in which there is a linear order given for the machines. In addition, for each job J_i(1≤i≤n), a 'first permissible' machine h_i (1≤h(i)≤m) is given on which it can be processed. Thus, machines M_hi,…, M_m are capable of processing job J_i while machines M₁,…, M_hi−1 cannot process job J_i. Each job J_i requires a time p_i and the goal is to minimise the makespan. We prove the NP-hardness of the general problem and present some polynomial sub-problems. Heuristics with an exact algorithm of branch and bound type are also presented with numerical experimentations.

Keywords: scheduling theory; MPMs; multi-purpose machines; makespan; complexity; heuristics; branch and bound. (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=33545 (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:ijores:v:8:y:2010:i:3:p:379-397

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().