Scheduling on machines with variable service rates (Q1094326)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Scheduling on machines with variable service rates |
scientific article |
Statements
Scheduling on machines with variable service rates (English)
0 references
1987
0 references
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.
0 references
single machine
0 references
minimum schedule length
0 references
minimum sum of completion times
0 references
minimum maximum lateness
0 references
minimum sum of tardiness times
0 references
minimum number of tardy jobs
0 references
parallel machines
0 references
cyclic series of service factors
0 references
0 references