|
|||||
|
|
Lower bounds for online makespan minimization on a small number of related machines |
|
| Authors: | ?ukasz Je? Jarett Schwartz Ji?í Sgall József Békési |
| Affiliation: | 1. Institute of Computer Science, University of Wroc?aw, ul. Joliot-Curie 15, 50-383, Wroc?aw, Poland 2. Institute of Mathematics, Academy of Sciences of the Czech Republic, ?itná 25, 115 67, Praha 1, Czech Republic 3. Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, 11800, Praha 1, Czech Republic 4. Faculty of Mathematics and Physics, Computer Science Inst. of Charles University, Malostranské nám. 25, 11800, Praha 1, Czech Republic 5. Department of Applied Informatics, Gyula Juhász Faculty of Education, University of Szeged, POB 396, 6701, Szeged, Hungary |
| Abstract: | In online makespan minimization, the jobs characterized by their processing time arrive one-by-one and each has to be assigned to one of the m uniformly related machines. The goal is to minimize the length of the schedule. We prove new combinatorial lower bounds for m=4 and m=5, and computer-assisted lower bounds for m≤11. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |