Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Scheduling
Published in: Journal of Scheduling 3/2018

13-04-2018 | Invited Survey Paper

A survey on makespan minimization in semi-online environments

Author: Leah Epstein

Published in: Journal of Scheduling | Issue 3/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We discuss variants of online scheduling on identical and uniformly related machines, where the objective is to minimize the makespan. All variants are such that some information regarding the input is provided in advance, and therefore these models are known as semi-online problems. Algorithms are analyzed with respect to the competitive ratio. We discuss the benefit arising from different kinds of available information and find that almost all variants allow one to reduce the competitive ratio significantly compared to the best possible competitive ratio for the corresponding pure online problem.
next article An implicit model for multi-activity shift scheduling problems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
Albers, S. (2002) On randomized online scheduling. In Proceedings of the on 34th annual ACM symposium on theory of computing (STOC2002) (pp. 134–143).
Albers, S. (2013). Recent advances for a classical scheduling problem. In Proceedings of the 40th international colloquium on automata, languages, and programming, (ICALP2013), part II (pp. 4–14).
Albers, S. (1999). Better bounds for online scheduling. SIAM Journal on Computing, 29(2), 459–473.CrossRef
Albers, S., & Hellwig, M. (2012). Semi-online scheduling revisited. Theoretical Computer Science, 443, 1–9.CrossRef
Albers, S., & Hellwig, M. (2017a). On the value of job migration in online makespan minimization. Algorithmica, 79(2), 598–623.CrossRef
Albers, S., & Hellwig, M. (2017b). Online makespan minimization with parallel schedules. Algorithmica, 78(2), 492–520.CrossRef
Andrews, M., Goemans, M. X., & Zhang, L. (1999). Improved bounds for on-line load balancing. Algorithmica, 23(4), 278–301.CrossRef
Angelelli, E. (2000). Semi on-line scheduling on two parallel processors with known sum and lower bound on the size of the tasks. Central European Journal of Operations Research, 8(4), 285–295.
Angelelli, E., Nagy, Á. B., Speranza, M. G., & Tuza, Z. (2004). The on-line multiprocessor scheduling problem with known sum of the tasks. Journal of Scheduling, 7(6), 421–428.CrossRef
Angelelli, E., Nagy, Á. B., Speranza, M. G., & Tuza, Z. (2007). Semi on-line scheduling on three processors with known sum of the tasks. Journal of Scheduling, 10(4), 263–269.CrossRef
Angelelli, E., Speranza, M. G., & Tuza, Z. (2003). Semi-on-line scheduling on two parallel processors with an upper bound on the items. Algorithmica, 37(4), 243–262.CrossRef
Angelelli, E., Speranza, M. G., & Tuza, Z. (2006). New bounds and algorithms for on-line scheduling: Two identical processors, known sum and upper bound on the tasks. Discrete Mathematics and Theoretical Computer Science, 8(1), 1–16.
Angelelli, E., Speranza, M. G., & Tuza, Z. (2008). Semi-online scheduling on two uniform processors. Theoretical Computer Science, 393(1–3), 211–219.CrossRef
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S. A., & Waarts, O. (1997). On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM, 44(3), 486–504.CrossRef
Azar, Y., & Regev, O. (2001). On-line bin-stretching. Theoretical Computer Science, 268(1), 17–41.CrossRef
Baram, G., & Tamir, T. (2014). Reoptimization of the minimum total flow-time scheduling problem. Sustainable Computing: Informatics and Systems, 4(4), 241–251.
Bar-Noy, A., Freund, A., & Naor, J. (2000). New algorithms for related machines with temporary jobs. Journal of Scheduling, 3(5), 259–272.CrossRef
Bartal, Y., Fiat, A., Karloff, H. J., & Vohra, R. (1995). New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51(3), 359–366.CrossRef
Bartal, Y., Karloff, H. J., & Rabani, Y. (1994). A better lower bound for on-line scheduling. Information Processing Letters, 50(3), 113–116.CrossRef
Berman, P., Charikar, M., & Karpinski, M. (2000). On-line load balancing for related machines. Journal of Algorithms, 35(1), 108–121.CrossRef
Böhm, M., Sgall, J., van Stee, R., & Veselý, P. (2017a). Online bin stretching with three bins. Journal of Scheduling, 20(6), 601–621.CrossRef
Böhm, M., Sgall, J., van Stee, R., & Veselý, P. (2017b). A two-phase algorithm for bin stretching with stretching factor 1.5. Journal of Combinaorial. Optimization, 34(3), 810–828.
Boyar, J., Favrholdt, L. M., Kudahl, C., & Mikkelsen, J. W. (2016). Weighted online problems with advice. In Proceedings of the 27th international workshop on combinatorial algorithms (IWOCA2016) (pp. 179–190).
Cai, S.-Y., & Yang, Q.-F. (2011). Semi-online scheduling on two uniform machines with the known largest size. Journal of Combinatorial Optimization, 21(4), 393–408.CrossRef
Cao, Q., Cheng, T., Wan, G., & Li, Y. (2012). Several semi-online scheduling problems on two identical machines with combined information. Theoretical Computer Science, 457, 35–44.CrossRef
Cao, Q., & Liu, Z. (2010a). Online scheduling with reassignment on two uniform machines. Theoretical Computer Science, 411(31–33), 2890–2898.CrossRef
Cao, Q., & Liu, Z. (2010b). Semi-online scheduling with known maximum job size on two uniform machines. Journal of Combinatorial Optimization, 20(4), 369–384.CrossRef
Cao, Q., & Liu, Z. (2016). Semi-online scheduling with bounded job sizes on two uniform machines. Theoretical Computer Science, 652, 1–17.CrossRef
Cao, Q., Liu, Z., & Cheng, T. C. E. (2011). Semi-online scheduling with known partial information about job sizes on two identical machines. Theoretical Computer Science, 412(29), 3731–3737.CrossRef
Cao, Q., & Wan, G. (2016). Semi-online scheduling with combined information on two identical machines in parallel. Journal of Combinatorial Optimization, 31(2), 686–695.CrossRef
Chandrasekaran, R., Chen, B., Galambos, G., Narayanan, P. R., & van Vliet, A. (1997). A note on “an on-line scheduling heuristic with better worst case ratio than Graham’s list scheduling”. SIAM Journal on Computing, 26(3), 870–872.CrossRef
Cheng, T. C. E., Kellerer, H., & Kotov, V. (2005). Semi-on-line multiprocessor scheduling with given total processing time. Theoretical Computer Science, 337(1–3), 134–146.CrossRef
Cheng, T. C. E., Kellerer, H., & Kotov, V. (2012). Algorithms better than LPT for semi-online scheduling with decreasing processing times. Operations Research Letters, 40(5), 349–352.CrossRef
Cheng, T. C. E., Ng, C. T., & Kotov, V. (2006). A new algorithm for online uniform-machine scheduling to minimize the makespan. Information Processing Letters, 99(3), 102–105.CrossRef
Chen, X., Lan, Y., Benko, A., Dósa, G., & Han, X. (2011). Optimal algorithms for online scheduling with bounded rearrangement at the end. Theoretical Computer Science, 412(45), 6269–6278.CrossRef
Chen, B., van Vliet, A., & Woeginger, G. J. (1994). New lower and upper bounds for on-line scheduling. Operations Research Letters, 16(4), 221–230.CrossRef
Cho, Y., & Sahni, S. (1980). Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9(1), 91–103.CrossRef
Ding, N., Lan, Y., Chen, X., Dósa, G., Guo, H., & Han, X. (2014). Online minimum makespan scheduling with a buffer. International Journal of Foundations of Computer Science, 25(05), 525–536.CrossRef
Dobson, G. (1984). Scheduling independent tasks on uniform processors. SIAM Journal on Computing, 13(4), 705–716.CrossRef
Dohrau, J. (2015). Online makespan scheduling with sublinear advice. In Proceedings of the 41st international conference on current trends in theory and practice of computer science (SOFSEM2015) (pp. 177–188).
Dolgui, A., Kotov, V., Nekrashevich, A., & Quilliot, A. (2018). General parametric scheme for the online uniform machine scheduling problem with two different speeds. Information Processing Letters, 134, 18–23.CrossRef
Dósa, G., & Epstein, L. (2010). Online scheduling with a buffer on related machines. Journal of Combinatorial Optimization, 20(2), 161–179.CrossRef
Dósa, G., Fügenschuh, A., Tan, Z., Tuza, Z., & Węsek, K. (2018). Tight upper bounds for semi-online scheduling on two uniform machines with known optimum. Central European Journal of Operations Research, 26(1), 161–180.CrossRef
Dósa, G., & He, Y. (2004). Semi-online algorithms for parallel machine scheduling problems. Computing, 72(3–4), 355–363.
Dósa, G., Speranza, M. G., & Tuza, Z. (2011). Two uniform machines with nearly equal speeds: Unified approach to known sum and known optimum in semi on-line scheduling. Journal of Combinatorial Optimization, 21(4), 458–480.CrossRef
Dósa, G., Wang, Y., Han, X., & Guo, H. (2011). Online scheduling with rearrangement on two related machines. Theoretical Computer Science, 412(8–10), 642–653.CrossRef
Ebenlendr, T., & Sgall, J. (2009). Optimal and online preemptive scheduling on uniformly related machines. Journal of Scheduling, 12(5), 517–527.CrossRef
Ebenlendr, T., & Sgall, J. (2011). Semi-online preemptive scheduling: One algorithm for all variants. Theory of Computing Systems, 48(3), 577–613.CrossRef
Ebenlendr, T., & Sgall, J. (2015). A lower bound on deterministic online algorithms for scheduling on related machines without preemption. Theory of Computing Systems, 56(1), 73–81.CrossRef
Ehlers, T., & Jansen, K. (2013). Online-scheduling on identical machines with bounded migration. In Proceedings of the 15th international symposium on symbolic and numeric algorithms for scientific computing (SYNASC2013) (pp. 361–366). New York: IEEE.
Englert, M. (2012). An overview of some results for reordering buffers. Computer Science-Research and Development, 27, 217–223.CrossRef
Englert, M., Özmen, D., & Westermann, M. (2014). The power of reordering for online minimum makespan scheduling. SIAM Journal on Computing, 43(3), 1220–1237.CrossRef
Epstein, L. (2003). Bin stretching revisited. Acta Informatica, 39(2), 97–117.CrossRef
Epstein, L., & Favrholdt, L. M. (2005). Optimal non-preemptive semi-online scheduling on two related machines. Journal of Algorithms, 57(1), 49–73.CrossRef
Epstein, L., Noga, J., Seiden, S. S., Sgall, J., & Woeginger, G. J. (2001). Randomized online scheduling on two uniform machines. Journal of Scheduling, 4(2), 71–92.CrossRef
Epstein, L., & Ye, D. (2007). Semi-online scheduling with “end of sequence” information. Journal of Combinatorial Optimization, 14(1), 45–61.CrossRef
Faigle, U., Kern, W., & Turán, G. (1989). On the performance of online algorithms for partition problems. Acta Cybernetica, 9(2), 107–119.
Fleischer, R., & Wahl, M. (2000). Online scheduling revisited. Journal of Scheduling, 3(6), 343–353.CrossRef
Friesen, D. K. (1987). Tighter bounds for LPT scheduling on uniform processors. SIAM Journal on Computing, 16(3), 554–560.CrossRef
Gabay, M., Brauner, N., & Kotov, V. (2017). Improved lower bounds for the online bin stretching problem. 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 15(2), 183–199.CrossRef
Gabay, M., Kotov, V., & Brauner, N. (2015). Online bin stretching with bunch techniques. Theoretical Computer Science, 602, 103–113.CrossRef
Galambos, G., & Woeginger, G. J. (1993). An on-line scheduling heuristic with better worst case ratio than Graham’s list scheduling. SIAM Journal on Computing, 22(2), 349–355.CrossRef
Gatto, M., & Widmayer, P. (2011). On robust online scheduling algorithms. Journal of Scheduling, 14(2), 141–156.CrossRef
Gonzalez, T. F., Ibarra, O. H., & Sahni, S. (1977). Bounds for LPT schedules on uniform processors. SIAM Journal on Computing, 6(1), 155–166.CrossRef
Gormley, T., Reingold, N., Torng, E., & Westbrook, J. (2000). Generating adversaries for request-answer games. In Proceedings of the 11th annual ACM-SIAM symposium on discrete algorithms (SODA2000) (pp. 564–565).
Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9), 1563–1581.CrossRef
Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 17(2), 416–429.CrossRef
Han, F., Tan, Z., & Yang, Y. (2012). On the optimality of list scheduling for online uniform machines scheduling. Optimization Letters, 6(7), 1551–1571.CrossRef
He, Y. (2000). The optimal on-line parallel machine scheduling. Computers and Mathematics with Applications, 39(7–8), 117–121.CrossRef
He, Y., & Dósa, G. (2005). Semi-online scheduling jobs with tightly-grouped processing times on three identical machines. Discrete Applied Mathematics, 150(1–3), 140–159.CrossRef
He, Y., & Dósa, G. (2007). Extension of algorithm list scheduling for a semi-online scheduling problem. Central European Journal of Operations Research, 15(1), 97–104.CrossRef
He, Y., Yang, Q., Tan, Z., & Yao, E. (2002). Algorithms for semi on-line multiprocessor scheduling problems. Journal of Zhejiang University-Science A, 3(1), 60–64.CrossRef
He, Y., & Zhang, G. (1999). Semi on-line scheduling on two identical machines. Computing, 62(3), 179–187.CrossRef
Hochbaum, D. S., & Shmoys, D. B. (1987). Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the ACM, 34(1), 144–162.CrossRef
Jeż, Ł., Schwartz, J., Sgall, J., & Békési, J. (2013). Lower bounds for online makespan minimization on a small number of related machines. Journal of Scheduling, 16(5), 539–547.CrossRef
Karger, D. R., Phillips, S. J., & Torng, E. (1996). A better algorithm for an ancient scheduling problem. Journal of Algorithms, 20(2), 400–430.CrossRef
Kellerer, H., & Kotov, V. (2013). An efficient algorithm for bin stretching. Operations Research Letters, 41(4), 343–346.CrossRef
Kellerer, H., Kotov, V., & Gabay, M. (2015). An efficient algorithm for semi-online multiprocessor scheduling with given total processing time. Journal of Scheduling, 18(6), 623–630.CrossRef
Kellerer, H., Kotov, V., Speranza, M. G., & Tuza, Z. (1997). Semi on-line algorithms for the partition problem. Operations Research Letters, 21(5), 235–242.CrossRef
Kovács, A. (2005). Fast monotone 3-approximation algorithm for scheduling related machines. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA2005) (pp. 616–627).
Kovács, A. (2009). Tighter approximation bounds for LPT scheduling in two special cases. Journal of Discrete Algorithms, 7(3), 327–340.CrossRef
Kovács, A. (2010). New approximation bounds for LPT scheduling. Algorithmica, 57(2), 413–433.CrossRef
Lee, K., Leung, J. Y., & Pinedo, M. L. (2013). Makespan minimization in online scheduling with machine eligibility. Annals of Operations Research, 204(1), 189–222.CrossRef
Lee, K., & Lim, K. (2013). Semi-online scheduling problems on a small number of machines. Journal of Scheduling, 16(5), 461–477.CrossRef
Li, S., Zhou, Y., Sun, G., & Chen, G . (2007) Study on parallel machine scheduling problem with buffer. In Proceedings of the 2nd international multisymposium on computer and computational sciences (IMSCCS2007) (pp. 278–281).
Li, R., & Shi, L. (1998). An on-line algorithm for some uniform processor scheduling. SIAM Journal on Computing, 27(2), 414–422.CrossRef
Liu, W., Sidney, J. B., & van Vliet, A. (1996). Ordinal algorithms for parallel machine scheduling. Operations Research Letters, 18(5), 223–232.CrossRef
Liu, M., Xu, Y., Chu, C., & Zheng, F. (2009). Online scheduling on two uniform machines to minimize the makespan. Theoretical Computer Science, 410(21–23), 2099–2109.CrossRef
Min, X., Liu, J., & Wang, Y. (2011). Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines. Information Processing Letters, 111(9), 423–428.CrossRef
Mireault, P., Orlin, J. B., & Vohra, R. V. (1997). A parametric worst case analysis of the LPT heuristic for two uniform machines. Operations Research, 45, 116–125.CrossRef
Motwani, R., Phillips, S. J., & Torng, E. (1994). Non-clairvoyant scheduling. Theoretical Computer Science, 130(1), 17–47.CrossRef
Musitelli, A., & Nicoletti, J.-M. (2011). Competitive ratio of list scheduling on uniform machines and randomized heuristics. Journal of Scheduling, 14(1), 89–101.CrossRef
Ng, C. T., Tan, Z., He, Y., & Cheng, T. C. E. (2009). Two semi-online scheduling problems on two uniform machines. Theoretical Computer Science, 410(8–10), 776–792.CrossRef
Renault, M. P., Rosén, A., & van Stee, R. (2015). Online algorithms with advice for bin packing and scheduling problems. Theoretical Computer Science, 600, 155–170.CrossRef
Rudin III, J.F. (2001) Improved bounds for the on-line scheduling problem. PhD thesis, The University of Texas at Dallas.
Rudin, J. F, I. I. I., & Chandrasekaran, R. (2003). Improved bounds for the online scheduling problem. SIAM Journal on Computing, 32(3), 717–735.CrossRef
Sanders, P., Sivadasan, N., & Skutella, M. (2009). Online scheduling with bounded migration. Mathematics of Operations Research, 34(2), 481–498.CrossRef
Schieber, B., Shachnai, H., Tamir, G., & Tamir, T. (2018). A theory and algorithms for combinatorial reoptimization. Algorithmica, 80(2), 576–607.CrossRef
Seiden, S. S., Sgall, J., & Woeginger, G. J. (2000). Semi-online scheduling with decreasing job sizes. Operations Research Letters, 27(5), 215–221.CrossRef
Sgall, J. (1998). On-line scheduling. In A. Fiat & G. J. Woeginger (Eds.), Online algorithms, the state of the art (pp. 196–231). Berlin: Springer.CrossRef
Shmoys, D. B., Wein, J., & Williamson, D. P. (1995). Scheduling parallel machines on-line. SIAM Jounral on Computing, 24(6), 1313–1331.CrossRef
Sun, H., & Fan, R. (2013). Improved semi-online makespan scheduling with a reordering buffer. Information Processing Letters, 113(12), 434–439.CrossRef
Tan, Z., & He, Y. (2001). Semi-on-line scheduling with ordinal data on two uniform machines. Operations Research Letters, 28(5), 221–231.CrossRef
Tan, Z., & He, Y. (2002). Semi-on-line problems on two identical machines with combined partial information. Operations Research Letters, 30(6), 408–414.CrossRef
Tan, Z., & He, Y. (2007). Semi-online scheduling problems on two identical machines with inexact partial information. Theoretical Computer Science, 377(1–3), 110–125.CrossRef
Tan, Z., & Li, R. (2015). Pseudo lower bounds for online parallel machine scheduling. Operations Research Letters, 43(5), 489–494.CrossRef
Tan, Z., & Yu, S. (2008). Online scheduling with reassignment. Operations Research Letters, 36(2), 250–254.CrossRef
Tan, Z., & Zhang, A. (2013). Online and semi-online scheduling. In P. M. Pardalos, D.-Z. Du, & R. Graham (Eds.), Handbook of combinatorial optimization (pp. 2191–2252). Berlin: Springer.CrossRef
Wang, Y., Benko, A., Chen, X., Dósa, G., Guo, H., Han, X., et al. (2012). Online scheduling with one rearrangement at the end: Revisited. Information Processing Letters, 112(16), 641–645.CrossRef
Westbrook, J. (2000). Load balancing for response time. Jounral of Algorithms, 35(1), 1–16.CrossRef
Wu, Y., Tan, Z., & Yang, Q. (2007). Optimal semi-online scheduling algorithms on a small number of machines. In Proceedings of the first international symposium on combinatorics, algorithms, probabilistic and experimental methodologies (ESCAPE2007) (pp. 504–515).
Wu, Y., Yang, Q., & Huang, Y. (2010). Semi-online bin stretching with non-increasing job processing times. In Proceedings of the international conference on computer application and system modeling (ICCASM2010) (Vol. 10, pp. V10–562–V10–566). New York: IEEE.
Zhang, G. (1997). A simple semi on-line algorithm for \({P2}//{{C}_{\max }}\) with a buffer. Information Processing Letters, 61, 145–148.CrossRef
Zhang, G., & Ye, D. (2002). A note on on-line scheduling with partial information. Computers and Mathematics with Applications, 44(3–4), 539–543.CrossRef
Metadata
Title
A survey on makespan minimization in semi-online environments
Author
Leah Epstein
Publication date
13-04-2018
Publisher
Springer US
Published in
Journal of Scheduling / Issue 3/2018
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-018-0567-z

Other articles of this Issue 3/2018

Journal of Scheduling 3/2018 Go to the issue

OriginalPaper

New strategies for stochastic resource-constrained project scheduling

OriginalPaper

The triangle scheduling problem

OriginalPaper

Algorithms for a special class of state-dependent shortest path problems with an application to the train routing problem

OriginalPaper

An implicit model for multi-activity shift scheduling problems

OriginalPaper

Improved algorithms for resource allocation under varying capacity

OriginalPaper

Single machine scheduling with job delivery to multiple customers

Premium Partner

    Image Credits