×

Static routing in stochastic scheduling: performance guarantees and asymptotic optimality. (English) Zbl 1446.90088

Summary: We study the problem of scheduling a set of \(J\) jobs on \(M\) machines with stochastic job processing times when no preemptions are allowed and with a weighted sum of expected completion times objective. Our model allows for “unrelated” machines: the distributions of processing times may vary across both jobs and machines. We study static routing policies, which assign (or “route”) each job to a particular machine at the start of the problem and then sequence jobs on each machine according to the weighted shortest expected processing time rule. We discuss how to obtain a good routing of jobs to machines by solving a convex quadratic optimization problem that has \(J \times M\) variables and depends only on the job processing distributions through their expected values. Our main result is an additive performance bound on the suboptimality of this static routing policy relative to an optimal adaptive, nonanticipative scheduling policy. This result implies that such static routing policies are asymptotically optimal as the number of jobs grows large. In the special case of “uniformly related” machines – that is, machines differing only in their speeds – we obtain a similar but slightly sharper result for a static routing policy that routes jobs to machines proportionally to machine speeds. We also study the impact that dependence in processing times across jobs can have on the suboptimality of the static routing policy. The main novelty in our work is deriving lower bounds on the performance of an optimal adaptive, nonanticipative scheduling policy; we do this through the use of an information relaxation in which all processing times are revealed before scheduling jobs and a penalty that appropriately compensates for this additional information.
The online appendices are available at https://doi.org/10.1287/opre.2018.1749.

MSC:

