Scheduling with arranged multi-purpose machines (Q614212)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Scheduling with arranged multi-purpose machines |
scientific article |
Statements
Scheduling with arranged multi-purpose machines (English)
0 references
27 December 2010
0 references
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.
0 references
makespan
0 references
complexity
0 references
branch and bound
0 references
scheduling theory
0 references
MPMs
0 references
multi-purpose machines
0 references
heuristics
0 references