Navegar

Colección

Datos Estadísticas

Artículo

Feuerstein, E.; Marchetti-Spaccamela, A.; Schalekamp, F.; Sitters, R.; Van Der Ster, S.; Stougie, L.; Van Zuylen, A. "Scheduling over scenarios on two machines" (2014) 20th International Computing and Combinatorics Conference, COCOON 2014. 8591 LNCS:559-571
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scenario is a subset of jobs that must be executed in that scenario and all scenarios are given explicitly. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. With this research into optimization problems over scenarios, we have opened a new and rich field of interesting problems. © 2014 Springer International Publishing Switzerland.

Registro:

Documento: Artículo
Título:Scheduling over scenarios on two machines
Autor:Feuerstein, E.; Marchetti-Spaccamela, A.; Schalekamp, F.; Sitters, R.; Van Der Ster, S.; Stougie, L.; Van Zuylen, A.
Ciudad:Atlanta, GA
Filiación:Departamento de Computación, FCEyN, UBA, Buenos Aires, Argentina
Sapienza University of Rome, Italy
Department of Mathematics, College of William and Mary, Williamsburg VA 23185, United States
Vrije Universiteit Amsterdam, Netherlands
CWI Amsterdam, Netherlands
Palabras clave:approximation; job scheduling; makespan minimization; scenarios; Approximation algorithms; Combinatorial mathematics; Optimization; Scheduling algorithms; Combinatorial mathematics; Optimization; Scheduling; Approximability; approximation; Job scheduling; Makespan minimization; Optimization problems; scenarios; Scheduling problem; Two machines; Approximation; Lower bounds; Scenarios; Scheduling; Approximation algorithms
Año:2014
Volumen:8591 LNCS
Página de inicio:559
Página de fin:571
DOI: http://dx.doi.org/10.1007/978-3-319-08783-2_48
Título revista:20th International Computing and Combinatorics Conference, COCOON 2014
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8591LNCS_n_p559_Feuerstein

Referencias:

  • Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M., (1999) Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, , Springer
  • Austrin, P., Guruswami, V., Hastad, J., (2 + e)-sat is np-hard (2013) Electronic Colloquium on Computational Complexity, TR13-159
  • Ben-Tal, A., Nemirovski, A., Robust optimization-methodology and applications (2002) Mathematical Programming, 92 (3), pp. 453-480
  • Bouyahia, Z., Bellalouna, M., Ghedira, K., Load balancing a priori strategy for the probabilistic weighted flowtime problem (2013) Comput. Ind. Eng., 64 (1), pp. 1-10
  • Bouyahia, Z., Bellalouna, M., Jaillet, P., Ghedira, K., A priori parallel machines scheduling (2010) Comput. Ind. Eng., 58 (3), pp. 488-500. , Supply, Production and Distribution Systems
  • Chekuri, C., Khanna, S., On multidimensional packing problems (2004) SIAM Journal on Computing, 33 (4), pp. 837-851
  • Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., Stougie, L., Universal sequencing on an unreliable machine (2012) SIAM Journal on Computing, 41, pp. 565-586
  • Feuerstein, E., Marchetti-Spaccamela, A., Schalekamp, F., Sitters, R., Van Der Ster, S., Stougie, L., Van Zuylen, A., (2014) Scheduling over Scenarios on Two Machines, , CoRR, abs/1404.4766
  • Garey, M.R., Johnson, D.S., (1990) Computers and Intractability; A Guide to the Theory of NP-Completeness, , W. H. Freeman & Co., New York
  • Goemans, M.X., Williamson, D.P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming (1995) J. ACM, 42 (6), pp. 1115-1145
  • Gupta, A., Pal, M., Ravi, R., Sinha, A., Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems (2011) SIAM Journal on Computing, 40 (5), pp. 1361-1401
  • Hastad, J., Some optimal inapproximability results (2001) J. ACM, 48 (4), pp. 798-859
  • Jaillet, P., A priori solution of a traveling salesman problem in which a random subset of the customers are visited (1988) Oper. Res., 36 (6), pp. 929-936
  • Karloff, H.J., Zwick, U., A 7/8-approximation algorithm for max 3sat? (1997) FOCS, pp. 406-415. , IEEE Computer Society
  • Khot, S., On the power of unique 2-prover 1-round games (2002) Proceedings of 34th Annual ACM Symposium on Theory of Computing, pp. 767-775
  • Khot, S., Kindler, G., Mossel, E., O'Donnell, R., Optimal inapproximability results for max-cut and other 2-variable csps? (2007) SIAM J. Comput., 37 (1), pp. 319-357
  • Zhang, J., Ye, Y., Han, Q., Improved approximations for max set splitting and max nae sat (2004) Discrete Applied Mathematics, 142 (1-3), pp. 133-149
  • Zwick, U., Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems (1999) STOC, pp. 679-687A4 -

Citas:

---------- APA ----------
Feuerstein, E., Marchetti-Spaccamela, A., Schalekamp, F., Sitters, R., Van Der Ster, S., Stougie, L. & Van Zuylen, A. (2014) . Scheduling over scenarios on two machines. 20th International Computing and Combinatorics Conference, COCOON 2014, 8591 LNCS, 559-571.
http://dx.doi.org/10.1007/978-3-319-08783-2_48
---------- CHICAGO ----------
Feuerstein, E., Marchetti-Spaccamela, A., Schalekamp, F., Sitters, R., Van Der Ster, S., Stougie, L., et al. "Scheduling over scenarios on two machines" . 20th International Computing and Combinatorics Conference, COCOON 2014 8591 LNCS (2014) : 559-571.
http://dx.doi.org/10.1007/978-3-319-08783-2_48
---------- MLA ----------
Feuerstein, E., Marchetti-Spaccamela, A., Schalekamp, F., Sitters, R., Van Der Ster, S., Stougie, L., et al. "Scheduling over scenarios on two machines" . 20th International Computing and Combinatorics Conference, COCOON 2014, vol. 8591 LNCS, 2014, pp. 559-571.
http://dx.doi.org/10.1007/978-3-319-08783-2_48
---------- VANCOUVER ----------
Feuerstein, E., Marchetti-Spaccamela, A., Schalekamp, F., Sitters, R., Van Der Ster, S., Stougie, L., et al. Scheduling over scenarios on two machines. Lect. Notes Comput. Sci. 2014;8591 LNCS:559-571.
http://dx.doi.org/10.1007/978-3-319-08783-2_48