90B36 Stochastic scheduling theory in operations research
90C39 Dynamic programming
90C20 Quadratic programming
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Agrawal A, Klein P, Ravi R (1995) When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24(3):440-456.Crossref, Google Scholar · Zbl 0831.68071 · doi:10.1137/S0097539792236237
[2] Anand S, Garg N, Kumar A (2012) Resource augmentation for weighted flow-time explained by dual fitting. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1228-1241.Crossref, Google Scholar · Zbl 1422.68319 · doi:10.1137/1.9781611973099.97
[3] Balseiro SR, Brown DB (2018) Approximations to stochastic dynamic programs via information relaxation duality. Oper. Res. Forthcoming.Google Scholar
[4] Bar-Yehuda R, Even S (1981) A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2):198-203.Crossref, Google Scholar · Zbl 0459.68033 · doi:10.1016/0196-6774(81)90020-1
[5] Bertsekas DP (1999) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar · Zbl 1015.90077
[6] Bertsimas D, Gamarnik D, Sethuraman J (2003) From fluid relaxations to practical algorithms for high-multiplicity job-shop scheduling: The holding cost objective. Oper. Res. 51(5):798-813.Link, Google Scholar · Zbl 1165.90449
[7] Brown DB, Smith JE, Sun P (2010) Information relaxations and duality in stochastic dynamic programs. Oper. Res. 58(4, part 1):785-801.Link, Google Scholar · Zbl 1228.90062
[8] Dai JG (1995) On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models Ann. Appl. Probab. 5(1):49-77.Crossref, Google Scholar · Zbl 0822.60083 · doi:10.1214/aoap/1177004828
[9] Dai JG, Lin W (2005) Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2):197-218.Link, Google Scholar · Zbl 1165.90359
[10] Dai J, Lin W (2008) Asymptotic optimality of maximum pressure policies in stochastic processing networks Ann. Appl. Probab. 18(6):2239-2299.Crossref, Google Scholar · Zbl 1175.90083 · doi:10.1214/08-AAP522
[11] Edmonds J (1971) Matroids and the greedy algorithm. Math. Programming 1(1):127-136.Crossref, Google Scholar · Zbl 0253.90027 · doi:10.1007/BF01584082
[12] Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5(2):287-326.Crossref, Google Scholar · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[13] Gupta V, Moseley B, Uetz M, Xie Q (2017) Stochastic online scheduling on unrelated machines. Eisenbrand F, Koenemann J, eds. Integer Programming and Combinatorial Optimization (IPCO 2017), Lecture Notes in Computer Science, vol. 10328 (Springer International, Cham, Switzerland), 228-240.Crossref, Google Scholar · Zbl 1416.90018 · doi:10.1007/978-3-319-59250-3_19
[14] Hall LA, Schulz AS, Shmoys DB, Wein J (1997) Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. 22(3):513-544.Link, Google Scholar · Zbl 0883.90064
[15] Haugh MB, Kogan L (2004) Pricing American options: A duality approach. Oper. Res. 52(2):258-270.Link, Google Scholar · Zbl 1165.91401
[16] Hoogeveen H, Schuurman P, Woeginger G (2001) Non-approximability results for scheduling problems with minsum criteria. INFORMS J. Comput. 13(2):157-168.Link, Google Scholar · Zbl 1238.90066
[17] Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2):274-296.Crossref, Google Scholar · Zbl 1089.68665 · doi:10.1145/375827.375845
[18] Maglaras C (2000) Discrete-review policies for scheduling stochastic networks: Trajectory tracking and fluid-scale asymptotic optimality. Ann. Appl. Probab. 10(3):897-929.Crossref, Google Scholar · Zbl 1083.60520 · doi:10.1214/aoap/1019487513
[19] Möhring RH, Schulz AS, Uetz M (1999) Approximation in stochastic scheduling: The power of LP-based priority policies. J. ACM 46(6):924-942.Crossref, Google Scholar · Zbl 1176.90262 · doi:10.1145/331524.331530
[20] Motwani R, Raghavan P (1995) Randomized Algorithms (Cambridge University Press, New York).Crossref, Google Scholar · Zbl 0849.68039 · doi:10.1017/CBO9780511814075
[21] Nazarathy Y, Weiss G (2009) Near optimal control of queueing networks over a finite time horizon. Ann. Oper. Res. 170(1):233-249.Crossref, Google Scholar · Zbl 1169.90346 · doi:10.1007/s10479-008-0443-x
[22] Rogers L (2002) Monte Carlo valuation of American options. Math. Finance 12(3):271-286.Crossref, Google Scholar · Zbl 1029.91036 · doi:10.1111/1467-9965.02010
[23] Rothkopf M (1966) Scheduling with random service times. Management Sci. 12(9):703-713.Link, Google Scholar · Zbl 0199.23302
[24] Scharbrodt M, Schickinger T, Steger A (2006) A new average case analysis for completion time scheduling. J. ACM 53(1):121-146.Crossref, Google Scholar · Zbl 1315.90017 · doi:10.1145/1120582.1120585
[25] Schulz AS (1996) Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. Cunningham WH, McCormick ST, Queyranne M, eds. Integer Programming and Combinatorial Optimization (IPCO 1996). Lecture Notes in Computer Science, vol. 1084 (Springer, Berlin), 301-315.Crossref, Google Scholar · Zbl 1414.90167 · doi:10.1007/3-540-61310-2_23
[26] Schulz AS, Skutella M (2002) Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math. 15(4):450-469.Crossref, Google Scholar · Zbl 1055.90040 · doi:10.1137/S0895480199357078
[27] Schulz AS, et al.. (1996) Polytopes and scheduling. Unpublished PhD thesis, Technische Universität Berlin, Berlin.Google Scholar · Zbl 0859.90088
[28] Sethuraman J, Squillante MS (1999) Optimal stochastic scheduling in multiclass parallel queues. ACM SIGMETRICS Perform. Eval. Rev. 27(1):93-102.Crossref, Google Scholar · doi:10.1145/301464.301483
[29] Skutella M (2001) Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM 48(2):206-242.Crossref, Google Scholar · Zbl 1323.90024 · doi:10.1145/375827.375840
[30] Skutella M, Sviridenko M, Uetz M (2016) Unrelated machine scheduling with stochastic processing times. Math. Oper. Res. 41(3):851-864.Link, Google Scholar · Zbl 1342.90072
[31] Smith W (1956) Various optimizers for single-stage production. Naval Res. Logist. Quart. 3(1-2):59-66.Crossref, Google Scholar · doi:10.1002/nav.3800030106
[32] Souza A, Steger A (2006) The expected competitive ratio for weighted completion time scheduling. Theory Comput. Systems 39(1):121-136.Crossref, Google Scholar · Zbl 1101.68010 · doi:10.1007/s00224-005-1261-z
[33] Uetz M (2003) When greediness fails: Examples from stochastic scheduling. Oper. Res. Lett. 31(6):413-419.Crossref, · Zbl 1052.90039 · doi:10.1016/S0167-6377(03)00047-6
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.