Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
From MaRDI portal
Publication:3951534
DOI10.1137/0603019zbMath0489.68031OpenAlexW2087547812MaRDI QIDQ3951534
Bryan L. Deuermeyer, Michael A. Langston, Donald K. Friesen
Publication date: 1982
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0603019
NP-hardindependent tasksmaintenance schedulingidentical processorsdeterministic fleet sizingearliest processor finishing timeworst- case performance of the LPT algorithm
Related Items
\(\kappa\)-partitioning problems for maximizing the minimum load, Fair Packing of Independent Sets, Comparing the minimum completion times of two longest-first scheduling-heuristics, SEMI-ONLINE MACHINE COVERING, Bin packing with divisible item sizes, Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines, A polynomial-time approximation scheme for maximizing the minimum machine completion time, SEMI-ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON THREE SPECIAL UNIFORM MACHINES, Semi on-line scheduling problem for maximizing the minimum machine completion time on two uniform machines, Improved approaches to the exact solution of the machine covering problem, Optimal semi-online algorithms for machine covering, Parallel-machine scheduling with non-simultaneous machine available time, Ordinal Maximin Share Approximation for Goods, Maximizing the minimum load: the cost of selfishness, Reducing price of anarchy of selfish task allocation with more selfishness, Online max-min fair allocation, Polynomial-time combinatorial algorithm for general max-min fair allocation, General max-min fair allocation, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Fair allocation of indivisible items with conflict graphs, Optimal algorithms for semi-online machine covering on two hierarchical machines, A state-of-the-art review of parallel-machine scheduling research, Parallel machine covering with limited number of preemptions, On-line machine covering on two machines with local migration, Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint, Online scheduling with rejection and reordering: exact algorithms for unit size jobs, Symmetry exploitation for online machine covering with bounded migration, Performance of Heuristics for a Computer Resource Allocation Problem, A better semi-online algorithm for \(\mathrm Q3/s_{1} = s_{2}\leq s_{3}/C_{\mathrm{min}}\) with the known largest size, Maximin share guarantee for goods with positive externalities, The exact LPT-bound for maximizing the minimum completion time, Semi-on-line scheduling problems for maximizing the minimum machine completion time, Tight bounds for bandwidth allocation on two links, Machine covering with combined partial information, Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data, Optimal semi-online preemptive algorithms for machine covering on two uniform machines, The cost of selfishness for maximizing the minimum load on uniformly related machines, Inefficiency of equilibria for the machine covering game on uniform machines, MapReduce machine covering problem on a small number of machines, Parallel machine scheduling problems with proportionally deteriorating jobs, A unified view of parallel machine scheduling with interdependent processing rates, Maximizing the Minimum Load for Selfish Agents, OPTIMAL PREEMPTIVE SEMI-ONLINE ALGORITHM FOR SCHEDULING TIGHTLY-GROUPED JOBS ON TWO UNIFORM MACHINES, On the price of anarchy of two-stage machine scheduling games, \(k\)-partitioning problems with partition matroid constraint, Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times, Maximizing the minimum completion time on parallel machines, Bin packing with restricted piece sizes, The optimal on-line parallel machine scheduling, Semi-online machine covering for two uniform machines, Maximizing the minimum load for selfish agents, Simultaneous approximation ratios for parallel machine scheduling problems, Preemptive machine covering on parallel machines, Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
Cites Work
