Title: Scheduling with arranged multi-purpose machines

Authors: Mourad Boudhar, Hamza Tchikou

Addresses: Faculty of Mathematics, Houari Boumediene University of Science and Technology (USTHB), BP 32 Bab-Ezzouar, El-Alia 16111, Algiers, Algeria. ' Faculty of Mathematics, Houari Boumediene University of Science and Technology (USTHB), BP 32 Bab-Ezzouar, El-Alia 16111, Algiers, Algeria

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.

DOI: 10.1504/IJOR.2010.033545

International Journal of Operational Research, 2010 Vol.8 No.3, pp.379 - 397

Published online: 04 Jun 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article