Scheduling on machines with variable service rates (Q1094326)

This paper deals with scheduling on single and parallel machines where the service rate of a machine remains constant while a job is being processed and is changed upon its completion. Associated with machine \(M_ 1\) there is a vector of service factors \(\alpha_{\ell}=(\alpha_{1l},\alpha_{2l},...,)\); it is described as cyclic of order k iff \(\alpha_ l(k)=(\alpha_{1l},...,\alpha_{kl},\alpha_{1l},...,\alpha_{kl},.... ,)\). Processing job \(J_ i\) in the jth position of \(M_ l\) consumes \(\alpha_{j\ell}t_ i\) time units. We present an 0(n log n) algorithm for \(1/vsr/\Sigma_{\max}\) and an \(0(n^ m\log n)\) algorithm for Pm/vsr/\(\sum C_ i\), \(m\geq 1\). It is proved that \(1/vsr/L_{\max}\) is NP-hard even for a monotone non-decreasing or a cyclic series of service factors, thus 1/vsr/\(\delta\), \(\delta\in \{\sum U_ i\), \(\sum T_ i\}\) and NP-hard as well. Finally, efficiently solvable special cases of 1/vsr/\(\delta\), \(\delta \in \{L_{\max},\sum U_ i,\sum T_ i\}\) are studied.