Online scheduling with multi-state machines. (English) Zbl 1386.90056
Summary: In this paper, we propose a general framework for online scheduling problems in which each machine has multiple states that lead to different processing times. For these problems, in addition to deciding how to assign jobs to machines, we also need to set the states of the machines each time they are assigned jobs. For a wide range of machine environments, job processing characteristics and constraints, and cost functions, we develop a 5.14-competitive deterministic online algorithm and a 3.65-competitive randomized online algorithm. The online weighted traveling repairman problem belongs to this general framework, and both our deterministic and randomized online algorithms lead to lower competitive ratios than the current existing ones in the literature. In addition, we include a complete proof that the online algorithm ReOpt (reoptimizing the route of the repairman whenever a new request is released) is almost surely asymptotically optimal for a probabilistic version of this problem.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68W27 | Online algorithms; streaming algorithms |
Keywords:
competitive analysis; deterministic and randomized algorithms; machine scheduling; multi-state; online algorithms; traveling repairmanReferences:
| [1] | A.Allahverdi, J. N.Gupta, and T.Aldowaisan, A review of scheduling research involving setup considerations, Omega27 (1999), 219-239. |
| [2] | A.Allahverdi et al., A survey of scheduling problems with setup times or costs, Eur. J. Oper. Res.187 (2008), 985-1032. · Zbl 1137.90474 |
| [3] | E. J.Anderson and C. N.Potts, Online scheduling of a single machine to minimize total weighted completion time, Math. Oper. Res.29 (2004), 686-697. · Zbl 1082.90033 |
| [4] | A.Archer and A.Blasiak, Improved approximation algorithms for the minimum latency problem via prize‐collecting strolls, Proc. 21st Ann. ACM‐SIAM Symp. Discrete Algorithms, Soc. Ind. App. Math., Austin, TX, 2010, pp. 429-447. · Zbl 1288.68100 |
| [5] | G.Ausiello, V.Bonifaci, and L.Laura, The online prize‐collecting traveling salesman problem, Inf. Process. Lett.107 (2008), 199-204. · Zbl 1190.90152 |
| [6] | G.Ausiello et al., Algorithms for the on‐line quota traveling salesman problem, Inf. Process. Lett.92 (2004), 89-94. · Zbl 1178.90282 |
| [7] | G.Ausiello, L.Laura, and E.Pini, A diligent algorithm for OL‐TRP on the line, Technical report 03‐06, Department of Computer and Systems Science, Univ. of Rome “La Sapienza”, Rome, Italy, 2006. |
| [8] | J.Beardwood, J. H.Halton, and J. M.Hammersley, The shortest path through many points, Cambridge Univ. Press35 (1959), 299-327. · Zbl 0118.35601 |
| [9] | M.Blom, S. O.Krumke, W. E.dePaepe, and L.Stougie, The online TSP against fair adversaries, INFORMS J. Comput.13 (2001), 138-148. · Zbl 1238.90127 |
| [10] | A.Blum et al., The minimum latency problem, Proc. 26th Ann. ACM Symp. Theor. Comput, Assoc. Comput. Machinery, Quebec, Canada, 1994, pp. 163-171. · Zbl 1345.90073 |
| [11] | V.Bonifaci, M.Lipmann, and L.Stougie, Online multi‐server dial‐a‐ride problems, TU/e, Eindhoven Univ. of Technology, Department of Mathematics and Computing Science, Eindhoven, Netherlands, 2006. |
| [12] | C.Chung, T.Nonner, and A.Souza, SRPT is 1.86‐competitive for completion time scheduling, Proc. 21st Ann. ACM‐SIAM Symp. Discrete Algorithms, Soc. Ind. Appl. Math., Austin, TX, 2010, pp. 1373-1388. · Zbl 1288.90024 |
| [13] | J.Correa and M.Wagner, LP‐based online scheduling: From single to parallel machines, Math. Program.119 (2007), 109-136. · Zbl 1162.90009 |
| [14] | E.Feuerstein and L.Stougie, On‐line single‐server dial‐a‐ride problems, Theor. Comput. Sci.268 (2001), 91-105. · Zbl 0984.68003 |
| [15] | G.Goel and A.Mehta, Online budgeted matching in random input models with applications to adwords, Proc. 19th Ann. ACM‐SIAM Symp. Discrete Algorithms, Soc. Ind. Appl. Math., New York, NY, 2008, pp. 982-991. · Zbl 1192.68482 |
| [16] | M. X.Goemans, Improved approximation algorithms for scheduling with release dates, Proc. 8th Ann. ACM‐SIAM Symp. Discrete Algorithms, Soc. Ind. Appl. Math., New Orleans, LA, 1997, pp. 591-598. · Zbl 1321.68502 |
| [17] | M. X.Goemans and J.Kleinberg, An improved approximation ratio for the minimum latency problem, Math. Program.82 (1998), 111-124. · Zbl 0920.90138 |
| [18] | M. X.Goemans et al., Single machine scheduling with release dates, SIAM J. Discrete Math.15 (2002), 165-192. · Zbl 1009.90096 |
| [19] | R. L.Graham et al., Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math.5 (1979), 287-326. · Zbl 0411.90044 |
| [20] | E.Günther et al.A new approach to online scheduling: Approximating the optimal competitive ratio, Proc. 24th Ann. ACM‐SIAM Symp. Discrete Algorithms, Soc. Ind. Appl. Math., New Orleans, Louisiana, 2013, pp. 118-128. · Zbl 1421.68247 |
| [21] | L. A.Hall et al., Scheduling to minimize average completion time: Off‐line and on‐line approximation algorithms, Math. Oper. Res.22 (1997), 513-544. · Zbl 0883.90064 |
| [22] | P.Jaillet and X.Lu, Online traveling salesman problems with service flexibility, Networks58 (2011), 137-146. · Zbl 1229.90164 |
| [23] | P.Jaillet and M. R.Wagner, Online routing problems: Value of advanced information as improved competitive ratios, Transport. Sci.40 (2006), 200-210. |
| [24] | P.Jaillet and M. R.Wagner, Online vehicle routing problems: A survey, The vehicle routing problem: Latest advances and new challenges, (B.Golden (ed.), S.Raghavan (ed.), and E.Wasil (ed.), eds), Springer, New York, NY, 2008, pp. 221-237. · Zbl 1187.90055 |
| [25] | P.Jaillet and M. R.Wagner, Almost sure asymptotic optimality for online routing and machine scheduling problems, Networks55 (2010), 2-12. · Zbl 1211.68517 |
| [26] | K.Jain et al., Greedy facility location algorithms analyzed using dual fitting with factor‐revealing LP, J. ACM50 (2003), 795-824. · Zbl 1325.90060 |
| [27] | K.Jain, M.Mahdian, and A.Saberi, A new greedy approach for facility location problems, Proc. 34th Ann. ACM Symp. Theor. Comput., Assoc. Comput. Machinery, New York, NY, 2002, pp. 731-740. · Zbl 1192.90106 |
| [28] | D. W.Kim et al., Unrelated parallel machine scheduling with setup times using simulated annealing, Robot. Comput. Integr. Manuf.18 (2002), 223-231. |
| [29] | S.Kim and P.Bobrowski, Impact of sequence‐dependent setup time on job shop scheduling performance, Int. J. Prod. Res.32 (1994), 1503-1520. · Zbl 0901.90130 |
| [30] | E.Koutsoupias and C.H.Papadimitriou, On the \(k\)‐server conjecture, J. ACM42 (1995), 971-983. · Zbl 0885.68075 |
| [31] | S. O.Krumke et al., News from the online traveling repairman, Theor. Comput. Sci.295 (2003), 279-294. · Zbl 1044.68069 |
| [32] | M.Lipmann, On‐line routing problems, Ph.D. Thesis, Technische Universiteit Eindhoven, 2003. |
| [33] | P.Liu and X.Lu, On‐line scheduling of parallel machines to minimize total completion times, Comput. Oper. Res.36 (2009), 2647-2652. · Zbl 1175.90177 |
| [34] | M.Mahdian, H.Nazerzadeh, and A.Saberi, Allocating online advertisement space with unreliable estimates, Proc. 8th ACM Conf. Electron. Commer., Assoc. Comput. Machinery, San Diego, CA, 2007, pp. 288-294. |
| [35] | M.Mahdian and Q.Yan, Online bipartite matching with random arrivals: An approach based on strongly factor‐revealing LPs, Proc. 43rd Ann. ACM Symp. Theor. Comput., Assoc. Comput. Machinery, San Jose, CA, 2011, pp. 597-606. · Zbl 1288.68288 |
| [36] | M.Mahdian, Y.Ye, and J.Zhang, Improved approximation algorithms for metric facility location problems, 5th Int. Workshop, Approx. 2002 Proc., Lecture Notes in Computer Science, vol. 2462, Springer, Berlin, 2002, pp. 229-242. · Zbl 1013.90115 |
| [37] | N.Megow and A. S.Schulz, On‐line scheduling to minimize average completion time revisited, Oper. Res. Lett.32 (2004), 485-490. · Zbl 1054.90037 |
| [38] | N.Megow, M.Uetz, and T.Vredeveld, Models and algorithms for stochastic online scheduling, Math. Oper. Res.31 (2006), 513-525. · Zbl 1278.90182 |
| [39] | V.Mirrokni, S.Oveis Gharan, and M.Zadimoghaddam, Simultaneous approximations for adversarial and stochastic online budgeted allocation, Proc. 23rd Ann. ACM‐SIAM Symp. Discrete Algorithms, Soc. Ind. Appl. Math., Kyoto, Japan, 2012, pp. 1690-1701. · Zbl 1422.68324 |
| [40] | E.Nowicki and S.Zdrzałka, A survey of results for sequencing problems with controllable processing times, Discrete Appl. Math.26 (1990), 271-287. · Zbl 0693.90056 |
| [41] | C.Phillips, C.Stein, and J.Wein, Scheduling jobs that arrive over time, Algorithms and data structures, (S. G.Akl (ed.)et al. (ed.) eds.), Springer Berlin Heidelberg, 1995, pp. 86-97. · Zbl 1502.68371 |
| [42] | M. L.Pinedo, Scheduling: Theory, algorithms, and systems, Springer International Publishing, New York, NY, 2016. · Zbl 1332.90002 |
| [43] | D.Shabtay, and G.Steiner, A survey of scheduling with controllable processing times, Discrete Appl. Math.155 (2007), 1643-1666. · Zbl 1119.90022 |
| [44] | D. B.Shmoys, J.Wein, and D. P.Williamson, Scheduling parallel machines on‐line, SIAM J. Comput.24 (1995), 1313-1331. · Zbl 0845.68042 |
| [45] | V.Vinod and R.Sridharan, Dynamic job‐shop scheduling with sequence‐dependent setup times: Simulation modeling and analysis, Int. J. Adv. Manuf. Technol.36 (2008), 355-372. |
| [46] | Y.Yi and D.Wang, Soft computing for scheduling with batch setup times and earliness‐tardiness penalties on parallel machines, J. Intell. Manuf.14 (2003), 311-322. |
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.
