Scheduling with arranged multi-purpose machines
type: Item
instance of: scholarly article
title: Scheduling with arranged multi-purpose machines
zbMATH Open document ID: 1202.90124
DOI: 10.1504/IJOR.2010.033545
author: Mourad Boudhar
author: Hamza Tchikou
published in: International Journal of Operational Research
publication date: 2010-12-27T00:00:00Z
review text: Summary: 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\leq i\leq n)\), a ``first permissible'' machine \(h_i (1\leq h(i)\leq m)\) is given on which it can be processed. Thus, machines \(M_{h_i},\ldots , M_m\) are capable of processing job \(J_i\) while machines \(M_1,\ldots , M_{h_i - 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 5829537
zbMATH Keywords: makespan
zbMATH Keywords: complexity
zbMATH Keywords: branch and bound
zbMATH Keywords: scheduling theory
zbMATH Keywords: MPMs
zbMATH Keywords: multi-purpose machines
zbMATH Keywords: heuristics
MaRDI profile type: Publication
full work available at URL: ijor.2010.033545
OpenAlex ID: W2147205879
description: scientific article; zbMATH DE number 5829537