Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

On-line scheduling problems are studied with jobs organized in a number of sequences called threads. Each job becomes available as soon as a scheduling decision is made on all preceding jobs in the same thread. We consider two different on-line paradigms. The first one models a sort of batch process: a schedule is constructed, in an on-line way, which is to be executed later. The other one models a real-time planning situation: jobs are immediately executed at the moment they are assigned to a machine. The classical objective functions of minimizing makespan and minimizing average completion time of the jobs are studied. We establish a fairly complete set of results for these problems. One of the highlights is that List Scheduling is a best possible algorithm for the makespan problem under the real-time model if the number of machines does not exceed the number of threads by more than 1. Another one is a polynomial time best possible algorithm for minimizing the average completion time on a single machine under both on-line paradigms.

Registro:

Documento: Artículo
Título:On-line multi-threaded Scheduling
Autor:Feuerstein, E.; Mydlarz, M.; Stougie, L.
Filiación:Departamento de Computación, Fac. de Ciencias Exactes y Naturales, Universidad de Buenos Aires, Argentina
Department of Computer Science, Rutgers University, Piscataway, NJ 08854-8019, United States
Combinational Optimization Group, Faculty of Mathematics, Technical University Eindhoven, P. O. Box 513, 5600 MB Eindhoven, Netherlands
Ctr. for Math. and Computer Science, P. O. Box 94079, 1090 GB Amsterdam, Netherlands
Palabras clave:Competitive analysis; Multiple threads; On-line algorithms; Scheduling problems; Algorithms; Constraint theory; Decision making; Information retrieval; Mathematical models; Problem solving; Program processors; Real time systems; Scheduling; Competitive analysis; Multiple threads; On-line algorithms; Scheduling problems; Online systems
Año:2003
Volumen:6
Número:2
Página de inicio:167
Página de fin:181
DOI: http://dx.doi.org/10.1023/A:1022987804726
Título revista:Journal of Scheduling
Título revista abreviado:J. Scheduling
ISSN:10946136
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10946136_v6_n2_p167_Feuerstein

Referencias:

  • Albers, S., Better bounds for on-line scheduling (1997) Proc. 29th Annu. ACM Symp. on the Theory of Computing (STOC), pp. 130-139
  • Alborzi, H., Torng, E., Uthaisombut, P., Wagner, S., The k-client problem (1997) Proc. 8th Annu. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 73-82
  • Bartal, Y., Fiat, A., Karloff, H., Vohra, R., New algorithms for an ancient scheduling problem (1995) J. Comput. Syst. Sci., 51, pp. 359-366
  • Borodin, A., El-Yaniv, R., (1998) On-line Computation and Competitive Analysis, , Cambridge University Press, Boston
  • Feuerstein, E., (1995) On-line Paging of Structured Data and Multi-threaded Paging, , Ph.D. Thesis, Università di Roma," La Sapienza,"
  • Feuerstein, E., De Loma, A.S., On multi-threaded paging (1996) Proc. 7th Annu. Int. Symp. on Algorithms and Computation (ISAAC'96), Lecture Notes in Computer Science, 1178, pp. 417-426. , Springer-Verlag, Berlin
  • Feuerstein, E., De Loma, A.S., (1998) Different Competitiveness Measures for Multi-threaded Paging, , International Workshop on On-line Algorithms, OLA98, Udine, Italy
  • Fleischer, R., Wahl, M., On-line scheduling revisited (2000) J. Sched, 3, pp. 343-353
  • Graham, R.L., Bounds for certain multiprocessing anomalies (1966) Bell Syst. Tech. J., 45, pp. 1563-1581
  • Karger, D.R., Philips, S.J., Torng, E., A better algorithm for an ancient scheduling problem (1996) J. Algorithms, 20, pp. 400-430
  • Kimbrel, T., Online and offline preemptive two-machine job shop scheduling (1999) IBM Research Report RC 21520
  • Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., Shmoys, D.B., Sequencing and scheduling: Algorithms and complexity (1993) Handbooks in Operations Research, 4. , S. C. Graves, A. H. G. Rinnooy Kan and P. H. Zipkin (eds.), North Holland, Amsterdam
  • Sgall, J., On-line scheduling (1998) On-line Algorithms - The State of the Art, Lecture Notes in Computer Science, 1442, pp. 196-231. , A. Fiat and G. Woeginger (eds.), Springer-Verlag, Berlin
  • Smith, W.E., Various optimizers for single-stage production (1956) Naval Res, Logistics Q., 3, pp. 59-66

Citas:

---------- APA ----------
Feuerstein, E., Mydlarz, M. & Stougie, L. (2003) . On-line multi-threaded Scheduling. Journal of Scheduling, 6(2), 167-181.
http://dx.doi.org/10.1023/A:1022987804726
---------- CHICAGO ----------
Feuerstein, E., Mydlarz, M., Stougie, L. "On-line multi-threaded Scheduling" . Journal of Scheduling 6, no. 2 (2003) : 167-181.
http://dx.doi.org/10.1023/A:1022987804726
---------- MLA ----------
Feuerstein, E., Mydlarz, M., Stougie, L. "On-line multi-threaded Scheduling" . Journal of Scheduling, vol. 6, no. 2, 2003, pp. 167-181.
http://dx.doi.org/10.1023/A:1022987804726
---------- VANCOUVER ----------
Feuerstein, E., Mydlarz, M., Stougie, L. On-line multi-threaded Scheduling. J. Scheduling. 2003;6(2):167-181.
http://dx.doi.org/10.1023/A:1022987804726