×

Scheduling on two identical machines with a speed-up resource. (English) Zbl 1260.68044

Summary: We address a variant of the scheduling problem on two identical machines, where we are given an additional speed-up resource. If a job uses the resource, its processing time may decrease. However, at any time the resource can only be used by at most one job. The objective is to minimize the makespan. For the offline version, we present an FPTAS. For the online version where jobs arrive over list, we propose an online algorithm with competitive ratio of \(1.781\), and show a lower bound of \(1.686\) for any online algorithm.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Epstein, L.; Noga, J.; Seiden, S.; Sgall, J.; Woeginger, G., Randomized on-line scheduling on two uniform machines, Journal of Scheduling, 4, 71-92 (2001) · Zbl 0989.90059
[2] A. Grigoriev, M. Sviridenko, M. Uetz, Unrelated parallel machine scheduling with resource dependent processing times, in: Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 2005, pp. 182-195.; A. Grigoriev, M. Sviridenko, M. Uetz, Unrelated parallel machine scheduling with resource dependent processing times, in: Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 2005, pp. 182-195. · Zbl 1119.90315
[3] Grigoriev, A.; Sviridenko, M.; Uetz, M., Machine scheduling with resource dependent processing times, Mathematical Programming, 110, 1, 209-228 (2007) · Zbl 1192.90073
[4] Grigoriev, A.; Uetz, M., Scheduling jobs with time-resource tradeoff via nonlinear programming, Discrete Optimization, 6, 4, 414-419 (2009) · Zbl 1175.90166
[5] Kellerer, H., An approximation algorithm for identical parallel machine scheduling with resource dependent processing times, Operations Research Letters, 36, 2, 157-159 (2008) · Zbl 1163.90494
[6] Kellerer, H.; Strusevich, V. A., Scheduling parallel dedicated machines under a single non-shared resource, European Journal of Operational Research, 147, 345-364 (2003) · Zbl 1037.90030
[7] Kellerer, H.; Strusevich, V. A., Scheduling problems for parallel dedicated machines under multiple resource constraints, Discrete Applied Mathematics, 113, 45-68 (2004) · Zbl 1053.90039
[8] Kellerer, H.; Strusevich, V. A., Scheduling parallel dedicated machines with the speeding-up resource, Naval Research Logistics, 55, 5, 377-389 (2008) · Zbl 1209.90174
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.