Online scheduling with a buffer on related machines |
| |
Authors: | György Dósa Leah Epstein |
| |
Institution: | (1) Department of Mathematics, University of Haifa, 31905 Haifa, Israel;(2) College of Computer Science, Zhejiang University, Hangzhou, 310027, China |
| |
Abstract: | Online scheduling with a buffer is a semi-online problem which is strongly related to the basic online scheduling problem. Jobs arrive one by one and are
to be assigned to parallel machines. A buffer of a fixed capacity K is available for storing at most K input jobs. An arriving job must be either assigned to a machine immediately upon arrival, or it can be stored in the buffer
for unlimited time. A stored job which is removed from the buffer (possibly, in order to allocate a space in the buffer for
a new job) must be assigned immediately as well. We study the case of two uniformly related machines of speed ratio s≥1, with the goal of makespan minimization. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|