Tighter Bounds for the Multifit Processor Scheduling Algorithm

No abstract is available for this paper.

• Publication year

  1984

• Venue

  SIAM journal on computing (Print)

• Publication date

  1984-02-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1137/0213013
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• No references are available for this paper.

• Robust Task Allocations by Distributing the Risk Among Agents: Theory and Algorithms

  2025cites this paper
• Non-Clairvoyant Makespan Minimization Scheduling with Predictions

  2025cites this paper
• Efficient approximation schemes for scheduling on a stochastic number of machines

  2024cites this paper
• A Reduction from Chores Allocation to Job Scheduling

  2023cites this paper
• Adaptive Capacity Planning for Ambulatory Surgery Centers

  2022influential citation
• Supply Chain Planning: A Case for Hybrid Cross-Docks

  2021cites this paper
• Scheduling parallel identical machines to minimize makespan: A parallel approximation algorithm

  2019cites this paper
• Improved Bound Fit Algorithm for Fine Delay Scheduling in a Multi-Group Scan of Ultrasonic Phased Arrays

  2019cites this paper
• Adaptive Capacity Planning for Ambulatory Surgery Centers

  2019cites this paper
• An iterated local search and tabu search for two-parallel machine scheduling problem to minimize the maximum total completion time

  2019cites this paper
• Minimizing Makespan on Identical Parallel Machines

  2019cites this paper
• Minimizing the makespan on two identical parallel machines with mold constraints

  2019cites this paper
• Parallel Machine Models (Deterministic)

  2016cites this paper
• Scheduling Advertisements on a Web Page

  2016cites this paper
• Partial Solutions and MultiFit Algorithm for Multiprocessor Scheduling

  2015cites this paper
• A job profile oriented scheduling architecture for improving the throughput of industrial printing environments

  2015cites this paper
• Approximation Ratio of LD Algorithm for Multi-Processor Scheduling and the Coffman-Sethi Conjecture

  2015cites this paper
• Scheduling and fixed-parameter tractability

  2014cites this paper
• Approximation Algorithms and Metaheuristics

  2014cites this paper
• Scheduling unrelated machines with two types of jobs

  2014cites this paper
• A Framework for Approximate Optimization of BoT Application Deployment in Hybrid Cloud Environment

  2014cites this paper
• Exact performance of MULTIFIT for nonsimultaneous machines

  2014cites this paper
• A dynamic edge covering and scheduling problem: complexity results and approximation algorithms

  2013cites this paper
• Scheduling Meets Fixed-Parameter Tractability

  2013cites this paper
• Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime

  2013cites this paper
• Bin packing approximation algorithms: Survey and classification

  2013cites this paper
• Approximation Algorithms for 2-dimensional Packing and Related Scheduling Problems

  2013cites this paper
• Scheduling with an Orthogonal Resource Constraint

  2012cites this paper
• Polynomial Algorithms for Scheduling Jobs with Two Processing Times on Unrelated Machines

  2012cites this paper
• Comparison of Heuristics for Identical Parallel Machine Scheduling

  2012cites this paper
• A new algorithm for minimizing makespan on identical parallel machines

  2012cites this paper
• Unrelated parallel machine scheduling—perspectives and progress

  2011cites this paper
• Nuevos algoritmos para el problema de secuenciación en máquinas paralelas no relacionadas y generalizaciones

  2011cites this paper
• Minimizing the Makespan in Nonpreemptive Parallel Machine Scheduling Problem

  2010cites this paper
• Techniques for Proving Approximation Ratios in Scheduling

  2010cites this paper
• Parallel machine scheduling with nested processing set restrictions

  2010cites this paper
• A Heuristic Approach for Workload Balancing Problems

  2010cites this paper
• Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint

  2009cites this paper
• Sequencing and Scheduling: Algorithms and Complexity

  2009influential citation
• Classic Scheduling Theory

  2009cites this paper
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables

  2009cites this paper
• Aplicando estratégias de escalonamento através da análise do perfil de jobs para ambientes de impressão distribuídos

  2009cites this paper
• Wrapper chain balance partition for cores based on best interchange decreasing: Wrapper chain balance partition for cores based on best interchange decreasing

  2009cites this paper
• Balancing wrapper chains of SoC core based on best interchange decreasing

  2008cites this paper
• Deliverable D4.2.4 Solutions for General and Specific Mechanism Design Problems under Consideration of Appropriate Objectives

  2007cites this paper
• Theoretical Aspects on Performance Bounds and Fault Tolerance in Parallel Computing

  2007cites this paper
• An On-line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling. Siam

  2007cites this paper
