Job scheduling to minimize expected weighted flowtime on uniform processors
We consider a sequencing problem in which there are n jobs to be processed nonpreemptively on m nonidentical processors. The processing time of the j-th processor is exponentially distributed with rate \(\mu_ j\), where \(\mu_ 1\geq \mu_ 2\geq...\geq \mu_ m\). Job i incurs a holding cost at rate \(c_ i\) per unit time while still in the system, where \(c_ 1\geq c_ 2\geq...\geq c_ n\). We show that to minimize total expected holding costs (weighted flowtime), it is optimal to take the fastest (lowest indexed) available processor, say processor j, and assign job k to it if \(k>(\sum^{j}_{i=1}\mu_ i)/\mu_ j-j\geq k-1\). After each assignment the jobs are renumbered (so that job \(k+1\) becomes job k, etc.), and the procedure is repeated with the next fastest available processor, etc. Note that the policy does not depend on the values of the holding costs \(c_ i\). This result is a generalization of the result of \textit{A. K. Agrawala, E. G. Coffman, M. R. Garey} and \textit{S. K. Tripathi} [IEEE Trans. Comput. C-33, 351-356 (1984; Zbl 0528.68022)] for minimizing expected flowtime, i.e., minimizing total holding cost when the holding costs of all the jobs are the same. We give a simpler proof of the more general result.
- Scheduling jobs on heterogeneous processors
- scientific article; zbMATH DE number 67289
- Stochastic scheduling on two non-identical parallel processors
- On the optimality of static priority policies in stochastic scheduling on parallel machines
- Minimizing expected makespans on uniform processor systems
- A note on Optimal control of a queueing system with two heterogeneous servers
- A Sequential Stochastic Assignment Problem
- A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniforn Processors
- scientific article; zbMATH DE number 3906232 (Why is no real title available?)
- scientific article; zbMATH DE number 3786125 (Why is no real title available?)
- scientific article; zbMATH DE number 3014822 (Why is no real title available?)
- Individually optimal routing in parallel systems
- Minimizing expected makespans on uniform processor systems
- Optimal control of a queueing system with two heterogeneous servers
- Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions
- The cμ rule revisited
- Two competing queues with linear costs and geometric service requirements: the μc-rule is often optimal
- Minimizing expected makespans of multi-priority classes of jobs on uniform processors
- Analysis of computer job control under uncertainty
- Stochastic scheduling on parallel machines to minimize discounted holding costs
- The expected competitive ratio for weighted completion time scheduling
- Scheduling jobs on heterogeneous processors
- Managing Queues with Heterogeneous Servers
- Stochastically Minimizing Total Delay of Jobs Subject to Random Deadlines
- SCHEDULING IMPATIENT JOBS IN A CLEARING SYSTEM WITH INSIGHTS ON PATIENT TRIAGE IN MASS CASUALTY INCIDENTS
- Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines
- Minimizing expected makespans on uniform processor systems
- On the optimality of static priority policies in stochastic scheduling on parallel machines
- Scheduling jobs on non-identical IFR processors to minimize general cost functions
- A Bayesian Sequential Single Machine Scheduling Problem to Minimize the Expected Weighted Sum of Flowtimes of Jobs with Exponential Processing Times
- scientific article; zbMATH DE number 1766736 (Why is no real title available?)
- Discussion of the standard processing time
- How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions
- Minimizing mean weighted execution time loss on identical and uniform processors
- Scheduling semi-malleable jobs to minimize mean flow time
This page was built for publication: Job scheduling to minimize expected weighted flowtime on uniform processors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111928)
