Bounds on Multiprocessing Timing Anomalies
From MaRDI portal
Publication:5582060
DOI10.1137/0117039zbMath0188.23101OpenAlexW2104680817WikidataQ29012258 ScholiaQ29012258MaRDI QIDQ5582060
Publication date: 1969
Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/c037edd22215b89c8d2924d4e3c81eb84fdadec7
Related Items (only showing first 100 items - show all)
An introduction to the analysis of approximation algorithms ⋮ A survey on makespan minimization in semi-online environments ⋮ Feasibility of scheduling lot sizes of two frequencies on one machine ⋮ Nonclairvoyant scheduling ⋮ Optimal distribution strategies with cyclic demands ⋮ \texttt{mplrs}: a scalable parallel vertex/facet enumeration code ⋮ A selfish allocation heuristic in scheduling: equilibrium and inefficiency bound analysis ⋮ The rate of convergence to optimality of the LPT rule ⋮ Heuristics for parallel machine scheduling with delivery times ⋮ Sensitivity analysis of list scheduling heuristics ⋮ A heuristic algorithm for a pseudo-cyclic delivery problem under window constraints ⋮ A robust strategy approach to a strategic mobility problem ⋮ Scheduling with incompatible jobs ⋮ A new enumeration scheme for the knapsack problem ⋮ List scheduling algorithms to minimize the makespan on identical parallel machines ⋮ On the worst-case ratio of a compound multiprocessor scheduling algorithm ⋮ UET scheduling with unit interprocessor communication delays ⋮ Tighter bounds on a heuristic for a partition problem ⋮ Modelling and scheduling a batch-type production on identical machines ⋮ Tight upper bounds for semi-online scheduling on two uniform machines with known optimum ⋮ Bin packing with divisible item sizes ⋮ Exact bounds of the modified LPT algorithms applying to parallel machines scheduling with nonsimultaneous machine available times ⋮ Multiprocessor scheduling with interprocessor communication delays ⋮ Solving large batches of traveling salesman problems with parallel and distributed computing ⋮ Matheuristic approaches for parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities ⋮ Multiprocessor scheduling: Combining LPT and MULTIFIT ⋮ Random allocation of jobs with weights and precedence ⋮ Exact and heuristic algorithms for thrift cyclic scheduling ⋮ Makespan minimization in preemptive two machine job shops ⋮ Localizing combinatorial properties of partitions ⋮ Scheduling on identical machines: How good is LPT in an on-line setting? ⋮ The exact bound of Lee's MLPT ⋮ A two-phase algorithm for bin stretching with stretching factor 1.5 ⋮ Using duplication for scheduling unitary tasks on m processors with unit communication delays ⋮ Sharing video on demand ⋮ 1-optimality of static BSP computations: Scheduling independent chains as a case study. ⋮ Efficient scheduling of tasks without full use of processor resources ⋮ Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities ⋮ A survey of scheduling methods for multiprocessor systems ⋮ When greediness fails: examples from stochastic scheduling. ⋮ General approximation algorithms for some arithmetical combinatorial problems ⋮ Improved 0/1-interchange scheduling ⋮ Divider-based algorithms for hierarchical tree partitioning. ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Tighter bound for MULTIFIT scheduling on uniform processors ⋮ Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint ⋮ Parametric bounds for LPT scheduling on uniform processors ⋮ A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes ⋮ \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems ⋮ Deterministic monotone algorithms for scheduling on related machines ⋮ Models and formal verification of multiprocessor system-on-chips ⋮ List scheduling for jobs with arbitrary release times and similar lengths ⋮ Nash equilibria in discrete routing games with convex latency functions ⋮ An algorithm for flow time minimization and its asymptotic makespan properties ⋮ Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints ⋮ A heuristic for preemptive scheduling with set-up times ⋮ New efficiency results for makespan cost sharing ⋮ Randomized priority algorithms ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ Resource constrained scheduling as generalized bin packing ⋮ The ratio of the extreme to the sum in a random sequence ⋮ Fast payment schemes for truthful mechanisms with verification ⋮ Extension of algorithm list scheduling for a semi-online scheduling problem ⋮ Coordination mechanisms for selfish scheduling ⋮ A general lower bound for the makespan problem ⋮ Semi on-line algorithms for the partition problem ⋮ \(k\)-partitioning problems with partition matroid constraint ⋮ Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times ⋮ Fair cost-sharing methods for scheduling jobs on parallel machines ⋮ Tighter approximation bounds for LPT scheduling in two special cases ⋮ A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem ⋮ Semi-online machine covering for two uniform machines ⋮ Partitioning under the \(L_p\) norm ⋮ Scheduling jobs with time-resource tradeoff via nonlinear programming ⋮ On truthfulness and approximation for scheduling selfish tasks ⋮ A hybrid two-stage flowshop with part family, batch production, major and minor set-ups ⋮ List schedules for cyclic scheduling ⋮ Approximation algorithms for partitioning small items in unequal bins to minimize the total size ⋮ Minimizing makespan subject to minimum total flow-time on identical parallel machines ⋮ On a methodology for discrete-continuous scheduling ⋮ Equilibria in load balancing games ⋮ The \(k\)-partitioning problem ⋮ The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines ⋮ Approximation algorithms for the multiprocessor open shop scheduling problem ⋮ A tight upper bound for the \(k\)-partition problem on ideal sets ⋮ Optimal scheduling on parallel machines for a new order class ⋮ A tight bound for 3-partitioning ⋮ Performance of scheduling algorithms for no-wait flowshops with parallel machines ⋮ Worst-case analysis of heuristics for open shops with parallel machines ⋮ First fit decreasing scheduling on uniform multiprocessors ⋮ On-line scheduling with precedence constraints ⋮ On scheduling send-graphs and receive-graphs under the LogP-model ⋮ On an on-line scheduling problem for parallel jobs ⋮ Some recent results in the analysis of greedy algorithms for assignment problems ⋮ Extending Graham's result on scheduling to other heuristics ⋮ List scheduling in a parallel machine environment with precedence constraints and setup times ⋮ A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective ⋮ Worst-case error bounds for parallel machine scheduling problems with bounded sequence-dependent setup times ⋮ A new on-line scheduling heuristic ⋮ A note on on-line scheduling with precedence constraints on identical machines
This page was built for publication: Bounds on Multiprocessing Timing Anomalies
