Online parallel-machine scheduling in KRT environment to minimize total weighted completion time. (English) Zbl 1404.90077
Summary: This paper studies online scheduling on \(m\) identical parallel machines under the KRT environment, where jobs arrive over time and “KRT” means that in the online setting no jobs can be released when all of the machines are busy. The goal is to determine a feasible schedule to minimize the total of weighted completion times. When \(m = 1\), we prove that WSPT is an optimal online algorithm. When \(m \geq 2\), we first present a lower bound \(\frac{m^2 - 2 + \sqrt{m^4 - 4 m + 4}}{2 m(m - 1)}\), and then show that WSPT is a 2-competitive online algorithm for the case \(m = 2\). For the case in which \(m = 2\) and all jobs have equal processing times, we provide a best possible online algorithm with a competitive ratio of \(\frac{1 + \sqrt{3}}{2}\).
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68W27 | Online algorithms; streaming algorithms |
References:
| [1] | Anderson, EJ; Potts, CN, Online scheduling of a single machine to minimize total weighted completion time, Mathematics of Operations Research, 29, 686-697, (2004) · Zbl 1082.90033 |
| [2] | Belouadah, H; Posner, ME; Potts, CN, Scheduling with release dates on a single machine to minimize total weighted completion time, Discrete Applied Mathematics, 36, 213-231, (1992) · Zbl 0757.90032 |
| [3] | Correa, JR; Wagner, MR, LP-based online scheduling: from single to parallel machines, Mathematical Programming, 119, 109-136, (2009) · Zbl 1162.90009 |
| [4] | Goemans, M; Queyranne, M; Schulz, AS; Skutella, M; Wang, Y, Single machine scheduling with release dates, SIAM Journal on Discrete Mathematics, 15, 165-192, (2002) · Zbl 1009.90096 |
| [5] | Hall, LA; Schulz, AS; Shmoys, DB; Wein, J, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, 22, 513-544, (1997) · Zbl 0883.90064 |
| [6] | Li, WJ; Yuan, JJ, Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs, Optimization Letters, 8, 1691-1706, (2014) · Zbl 1310.90046 |
| [7] | Li, WJ; Yuan, JJ, LPT online strategy for parallel-machine scheduling with kind release times, Optimization Letters, 10, 159-168, (2016) · Zbl 1337.90027 |
| [8] | Ma, R; Tao, JP, An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time, Journal of Industrial and Management Optimization, (2017) |
| [9] | Ma, R; Yuan, JJ, Online scheduling with rejection to minimize the total weighted completion time plus the total rejection cost on parallel machines, Journal of the Operations Research Society of China, 4, 111-119, (2016) · Zbl 1338.90175 |
| [10] | Ma, R; Yuan, JJ, Online scheduling to minimize the total weighted completion time plus the rejection cost, Journal of Combinatorial Optimization, 34, 483-503, (2017) · Zbl 1382.90037 |
| [11] | Megow, N; Schulz, AS, On-line scheduling to minimize average completion time revisited, Operations Research Letters, 32, 485-490, (2004) · Zbl 1054.90037 |
| [12] | Pruhs, K; Sgall, J; Tong, E; Leung, J. Y.-T., Handbook of Scheduling: Algorithm, Model, and Performance Analysis, Online scheduling, (2004), Chapman \(\&\) Hall/CRC Press, Boca Raton · Zbl 1103.90002 |
| [13] | Sitters, R; Eisenbrand, F.; Shepherd, F., Integer Programming and Combinatorial Optimization, 6080, Efficient algorithms for average completion time scheduling, 411-423, (2010) · Zbl 1285.90010 |
| [14] | Schulz, AS; Skutella, M, Scheduling unrelated machines by randomized rounding, SIAM Journal on Discrete Mathematics, 15, 450-469, (2002) · Zbl 1055.90040 |
| [15] | Schulz, AS; Skutella, M, The power of -points in preemptive single machine scheduling, Journal of Scheduling, 5, 121-133, (2002) · Zbl 1038.90037 |
| [16] | Tao, JP, A better online algorithm for the parallel machine scheduling to minimize the weighted completion time, Computer and Operations Research, 43, 215-224, (2014) · Zbl 1348.68299 |
| [17] | Tao, JP; Huang, RH; Liu, TD, A 2.28-competitive algorithm for online scheduling on identical machines, Journal of Industrial and Management Optimization, 11, 185-198, (2015) · Zbl 1304.90104 |
| [18] | Tian, J; Fu, RY; Yuan, JJ, Online over time scheduling on parallel-batch machines: A survey, Journal of the Operations Research Society of China, 2, 445-454, (2014) · Zbl 1306.90060 |
| [19] | Vestjeans, APA (1997). On-line machine scheduling. Ph.D. Thesis, Eindhove University of Technology, Netherlands. · Zbl 0941.68515 |
| [20] | Yuan, JJ; Ng, CT; Cheng, TCE, Best semi-online algorithms for unbounded parallel batch scheduling, Discrete Applied Mathematics, 159, 838-847, (2011) · Zbl 1213.68714 |
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.
