文章基本信息

标题：Scheduling Resources for Executing a Partial Set of Jobs
本地全文：下载
作者：Venkatesan T. Chakaravarthy ; Arindam Pal ; Sambuddha Roy 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：18
页码：199-210
DOI：10.4230/LIPIcs.FSTTCS.2012.199
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper, we consider the problem of choosing a minimum cost set of resources for executing a specified set of jobs. Each input job is an interval, determined by its start-time and end-time. Each resource is also an interval determined by its start-time and end-time; moreover, every resource has a capacity and a cost associated with it. We consider two versions of this problem. In the partial covering version, we are also given as input a number k, specifying the number of jobs that must be performed. The goal is to choose $k$ jobs and find a minimum cost set of resources to perform the chosen k jobs (at any point of time the capacity of the chosen set of resources should be sufficient to execute the jobs active at that time). We present an O(log n)-factor approximation algorithm for this problem. We also consider the prize collecting version, wherein every job also has a penalty associated with it. The feasible solution consists of a subset of the jobs, and a set of resources, to perform the chosen subset of jobs. The goal is to find a feasible solution that minimizes the sum of the costs of the selected resources and the penalties of the jobs that are not selected. We present a constant factor approximation algorithm for this problem.
关键词：Approximation Algorithms; Partial Covering; Interval Graphs