Bounds on Multiprocessing Timing Anomalies

Cited in

(only showing first 100 items - show all)

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
\(k\)-partitioning problems with partition matroid constraint
Fair cost-sharing methods for scheduling jobs on parallel machines
Tighter approximation bounds for LPT scheduling in two special cases
Semi-online machine covering for two uniform machines
Scheduling jobs with time-resource tradeoff via nonlinear programming
On truthfulness and approximation for scheduling selfish tasks
Equilibria in load balancing games
First fit decreasing scheduling on uniform multiprocessors
An introduction to the analysis of approximation algorithms
Optimal distribution strategies with cyclic demands
The rate of convergence to optimality of the LPT rule
A heuristic algorithm for a pseudo-cyclic delivery problem under window constraints
A new enumeration scheme for the knapsack problem
On the worst-case ratio of a compound multiprocessor scheduling algorithm
UET scheduling with unit interprocessor communication delays
Modelling and scheduling a batch-type production on identical machines
Bin packing with divisible item sizes
Multiprocessor scheduling with interprocessor communication delays
Multiprocessor scheduling: Combining LPT and MULTIFIT
Localizing combinatorial properties of partitions
The exact bound of Lee's MLPT
Efficient scheduling of tasks without full use of processor resources
A survey of scheduling methods for multiprocessor systems
General approximation algorithms for some arithmetical combinatorial problems
Improved 0/1-interchange scheduling
Tighter bound for MULTIFIT scheduling on uniform processors
Parametric bounds for LPT scheduling on uniform processors
An algorithm for flow time minimization and its asymptotic makespan properties
A heuristic for preemptive scheduling with set-up times
Resource constrained scheduling as generalized bin packing
A general lower bound for the makespan problem
Semi on-line algorithms for the partition problem
Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times
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
On a methodology for discrete-continuous scheduling
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
Some recent results in the analysis of greedy algorithms for assignment problems
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
Feasibility of scheduling lot sizes of two frequencies on one machine
Nonclairvoyant scheduling
Heuristics for parallel machine scheduling with delivery times
Sensitivity analysis of list scheduling heuristics
A robust strategy approach to a strategic mobility problem
Scheduling with incompatible jobs
List scheduling algorithms to minimize the makespan on identical parallel machines
Tighter bounds on a heuristic for a partition problem
Exact bounds of the modified LPT algorithms applying to parallel machines scheduling with nonsimultaneous machine available times
Random allocation of jobs with weights and precedence
Makespan minimization in preemptive two machine job shops
Scheduling on identical machines: How good is LPT in an on-line setting?
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.
When greediness fails: examples from stochastic scheduling.
Divider-based algorithms for hierarchical tree partitioning.
A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
Partitioning under the \(L_p\) norm
Minimizing makespan subject to minimum total flow-time on identical parallel machines
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
Extending Graham's result on scheduling to other heuristics
List scheduling in a parallel machine environment with precedence constraints and setup times
A note on on-line scheduling with precedence constraints on identical machines
A survey on makespan minimization in semi-online environments
\texttt{mplrs}: a scalable parallel vertex/facet enumeration code
A selfish allocation heuristic in scheduling: equilibrium and inefficiency bound analysis
Tight upper bounds for semi-online scheduling on two uniform machines with known optimum
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
Exact and heuristic algorithms for thrift cyclic scheduling
A two-phase algorithm for bin stretching with stretching factor 1.5
Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities
Approximation for scheduling on uniform nonsimultaneous parallel machines
Online bin stretching with three bins
General parametric scheme for the online uniform machine scheduling problem with two different speeds
Bounds for parallel machine scheduling with predefined parts of jobs and setup time
A theory and algorithms for combinatorial reoptimization
Scheduling on uniform processors with at most one downtime on each machine
Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan
Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games
Algorithms better than LPT for semi-online scheduling with decreasing processing times
A cutting plane approach for integrated planning and scheduling
A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria
The effect of machine availability on the worst-case performance of LPT

This page was built for publication: Bounds on Multiprocessing Timing Anomalies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5582060)