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)
Vertex cover meets scheduling ⋮ Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions ⋮ A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem ⋮ A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines ⋮ A characterization of optimal multiprocessor schedules and new dominance rules ⋮ Scheduling with testing on multiple identical parallel machines ⋮ A 13/12 approximation algorithm for bin packing with extendable bins ⋮ Semi on-line scheduling on three processors with known sum of the tasks ⋮ The impact of local policies on the quality of packet routing in paths, trees, and rings ⋮ On-line scheduling with setup costs ⋮ Fast approximation algorithms for bi-criteria scheduling with machine assignment costs ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks ⋮ A new algorithm for online uniform-machine scheduling to minimize the makespan ⋮ Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming ⋮ Scheduling under linear constraints ⋮ On-line scheduling on parallel machines to minimize the makespan ⋮ Linear time algorithms for parallel machine scheduling ⋮ A taxonomy of flexible flow line scheduling procedures ⋮ Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime ⋮ Truthful algorithms for scheduling selfish tasks on parallel machines ⋮ Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules ⋮ Performance ratios of the Karmarkar-Karp differencing method ⋮ State aggregation in dynamic programming - an application to scheduling of independent jobs on parallel processors ⋮ Decentralized list scheduling ⋮ Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines ⋮ An engineering process for the verification of real-time systems ⋮ Machine scheduling with resource dependent processing times ⋮ Scheduling web advertisements: a note on the minspace problem ⋮ Scheduling parallel machines for the customer order problem ⋮ Scheduling parallel jobs to minimize the makespan ⋮ Heuristics for parallel machine scheduling with batch delivery consideration ⋮ Semi-online scheduling for jobs with release times ⋮ Heuristic stability: a permutation disarray measure ⋮ Maximizing the minimum load: the cost of selfishness ⋮ Reducing price of anarchy of selfish task allocation with more selfishness ⋮ Improved semi-online makespan scheduling with a reordering buffer ⋮ Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence ⋮ Multi-criteria scheduling: an agent-based approach for expert knowledge integration ⋮ On multiprocessor temperature-aware scheduling problems ⋮ A cutting and scheduling problem in float glass manufacturing ⋮ Improved upper bounds for online malleable job scheduling ⋮ Partial solutions and multifit algorithm for multiprocessor scheduling ⋮ Coordination mechanisms with hybrid local policies ⋮ Scheduling and fixed-parameter tractability ⋮ Minimizing expectation plus variance ⋮ Scheduling on same-speed processors with at most one downtime on each machine ⋮ An efficient algorithm for semi-online multiprocessor scheduling with given total processing time ⋮ An effective approximation algorithm for the malleable parallel task scheduling problem ⋮ Computer-assisted proof of performance ratios for the differencing method ⋮ On the asymptotic probabilistic analysis of scheduling problems in the presence of precedence constraints ⋮ A note on Graham's bound ⋮ Multi-task implementation of multi-periodic synchronous programs ⋮ Scheduling independent jobs with stochastic processing times and a common due date on parallel and identical machines ⋮ Scheduling of uniform parallel machines with s-precedence constraints ⋮ Non-clairvoyant scheduling games ⋮ A novel robust on-line protocol for load-balancing in structured peer-to-peer systems ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ Selfish bin covering ⋮ Parallel machine covering with limited number of preemptions ⋮ Minimizing the makespan in nonpreemptive parallel machine scheduling problem ⋮ Scheduling semiconductor multihead testers using metaheuristic techniques embedded with lot-specific and configuration-specific information ⋮ Online square packing with gravity ⋮ Robust reachability in timed automata and games: a game-based approach ⋮ Single-processor scheduling with time restrictions ⋮ Improved approximation algorithms for scheduling parallel jobs on identical clusters ⋮ Online bin stretching with bunch techniques ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Notes on a hierarchical scheduling problem on identical machines ⋮ A coordination mechanism for a scheduling game with parallel-batching machines ⋮ Bee colony optimization for scheduling independent tasks to identical processors ⋮ Performance bounds on multiprocessor scheduling strategies for statically allocated programs ⋮ Combination of parallel machine scheduling and vertex cover ⋮ Scheduling with bully selfish jobs ⋮ Semi-online preemptive scheduling: one algorithm for all variants ⋮ On robust online scheduling algorithms ⋮ A composite algorithm for multiprocessor scheduling ⋮ Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay. ⋮ Parallel \(\mathcal H\)-matrix arithmetics on shared memory systems ⋮ Semi-on-line multiprocessor scheduling with given total processing time ⋮ Online scheduling with a buffer on related machines ⋮ Scheduling algorithms for flexible flowshops: Worst and average case performance ⋮ Performance of the LPT algorithm in multiprocessor scheduling ⋮ Efficient priority rules for the stochastic resource-constrained project scheduling problem ⋮ Isomorphic scheduling problems ⋮ Makespan minimization for parallel machines scheduling with multiple availability constraints ⋮ Parallel bundle-based decomposition for large-scale structured mathematical programming problems ⋮ Approximation algorithms for scheduling unrelated parallel machines ⋮ Distribution-free bounds on the expectation of the maximum with scheduling applications ⋮ Parallel machines scheduling with nonsimultaneous machine available time ⋮ List scheduling of parallel tasks ⋮ Online scheduling on three uniform machines ⋮ Scheduling MapReduce jobs on identical and unrelated processors ⋮ Research on construction and application for the model of multistage job shop scheduling problem ⋮ Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm ⋮ Mathematical programming formulations for machine scheduling: A survey ⋮ On the complexity of scheduling unit-time jobs with or-precedence constraints ⋮ The no-wait flow-shop paradox ⋮ No-wait flexible flowshop scheduling with no-idle machines ⋮ An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
This page was built for publication: Bounds on Multiprocessing Timing Anomalies
