Job scheduling to minimize expected weighted flowtime on uniform processors (Q1111928): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0167-6911(88)90009-6 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2020231705 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniforn Processors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two competing queues with linear costs and geometric service requirements: the <i>μc</i>-rule is often optimal / rank
 
Normal rank
Property / cites work
 
Property / cites work: The <i>c</i>μ rule revisited / rank
 
Normal rank
Property / cites work
 
Property / cites work: Minimizing expected makespans on uniform processor systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Sequential Stochastic Assignment Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4758141 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Individually optimal routing in parallel systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal control of a queueing system with two heterogeneous servers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3964013 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3683893 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on ''Optimal control of a queueing system with two heterogeneous servers'' / rank
 
Normal rank
Property / cites work
 
Property / cites work: Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions / rank
 
Normal rank

Latest revision as of 10:00, 19 June 2024

scientific article
Language Label Description Also known as
English
Job scheduling to minimize expected weighted flowtime on uniform processors
scientific article

    Statements

    Job scheduling to minimize expected weighted flowtime on uniform processors (English)
    0 references
    0 references
    1988
    0 references
    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.
    0 references
    stochastic dynamic programming
    0 references
    Markov decision problem
    0 references
    sequential assignment
    0 references
    nonpreemptive scheduling
    0 references
    sequencing
    0 references
    nonidentical processors
    0 references
    total expected holding costs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references