• Load-Balanced Clustering Algorithms for Wireless Sensor Networks

  2007cites this paper
• Theoretical Aspects on Performance Bounds and Fault Tolerance in Parallel Computing

  2007cites this paper
• A New Approximation Algorithm for the Nonpreemptive Scheduling of Independent Jobs on Identical Parallel Processors

  2007cites this paper
• A simulated annealing approach to makespan minimization on identical parallel machines

  2006cites this paper
• Fair cost-sharing methods for scheduling jobs on parallel machines

  2006cites this paper
• Performance ratios of the Karmarkar-Karp differencing method

  2006cites this paper
• An Approximation Algorithm for The Load-Balanced Clustering Problem in Wireless Sensor Networks

  2006cites this paper
• An optimal rounding gives a better approximation for scheduling unrelated machines

  2005cites this paper
• The effect of machine availability on the worst-case performance of LPT

  2005cites this paper
• Test-Access Planning and Test Scheduling for Embedded Core-Based System Chips

  2005cites this paper
• Scheduling Web Advertisements: A Note on the Minspace Problem

  2005cites this paper
• Parallel Scheduling for Early Completion

  2004influential citation
• Online problems and two-player games: algorithms and analysis

  2004cites this paper
• Scheduling with Bounded Migration

  2004cites this paper
• Online Scheduling with Bounded Migration

  2004cites this paper
• A Hybrid Bin-Packing Heuristic to Multiprocessor Scheduling

  2004cites this paper
• A hierarchical heuristic approach for machine loading problems in a partially grouped environment

  2004cites this paper
• Performance ratios for the differencing method

  2004cites this paper
• Chapter 2: Previous scheduling research

  2003cites this paper
• On the reconfigurability of single-hub WDM ring networks

  2003cites this paper
• Performance Bounds of Algorithms for Scheduling Advertisements on a Web Page

  2003cites this paper
• 2-Approximation Algorithm for Parallel Machine Scheduling with Consecutive Eligibility

  2003cites this paper
• Performance Ratios for the Karmarkar-Karp Differencing Method

  2003cites this paper
• Chapter 6: Parallel program scheduling using test executions

  2003cites this paper
• Chapter 5: Parallel program scheduling with given parallel profile

  2003cites this paper
• Performance ratios for the Karmarker-Karp differencing method

  2002cites this paper
• The scheduling and wavelength assignment problem in optical WDM networks

  2002influential citation
• Tight Performance Bounds of CP-Scheduling on Out-Trees

  2001cites this paper
• Scheduling problems with applications to packet-switched optical WDM networks

  2001cites this paper
• A LISTFIT heuristic for minimizing makespan on identical parallel machines

  2001cites this paper
• Heuristic scheduling of parallel machines with sequence-dependent set-up times

  2001cites this paper
• Task Distributions on Multiprocessor Systems

  2000cites this paper
• Wrapper design for embedded core test

  2000cites this paper
• Approximation algorithms for multiprocessor scheduling problem

  2000cites this paper
• The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items

  2000cites this paper
• Bin Packing Approximation Algorithms: Combinatorial Analysis

  1999cites this paper
• Predicting and Bounding the Speedup of Multithreaded Solaris Programs

  1999cites this paper
• Approximability of scheduling with fixed jobs

  1999cites this paper
• Algorithms for multiprocessor scheduling with machine release times

  1998cites this paper
• A Review of Machine Scheduling: Complexity, Algorithms and Approximability

  1998cites this paper
• Using Recorded Values for Bounding the Minimum Completion Time in Multiprocessors

  1998cites this paper
• An optimal lower bound on the maximum speedup in multiprocessors with clusters

  1995cites this paper
• Combinatorics for Multiprocessor Scheduling Optimization and Oter Contexts in Computer Architecture

  1995cites this paper
• Determining the Performance Ratio of Algorithm Multifit for Scheduling

  1995cites this paper
• Scheduling Multiprocessor Flow Shops

  1994cites this paper
• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective

  1994influential citation
• An optimal upper bound on the minimal completion time in distributed supercomputing

  1994cites this paper
• Chapter 9 Sequencing and scheduling: Algorithms and complexity

  1993cites this paper
• Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times

  1993cites this paper
• HEURISTIC APPROACHES FOR LOADING PROBLEMS IN FLEXIBLE MANUFACTURING SYSTEMS

  1993cites this paper
• Sequencing and scheduling : algorithms and complexity

  1993cites this paper
• Worst-case analysis of heuristics for open shops with parallel machines

  1993cites this paper
• Scheduling

  1992cites this paper