Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875407 | Theoretical Computer Science | 2018 | 12 Pages |
Abstract
An on-line scheduling problem on m uniform parallel-batch machines to minimize the makespan is considered in this paper. Each machine can process infinite jobs as a batch at a time. Jobs arrive over time and have equal lengths denoted by 1. Compared to parallel machines, uniform machines are more difficult to deal with because they have different processing speeds. There are two types of machines in our model. The lower bound on the competitive ratio is characterized by some complicated algebraic equations. And a best possible on-line algorithm matching the lower bound is constructed and proved in this paper.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wenhua Li, Xing Chai, Yali Song,