2021/11/12 by G. Jaykrishnan, Jaykrishnan, G., Asaf Levin +1
Computer Science · Engineering · Mathematics · #90C27 #Advanced Manufacturing and Logistics Optimization #Assembly Line Balancing Optimization #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #Optimization and Control (math.OC) #Scheduling and Optimization Algorithms #acm:90C27 #cs.DM #cs.DS #math.CO #math.OC #msc:90C27
paper · pdf · doi:10.48550/arxiv.2111.06692
arxiv created 2021/11/12 · openalex publication_date 2021/11/12 · arxiv updated 2021/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.