Exact and approximate algorithms for high-multiplicity parallel machine scheduling

DOI10.1007/s10951-009-0122-zzbMath1176.90209OpenAlexW1965652713MaRDI QIDQ1041349

Carlo Filippi, Giorgio Romanin-Jacur

Publication date: 2 December 2009

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-009-0122-z

zbMATH Keywords

computational complexityschedulingparallel machineshigh-multiplicity

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (6)

Scheduling High Multiplicity Jobs on Parallel Multi-Purpose Machines with Setup Times and Machine Available Times ⋮ An alternative approach for proving the NP-hardness of optimization problems ⋮ High-multiplicity scheduling on one machine with forbidden start and completion times ⋮ A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria ⋮ An approximate algorithm for a high-multiplicity parallel machine scheduling problem ⋮ Cyclic lot-sizing problems with sequencing costs

Cites Work

• Unnamed Item
• The linear balancing flow problem
• A polynomial algorithm for an integer quadratic non-separable transportation problem
• On polynomial solvability of the high multiplicity total weighted tardiness problem
• Parallel machine scheduling with splitting jobs
• From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective
• A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems
• A framework for the complexity of high-multiplicity scheduling problems
• A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths
• A Dynamic Programming Approach for Sequencing Groups of Identical Jobs
• On Scheduling Independent Tasks with Restricted Execution Times
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Bayesian Sequential Single Machine Scheduling Problem to Minimize the Expected Weighted Sum of Flowtimes of Jobs with Exponential Processing Times
• Multiplicity and complexity issues in contemporary production scheduling
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• Scheduling Jobs on Several Machines with the Job Splitting Property
• Convex separable optimization is not much harder than linear optimization
• Parallel machine scheduling with high multiplicity

This page was built for publication: Exact and approximate algorithms for high-multiplicity parallel machine scheduling