EPTAS for parallel identical machine scheduling with time restrictions

We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of B, and even the case of non-constant values of B on one machine was not known to admit a PTAS.

• Publication year

  2021

• Venue

  Journal of combinatorial optimization

• Publication date

  2021-11-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10878-024-01108-yarXiv 2111.06692
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Unified Framework for Designing EPTAS for Load Balancing on Parallel Machines

  2019cited by this paper
• The single-processor scheduling problem with time restrictions: complexity and related problems

  2018cited by this paper
• Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times

  2018cited by this paper
• An EPTAS for Scheduling on Unrelated Machines of Few Different Types

  2017cited by this paper
• On the NP-hardness of scheduling with time restrictions

  2017influential reference
• Optimal Matroid Partitioning Problems

  2017cited by this paper
• An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints

  2016influential reference
• Closing the Gap for Makespan Scheduling via Sparsification Techniques

  2016cited by this paper
• Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions

  2016cited by this paper
• Better permutations for the single-processor scheduling with time restrictions

  2016cited by this paper
• Minimum total weighted completion time: Faster approximation schemes

  2014cited by this paper
• On the single-processor scheduling problem with time restrictions

  2014cited by this paper
• Single-processor scheduling with time restrictions

  2013cited by this paper
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines

  2012cited by this paper
• A 3/2-approximation algorithm for 3/2-partitioning

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

  2009cited by this paper
• Lower bounds and heuristic algorithms for the k

  2006cited by this paper
• Parameterized Complexity Theory

  2006cited by this paper
• 3-Partitioning Problems for Maximizing the Minimum Load

  2002cited by this paper
• Bounds for the cardinality constrained P∥Cmax problem

  2001cited by this paper
• Approximation schemes for scheduling on parallel machines

  1998cited by this paper
• Parameterized Complexity

  1998influential reference
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• On the Efficiency of Polynomial Time Approximation Schemes

  1997cited by this paper
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach

  1988cited by this paper
• Using dual approximation algorithms for scheduling problems: Theoretical and practical results

  1985influential reference
• Integer Programming with a Fixed Number of Variables

  1983cited by this paper
• Improved algorithms for integer programming and related lattice problems

  1983cited by this paper

• No citing papers are available for this paper.