Results 1  10
of
62
Minimizing maximum (weighted) flowtime on related and unrelated machines
"... Abstract. In this paper we initiate the study of job scheduling on related and unrelated machines so as to minimize the maximum flow time or the maximum weighted flow time (when each job has an associated weight). Previous work for these metrics considered only the setting of parallel machines, whil ..."
Abstract

Cited by 4 (1 self)
 Add to MetaCart
, while previous work for scheduling on unrelated machines only considered Lp, p < ∞ norms. Our main results are: (i) We give an O(ε −3)competitive algorithm to minimize maximum weighted flow time on related machines where we assume that the machines of the online algorithm can process 1 + ε units
Scheduling for flowtime with admission control
 In Proc. 11th Annual European Symp. Algorithms, number 2832 in LNCS
, 2003
"... Abstract. We consider the problem of scheduling jobs on a single machine with preemption, when the server is allowed to reject jobs at some penalty. We consider minimizing two objectives: total flow time and total jobidle time (the idle time of a job is the flow time minus the processing time). We ..."
Abstract

Cited by 7 (0 self)
 Add to MetaCart
Abstract. We consider the problem of scheduling jobs on a single machine with preemption, when the server is allowed to reject jobs at some penalty. We consider minimizing two objectives: total flow time and total jobidle time (the idle time of a job is the flow time minus the processing time). We
Minimizing Average Flowtime: Upper and Lower Bounds
, 2007
"... We consider the problem of minimizing average flow time on multiple machines when each job can be assigned only to a specified subset of the machines. This is a special case of scheduling on unrelated machines and we show that no online algorithm can have a bounded competitive ratio. We provide an O ..."
Abstract

Cited by 12 (4 self)
 Add to MetaCart
We consider the problem of minimizing average flow time on multiple machines when each job can be assigned only to a specified subset of the machines. This is a special case of scheduling on unrelated machines and we show that no online algorithm can have a bounded competitive ratio. We provide
Resource Augmentation for Weighted Flowtime explained by Dual Fitting
"... We propose a general dualfitting technique for analyzing online scheduling algorithms in the unrelated machines setting where the objective function involves weighted flowtime, and we allow the machines of the online algorithm to have (1 + ε)extra speed than the offline optimum (the socalled sp ..."
Abstract
 Add to MetaCart
We propose a general dualfitting technique for analyzing online scheduling algorithms in the unrelated machines setting where the objective function involves weighted flowtime, and we allow the machines of the online algorithm to have (1 + ε)extra speed than the offline optimum (the so
A Dynamic Programming Framework for NonPreemptive Scheduling Problems on Multiple Machines [Extended Abstract]
"... In this paper, we consider a variety of scheduling problems where n jobs with release times are to be scheduled nonpreemptively on a set of m identical machines. The problems considered are machine minimization, (weighted) throughput maximization and minsum objectives such as (weighted) flow t ..."
Abstract

Cited by 1 (0 self)
 Add to MetaCart
In this paper, we consider a variety of scheduling problems where n jobs with release times are to be scheduled nonpreemptively on a set of m identical machines. The problems considered are machine minimization, (weighted) throughput maximization and minsum objectives such as (weighted) flow
Online scalable algorithm for minimizing ;knorms of weighted flow time on unrelated machines
 In SODA
, 2011
"... We consider the problem of scheduling jobs that arrive online in the unrelated machine model to minimize `k norms of weighted flowtime. In the unrelated setting, the processing time and weight of a job depends on the machine it is assigned to, and it is perhaps the most general machine model conside ..."
Abstract

Cited by 5 (3 self)
 Add to MetaCart
We consider the problem of scheduling jobs that arrive online in the unrelated machine model to minimize `k norms of weighted flowtime. In the unrelated setting, the processing time and weight of a job depends on the machine it is assigned to, and it is perhaps the most general machine model
B.: An online scalable algorithm for minimizing ℓknorms of weighted flow time on unrelated machines
 In: ACMSIAM Symposium on Discrete Algorithms
, 2011
"... We consider the problem of scheduling jobs that arrive online in the unrelated machine model to minimize ℓk norms of weighted flowtime. In the unrelated setting, the processing time and weight of a job depends on the machine it is assigned to, and it is perhaps the most general machine model conside ..."
Abstract

Cited by 4 (3 self)
 Add to MetaCart
We consider the problem of scheduling jobs that arrive online in the unrelated machine model to minimize ℓk norms of weighted flowtime. In the unrelated setting, the processing time and weight of a job depends on the machine it is assigned to, and it is perhaps the most general machine model
Online Weighted Flow Time and Deadline Scheduling
 In RANDOMAPPROX
, 2001
"... In this paper we study some aspects of Weighted Flow Time on parallel machines. We first show that the online algorithm Highest Density First is an O(1)speed O(1)approximation algorithm for P jr i ; pmtnj P w i F i . We then consider a related Deadline Scheduling Problem that involves minimizing t ..."
Abstract

Cited by 51 (21 self)
 Add to MetaCart
In this paper we study some aspects of Weighted Flow Time on parallel machines. We first show that the online algorithm Highest Density First is an O(1)speed O(1)approximation algorithm for P jr i ; pmtnj P w i F i . We then consider a related Deadline Scheduling Problem that involves minimizing
Minimizing weighted flow time
 In Proc. 14th Symp. on Discrete Algorithms (SODA
, 2003
"... 1 Introduction We consider the classic problem of scheduling a collection of dynamically arriving jobs over time so as to minimize the total weighted flow time. The flow time of a job (also known as the response time) is the total time it spends in the system, thus it is the sum of times the job is ..."
Abstract

Cited by 19 (5 self)
 Add to MetaCart
known result [13] is that the online algorithm that at any time schedules the job with the shortest remaining processing time (SRPT) minimizes the flow time on a single machine.
Online Scheduling to Minimize Max Flow Time: An Optimal Preemptive Algorithm
, 2004
"... We investigate the problem of online scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the maximum flow time among all jobs, where the flow time of a job is its completion time minus its release time. We derive an online algorithm with competiti ..."
Abstract

Cited by 2 (0 self)
 Add to MetaCart
We investigate the problem of online scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the maximum flow time among all jobs, where the flow time of a job is its completion time minus its release time. We derive an online algorithm
Results 1  10
of
62