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

Registro:

Documento: Artículo
Título:Multiprocessor scheduling under precedence constraints: Polyhedral results
Autor:Coll, P.E.; Ribeiro, C.C.; De Souza, C.C.
Filiación:Universidad de Buenos Aires, Departamento de Computación, Ciudad Universitaria, Pabellón I, 1428 Buenos Aires, Argentina
Department of Computer Science, Catholic University of Rio de Janeiro, Rua Marques de Sao Vicente, 225, Rio de Janeiro, RJ 22453-900, Brazil
University of Campinas, Institute of Computing, Caixa Postal 6176, Campinas, SP 13084-971, Brazil
Palabras clave:Multiprocessors; Order polytopes; Polyhedral combinatorics; Precedence constraints; Scheduling; Valid inequalities; Combinatorial mathematics; Integer programming; Problem solving; Set theory; Order polytopes; Polyhedral combinatorics; Valid inequalities; Scheduling
Año:2006
Volumen:154
Número:5 SPEC ISS
Página de inicio:770
Página de fin:801
DOI: http://dx.doi.org/10.1016/j.dam.2004.07.009
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v154_n5SPECISS_p770_Coll

Referencias:

  • Bertsekas, D.P., Tsitsiklis, J.N., (1989) Parallel and Distributed Computation - Numerical Methods, , Prentice-Hall Englewood Cliffs, NJ
  • Blazewicz, J., Cellary, W., Slowinski, R., Weglarz, J., (1986) Scheduling under Resource Constraints - Deterministic Models, , J.C. Baltzer AG Basel
  • Christof, T., Reinelt, G., Low-dimensional linear ordering polytopes (1997) Technical Report, , Universität Heidelberg
  • Coffman, E.G., Denning, P.J., (1973) Operating Systems Theory, , Prentice-Hall Englewood Cliffs, NJ
  • Coll, P.E., (2002) A Polyhedral Approach to Scheduling Unrelated Processors under Precedence Constrains, Doctorate Dissertation, , University of Buenos Aires Argentina
  • Cook, W.J., Cunnigham, W.H., Pulleyblank, W.R., Schrijver, A., (1998) Combinatorial Optimization, , Wiley New York
  • Doignon, J.P., Samuel, F., Facets of the weak order polytope derived from the induced partition projection (2002) SIAM J. Discrete Math., 15 (1), pp. 112-121
  • Garey, M.R., Johnson, D.S., Strong NP-completeness results: Motivation, examples and implications (1978) J. ACM, 25, pp. 499-508
  • Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W.H. Freeman and Company San Francisco
  • Grötschel, M., Jünger, M., Reinelt, G., A cutting plane algorithm for the linear ordering problem (1984) Oper. Res., 32, pp. 1195-1220
  • Grötschel, M., Jünger, M., Reinelt, G., Facets of the linear ordering polytope (1985) Math. Program., 33, pp. 43-60
  • Grötschel, M., Jünger, M., Reinelt, G., On the acyclic subgraph polytope (1985) Math. Program., 33, pp. 28-42
  • Grötschel, M., Wakabayashi, Y., A cutting plane algorithm for a clustering problem (1989) Math. Program. Ser. B, 45, pp. 59-96
  • Grötschel, M., Wakabayashi, Y., Facets of the clique partitioning polytope (1990) Math. Program., 47, pp. 367-387
  • Gurgel, M.A.M.C., (1992) Poliedros de Grafos Transitivos, , Ph.D. Thesis, Department of Computing Science, University of São Paulo
  • Gurgel, M.A.M.C., Wakabayashi, Y., Adjacency of vertices of the complete pre-order polytope (1997) Discrete Math., 175 (1-3), pp. 163-172
  • Ibarra, O.H., Sohn, S.M., On mapping systolic algorithms onto the hypercube (1990) IEEE Trans. Parallel Distrib. Systems, 1, pp. 48-63
  • (1998) Using the CPLEX Callable Library, Version 6.0
  • Kitajima, J.P., (1992) Modèles Quantitatifs d'Algorithmes Parallèles, , Ph.D. Thesis, Institut National Polytechnique de Grenoble
  • Kitajima, J.P., Plateau, B., Bouvry, P., Trystram, D., A method and a tool for performance evaluation - A case study: Evaluating mapping strategies (1996) Technical Report, , Institut National Polytechnique de Grenoble
  • Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B., (1989) Sequencing and Scheduling: Algorithms and Complexity, , Report NFI 11.89/03, Eindhoven Institute of Technology, Department of Mathematics and Computer Science, Eindhoven
  • MacUlan, N., Porto, S.C.S., Ribeiro, C.C., De Souza, C.C., A new formulation for scheduling unrelated processors under precedence constraints (1999) RAIRO Rech. Opér., 33, pp. 87-90
  • Madal, S., Sinclair, J.B., Performance of synchronous parallel algorithms with regular structures (1991) IEEE Trans. Parallel Distrib. Systems, 2, pp. 105-116
  • Menascé, D.A., Porto, S.C.S., Processor assignment in heterogeneous parallel architectures (1992) Proceedings of the IEEE International Parallel Processing Symposium, pp. 186-191. , Beverly Hills
  • Müller, R., On the partial order polytope of a digraph (1996) Math. Program. Ser. A, 73, pp. 31-49
  • Porto, S.C., Kitajima, J.P., Ribeiro, C.C., Performance evaluation of a parallel tabu search task scheduling algorithm (2000) Parallel Comput., 26, pp. 73-90
  • Porto, S.C., Ribeiro, C.C., A tabu search approach to task scheduling on heterogeneous processors under precedence constraints (1995) Internat. J. High Speed Comput., 7, pp. 45-71
  • Porto, S.C., Ribeiro, C.C., Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints (1995) J. Heuristics, 1, pp. 207-223
  • Schulz, A.S., (1996) Polytopes and Scheduling, , Ph.D. Thesis, Technischen Universität Berlin
  • Thienel, S., (1995) ABACUS - A Branch-and-CUt System, , Ph.D. Thesis, Universitat zu Köln

Citas:

---------- APA ----------
Coll, P.E., Ribeiro, C.C. & De Souza, C.C. (2006) . Multiprocessor scheduling under precedence constraints: Polyhedral results. Discrete Applied Mathematics, 154(5 SPEC ISS), 770-801.
http://dx.doi.org/10.1016/j.dam.2004.07.009
---------- CHICAGO ----------
Coll, P.E., Ribeiro, C.C., De Souza, C.C. "Multiprocessor scheduling under precedence constraints: Polyhedral results" . Discrete Applied Mathematics 154, no. 5 SPEC ISS (2006) : 770-801.
http://dx.doi.org/10.1016/j.dam.2004.07.009
---------- MLA ----------
Coll, P.E., Ribeiro, C.C., De Souza, C.C. "Multiprocessor scheduling under precedence constraints: Polyhedral results" . Discrete Applied Mathematics, vol. 154, no. 5 SPEC ISS, 2006, pp. 770-801.
http://dx.doi.org/10.1016/j.dam.2004.07.009
---------- VANCOUVER ----------
Coll, P.E., Ribeiro, C.C., De Souza, C.C. Multiprocessor scheduling under precedence constraints: Polyhedral results. Discrete Appl Math. 2006;154(5 SPEC ISS):770-801.
http://dx.doi.org/10.1016/j.dam.2004.07.009