首页 | 本学科首页   官方微博 | 高级检索  
     


Scheduling on two identical machines with a speed-up resource
Authors:Haifeng Xu  Deshi Ye
Affiliation:a Department of Mathematics, Zhejiang University, Hangzhou 310027, China
b College of Computer Science, Zhejiang University, Hangzhou 310027, China
Abstract:We address a variant of scheduling problem on two identical machines, where we are given an additional speed-up resource. If a job uses the resource, its processing time may decrease. However, at any time the resource can only be used by at most one job. The objective is to minimize the makespan. For the offline version, we present an FPTAS. For the online version where jobs arrive over list, we propose an online algorithm with competitive ratio of 1.781, and show a lower bound of 1.686 for any online algorithm.
Keywords:Scheduling   FPTAS   Online algorithms
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号