Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433925 | Theoretical Computer Science | 2015 | 8 Pages |
Abstract
We consider the online scheduling problem on m parallel machines with eligibility constraints. The jobs arrive over time and have equal processing times. The objective is to minimize the makespan. We develop optimal deterministic online algorithms for the nested processing set case and the inclusive processing set case with an arbitrary number of machines, as well as the tree-like processing set case with three machines.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jia Xu, Zhaohui Liu,