Bounds for Certain Multiprocessing Anomalies
From MaRDI portal
Publication:5555416
DOI10.1002/j.1538-7305.1966.tb01709.xzbMath0168.40703OpenAlexW2089269509WikidataQ63353540 ScholiaQ63353540MaRDI QIDQ5555416
Publication date: 1968
Published in: Bell System Technical Journal (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/j.1538-7305.1966.tb01709.x
Related Items
A multiperiod single processor scheduling problem with periodic requirements, Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem, Vertex cover meets scheduling, Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions, Semi-online scheduling on two identical machines with a common due date to maximize total early work, A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem, Online production planning to maximize the number of on-time orders, A lower bound for randomized on-line multiprocessor scheduling, Scheduling with testing on multiple identical parallel machines, Online makespan minimization with budgeted uncertainty, A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer, No-wait scheduling in single-hop multi-channel lans, When it is worthwhile to work with the stochastic RCPSP?, Semi on-line scheduling on three processors with known sum of the tasks, List's worst-average-case or WAC ratio, On-line service scheduling, Online parallel machines scheduling with two hierarchies, Coordination mechanisms, On designing truthful mechanisms for online scheduling, Scheduling under linear constraints, On-line scheduling on parallel machines to minimize the makespan, Linear time algorithms for parallel machine scheduling, Taking advantage of a diverse set of efficient production schedules: a two-step approach for scheduling with side concerns, Energy-oriented scheduling based on evolutionary algorithms, A taxonomy of flexible flow line scheduling procedures, Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime, Flexible open shop scheduling problem to minimize makespan, Scheduling resource allocation with timeslot penalty for changeover, A simple linear time approximation algorithm for multi-processor job scheduling on four processors, State aggregation in dynamic programming - an application to scheduling of independent jobs on parallel processors, On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines, On-line scheduling mesh jobs with dependencies, Online multi-coloring on the path revisited, Heuristics for parallel machine scheduling with batch delivery consideration, Online LPT algorithms for parallel machines scheduling with a single server, Better bounds on online unit clustering, Approximation algorithms for multiprocessor scheduling under uncertainty, Reducing price of anarchy of selfish task allocation with more selfishness, An on-line scheduling problem of parallel machines with common maintenance time, Semi-online scheduling problems on a small number of machines, Lower bounds for online makespan minimization on a small number of related machines, Single-machine scheduling with periodic maintenance to minimize makespan revisited, Smoothed performance guarantees for local search, Online multiple-strip packing, Online hierarchical scheduling: an approach using mathematical programming, Coordination mechanisms with hybrid local policies, Scheduling malleable tasks with precedence constraints, Parallel machines scheduling with machine maintenance for minsum criteria, New upper and lower bounds for online scheduling with machine cost, Optimizing the stretch of independent tasks on a cluster: from sequential tasks to moldable tasks, An effective approximation algorithm for the malleable parallel task scheduling problem, Semi-online scheduling revisited, Scheduling of uniform parallel machines with s-precedence constraints, Non-clairvoyant scheduling games, Online scheduling with rejection and withdrawal, An efficient polynomial time approximation scheme for load balancing on uniformly related machines, Minimizing the makespan in nonpreemptive parallel machine scheduling problem, Scheduling unit length jobs on parallel machines with lookahead information, Robust algorithms for preemptive scheduling, Distribution of assignments among participants under conditions of constraints, On a local protocol for concurrent file transfers, Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks, Hybrid flowshop scheduling with interstage job transportation, Online scheduling with rejection and reordering: exact algorithms for unit size jobs, Single-processor scheduling with time restrictions, Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling, A comparison of performance measures for online algorithms, The complexity of pure equilibria in mix-weighted congestion games on parallel links, Online bin stretching with bunch techniques, A study of scheduling problems with preemptions on multi-core computers with GPU accelerators, Unrelated parallel machine scheduling -- perspectives and progress, Combination of parallel machine scheduling and vertex cover, Scheduling partially ordered jobs faster than \(2^n\), A variant of multi-task \(n\)-vehicle exploration problem: maximizing every processor's average profit, Scheduling with bully selfish jobs, On the optimality of list scheduling for online uniform machines scheduling, Semi-online preemptive scheduling: one algorithm for all variants, Scheduling \(UET\)-tasks on a star network: complexity and approximation, On robust online scheduling algorithms, New competitive results for the stochastic resource-constrained project scheduling problem: exploring the benefits of pre-processing, A composite algorithm for multiprocessor scheduling, Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay., Semi-online scheduling with known partial information about job sizes on two identical machines, Scheduling jobs under increasing linear machine maintenance time, Semi-on-line multiprocessor scheduling with given total processing time, Online scheduling with a buffer on related machines, Several semi-online scheduling problems on two identical machines with combined information, Improved bounds for online scheduling with eligibility constraints, Scheduling algorithms for flexible flowshops: Worst and average case performance, The cache complexity of multithreaded cache oblivious algorithms, On the price of heterogeneity in parallel systems, Isomorphic scheduling problems, A modification of Hochbaum and Shmoys' algorithm for scheduling problems, Approximation algorithms for scheduling unrelated parallel machines, Parallel machines scheduling with nonsimultaneous machine available time, Randomized truthful algorithms for scheduling selfish tasks on parallel machines, The Pareto frontier of inefficiency in mechanism design, Research on construction and application for the model of multistage job shop scheduling problem, Efficient job scheduling algorithms with multi-type contentions, Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints, Vector scheduling with rejection on two machines, New Algorithmic Results for Bin Packing and Scheduling, Exponential size neighborhoods for makespan minimization scheduling, Scheduling in the presence of processor networks : complexity and approximation, Towards Tight Lower Bounds for Scheduling Problems, Task scheduling in networks, On two dimensional packing, A Packing Problem You Can Almost Solve by Sitting on Your Suitcase, OPTIMAL ONLINE ALGORITHMS ON TWO HIERARCHICAL MACHINES WITH RESOURCE AUGMENTATION, An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops, Online load balancing of temporary tasks, Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms, Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures, APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS, Unnamed Item, Measuring the problem-relevant information in input, ONLINE SCHEDULING OF MIXED CPU-GPU JOBS, Approximation Algorithms for Scheduling with Resource and Precedence Constraints, Semi-online scheduling: a survey, Ordinal Maximin Share Approximation for Goods, On-line scheduling of parallel jobs, On-line load balancing for related machines, Randomized algorithms for that ancient scheduling problem, Algorithms for single machine scheduling problem with release dates and submodular penalties, Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties, Rescheduling to minimize makespan on a changing number of identical processors, Mixed coordination mechanisms for scheduling games on hierarchical machines, Worst-case analysis of LPT scheduling on a small number of non-identical processors, Advice complexity of disjoint path allocation, Bin stretching with migration on two hierarchical machines, A massively parallel implementation of multilevel Monte Carlo for finite element models, Load balancing for response time, Parallel solutions for preemptive makespan scheduling on two identical machines, Machine covering in the random-order model, Online Single Machine Scheduling to Minimize the Maximum Starting Time, Unnamed Item, PARALLEL MACHINE SCHEDULING WITH JOB DELIVERY COORDINATION, Tight Bounds for Online Vector Scheduling, Approximation algorithms and heuristics for task scheduling in data‐intensive distributed systems, A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan, On Approximation Algorithms for Two-Stage Scheduling Problems, Quasi-PTAS for scheduling with precedences using LP hierarchies, Scheduling games with machine-dependent priority lists, Semi-online Machine Covering on Two Hierarchical Machines with Known Total Size of Low-Hierarchy Jobs, Online Makespan Scheduling with Job Migration on Uniform Machines, On packet scheduling with adversarial jamming and speedup, The Bursty Steiner Tree Problem, Scheduling aspects in keyword extraction problem, Optimal on-line algorithms for single-machine scheduling, WORST-CASE PERFORMANCE EVALUATION ON MULTIPROCESSOR TASK SCHEDULING WITH RESOURCE AUGMENTATION, A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS, Semi-online scheduling with decreasing job sizes, Semi-on-line scheduling problems for maximizing the minimum machine completion time, Online Scheduling on a CPU-GPU Cluster, Online Bounded Analysis, Randomized on-line scheduling on two uniform machines, Unnamed Item, Bounds for the cardinality constrained \(P \|C_{max}\) problem, Competitive routing of virtual circuits with unknown duration, Parallel machine scheduling with job assignment restrictions, Scheduling experiments on a nulear reactor using mixed integer programming, A m‐parallel crane scheduling problem with a non‐crossing constraint, Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel, A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints, On-line load balancing of temporary tasks revisited, On-line bin-stretching, On-line scheduling of parallel jobs with runtime restrictions, An optimal online algorithm for scheduling two machines with release times, ONLINE SCHEDULING OF PARALLEL JOBS WITH BOUNDED PROCESSING TIMES ON TWO MACHINES, b9000A 1/4 approximate algorithm for P2/tree/Cmax, Scheduling with forbidden sets, Cooperativead hoccomputing: towards enabling cooperative processing in wireless environments, A Unified Approach to Truthful Scheduling on Related Machines, Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan, Semi-online scheduling with combined information on two identical machines in parallel, LPT online strategy for parallel-machine scheduling with kind release times, Load rebalancing games in dynamic systems with migration costs, Maximizing the Minimum Load for Selfish Agents, PARALLEL MACHINE SCHEDULING WITH A SIMULTANEITY CONSTRAINT AND UNIT-LENGTH JOBS TO MINIMIZE THE MAKESPAN, On the approximability of time disjoint walks, Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs, NP-Complete operations research problems and approximation algorithms, Closing the Gap for Makespan Scheduling via Sparsification Techniques, Online Order Scheduling Problem with the Same Order Size on Two Identical Machines, Non-Clairvoyant Precedence Constrained Scheduling., Online Collaborative Filtering on Graphs, Stochastic Load Balancing on Unrelated Machines, Approximation scheduling algorithms: a survey, On minimizing the makespan when some jobs cannot be assigned on the same machine, A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies, Scheduling in network flow shops, Semi-online scheduling jobs with tightly-grouped processing times on three identical machines, Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming, Multicriteria scheduling, Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs, On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs, A load balancing strategy for parallel computation of sparse permanents, Parallel Machine Scheduling with a Single Server: Loading and Unloading, ONLINE ALGORITHMS FOR SCHEDULING WITH MACHINE ACTIVATION COST, An introduction to the analysis of approximation algorithms, A better lower bound for on-line scheduling, Online-bounded analysis, A survey on makespan minimization in semi-online environments, New strategies for stochastic resource-constrained project scheduling, On-line load balancing, Dynamic scheduling on parallel machines, Optimal distribution strategies with cyclic demands, A lower bound for randomized on-line scheduling algorithms, 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, Minimizing makespan in hybrid flowshops, Scheduling with incompatible jobs, List scheduling algorithms to minimize the makespan on identical parallel machines, Multiprocessor scheduling: Combining LPT and MULTIFIT, Approximate algorithms for the \(P\parallel C_{\max}\) problem, Anomalous behavior in bin packing algorithms, On the existence of schedules that are near-optimal for both makespan and total weighted completion time, Machine scheduling with resource dependent processing times, Scheduling parallel machines for the customer order problem, Scheduling parallel jobs to minimize the makespan, The relative worst-order ratio applied to paging, Heuristic stability: a permutation disarray measure, Discrete parallel machine makespan ScheLoc problem, Semi-online scheduling problems on two identical machines with inexact partial information, Improved lower bounds for online scheduling to minimize total stretch, Job distribution algorithms, Multiprofessor scheduling, Flowshop scheduling with interstage job transportation, Partial solutions and multifit algorithm for multiprocessor scheduling, 1-optimality of static BSP computations: Scheduling independent chains as a case study., Penalty cost constrained identical parallel machine scheduling problem, The price of envy-freeness in machine scheduling, Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities, Online MapReduce processing on two identical parallel machines, An efficient algorithm for semi-online multiprocessor scheduling with given total processing time, When greediness fails: examples from stochastic scheduling., Bounds for parallel machine scheduling with predefined parts of jobs and setup time, A note on Graham's bound, A state-of-the-art review of parallel-machine scheduling research, Multi-machine scheduling with interval constrained position-dependent processing times, On-line load balancing made simple: greedy strikes back, Preemptive scheduling on a small number of hierarchical machines, On-line algorithms for the channel assignment problem in cellular networks., Minimizing the makespan on two identical parallel machines with mold constraints, The hierarchical model for load balancing on two machines, Optimal on-line algorithms to minimize makespan on two machines with resource augmentation, Speed scaling of tasks with precedence constraints, Competitive analysis of scheduling algorithms for aggregated links, A monotone approximation algorithm for scheduling with precedence constraints, Online scheduling with reassignment, Performance of service policies in a specialized service system with parallel servers, Block rearranging elements within matrix columns to minimize the variability of the row sums, Deterministic monotone algorithms for scheduling on related machines, On-line scheduling of parallel jobs on two machines, Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints, Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, On the power of lookahead in on-line server routing problems, A heuristic for preemptive scheduling with set-up times, On-line scheduling of two parallel machines with a single server, Algorithms better than LPT for semi-online scheduling with decreasing processing times, On one problem of construction of energy-saving schedules, An experimental study of new and known online packet buffering algorithms, Randomized priority algorithms, Analyzing scheduling with transient failures, On-line scheduling of multi-core processor tasks with virtualization, Competitive analysis of the online inventory problem, Resource constrained scheduling as generalized bin packing, Fast payment schemes for truthful mechanisms with verification, Coordination mechanisms for selfish scheduling, Preemptive online scheduling: Optimal algorithms for all speeds, Optimal and heuristic solution methods for a multiprocessor machine scheduling problem, Online scheduling on two uniform machines to minimize the makespan, Semi on-line algorithms for the partition problem, Combinatorial algorithms for data migration to minimize average completion time, Online scheduling with general machine cost functions, Priority algorithms for the subset-sum problem, The optimal on-line parallel machine scheduling, Scheduling jobs with time-resource tradeoff via nonlinear programming, Maximizing the minimum load for selfish agents, Heuristics for unrelated machine scheduling with precedence constraints, Scheduling interfering job sets on parallel machines, The \(k\)-partitioning problem, Resource augmentation in load balancing., New algorithms for related machines with temporary jobs., Applying extra-resource analysis to load balancing., Scheduling multiple variant programs under hard real-time constraints, Optimal scheduling on parallel machines for a new order class, Restarts can help in the on-line minimization of the maximum delivery time on a single machine, On-line scheduling revisited, Performance of scheduling algorithms for no-wait flowshops with parallel machines, Worst-case analysis of heuristics for open shops with parallel machines, A note on generalizing the maximum lateness criterion for scheduling, On-line scheduling with precedence constraints, On an on-line scheduling problem for parallel jobs, A manifesto for the computational method, Tabu search for the job-shop scheduling problem with multi-purpose machines, A note on on-line scheduling with precedence constraints on identical machines, An on-line \textit{seru} scheduling algorithm with proactive waiting considering resource conflicts, Improved approximation algorithms for multiprocessor scheduling with testing, Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines, Scheduling games with rank-based utilities, Approximation scheme for single-machine rescheduling with job delay and rejection, The constrained parallel-machine scheduling problem with divisible processing times and penalties, Scheduling with machine conflicts, Advice complexity of adaptive priority algorithms, On scheduling multiple parallel two-stage flowshops with Johnson's rule, Improved bounds for on-line load balancing, Server cloud scheduling, Online makespan minimization with parallel schedules, Approximation algorithms for simple assembly line balancing problems, Variable neighborhood descent branching applied to the multi-way number partitioning problem, Approximation schemes for parallel machine scheduling problems with controllable processing times, A note on on-line scheduling with partial information, A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, Anarchy in the UJ: coordination mechanisms for minimizing the number of late jobs, New lower and upper bounds for on-line scheduling, New approximation bounds for LPT scheduling, Scheduling with machine cost and rejection, Separating online scheduling algorithms with the relative worst order ratio, Approximation algorithms for the maximum bounded connected bipartition problem, Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence, Streaming algorithms for multitasking scheduling with shared processing, An exact algorithm for parallel machine scheduling with conflicts, Approximation and online algorithms for multidimensional bin packing: a survey, Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties, Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing, Parallel batch scheduling with nested processing set restrictions, A data intensive heuristic approach to the two-stage streaming scheduling problem, An optimal online algorithm for scheduling with general machine cost functions, On the value of job migration in online makespan minimization, Rejecting jobs to minimize load and maximum flow-time, Coordination mechanisms for parallel machine scheduling, The benefit of preemption with respect to the \(\ell_p\) norm, A note on posterior tight worst-case bounds for longest processing time schedules, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, Interruptible algorithms for multiproblem solving, Offline file assignments for online load balancing, A system-centric metric for the evaluation of online job schedules, Comparing online algorithms for bin packing problems, Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments, Inefficiency of Nash equilibria with parallel processing policy, Approximate strong equilibria in job scheduling games with two uniformly related machines, Approximability of scheduling with fixed jobs, An efficient algorithm for bin stretching, Theorem proving for pointwise metric temporal logic over the naturals via translations, Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays, Exploiting incomplete information to manage multiprocessor tasks with variable arrival rates, Semi-online scheduling with ``end of sequence information, Online scheduling with machine cost and rejection, Scheduling In the random-order model, Robust surgery loading, On scheduling multiple two-stage flowshops, Semi-online scheduling on two uniform processors, Scheduling jobs on identical machines with agreement graph, Online scheduling of two job types on a set of multipurpose machines with unit processing times, Minimizing the maximum starting time on-line, An optimal rounding gives a better approximation for scheduling unrelated machines, Designing PTASs for MIN-SUM scheduling problems, Can the agent with limited information solve travelling salesman problem?, Vector assignment schemes for asymmetric settings, Stochastic scheduling on parallel machines to minimize discounted holding costs, Worst-case analysis for on-line service policies, Minimizing makespan with release times on identical parallel batching machines, Analysis of flow shop scheduling anomalies, Load balancing of temporary tasks in the \(\ell _{p}\) norm, Pseudo lower bounds for online parallel machine scheduling, Randomized on-line scheduling similar jobs to minimize makespan on two identical processors, The maximum resource bin packing problem, Variable neighborhood descent applied to multi-way number partitioning problem, Improved approximation algorithms for two-stage flowshops scheduling problem, Parallel machine scheduling with nested processing set restrictions and job delivery times, Online scheduling of jobs with favorite machines, On-line order batching and sequencing problem with multiple pickers: a hybrid rule-based algorithm, An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time, Approximation algorithms for the multiprocessor scheduling with submodular penalties, Polynomial time approximation algorithms for machine scheduling: Ten open problems, On the price of anarchy of two-stage machine scheduling games, Malleable scheduling for flows of jobs and applications to MapReduce, A review of four decades of time-dependent scheduling: main results, new topics, and open problems, Starting time minimization for the maximum job variant, Makespan minimization with OR-precedence constraints, An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem, Stochastic dominance and the bijective ratio of online algorithms, Speed-robust scheduling. Sand, bricks, and rocks, Centers of probability measures without the mean, Online makespan scheduling with job migration on uniform machines, Parallel execution of schedules with random dependency graph, On scheduling inclined jobs on multiple two-stage flowshops, Optimal scheduling for two-processor systems, Tight lower bounds for semi-online scheduling on two uniform machines with known optimum, Simultaneous approximation ratios for parallel machine scheduling problems, A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model, New results on competitive analysis of online SRPT scheduling, Techniques and results on approximation algorithms for packing circles, A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops, Server cloud scheduling, Improved approximation algorithms for the combination problem of parallel machine scheduling and path, An approximation algorithm for scheduling trees of malleable tasks, On-line restricted assignment of temporary tasks with unknown durations., Off-line temporary tasks assignment., Delayed information and action in on-line algorithms, Simultaneous rational function reconstruction with errors: handling multiplicities and poles, Scheduling with an orthogonal resource constraint, Combinatorial approximation algorithms for the maximum bounded connected bipartition problem, Optimal preemptive semi-online scheduling to minimize makespan on two related machines, A new approach for bicriteria partitioning problem, Algorithms for dynamic scheduling of unit execution time tasks, Single-server parallel-machine scheduling with loading and unloading times
