Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem

DOI10.1016/j.ejor.2004.09.002zbMath1116.90043OpenAlexW2056047740WikidataQ59222274 ScholiaQ59222274MaRDI QIDQ819064

Manuel Iori, Silvano Martello, Michele Monaci, Mauro Dell'Amico

Publication date: 22 March 2006

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.09.002

zbMATH Keywords

partitioningschedulingcolumn generationparallel machinescardinality constraintsbin packingscatter search

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

EPTAS for the dual of splittable bin packing with cardinality constraint, A 3/2-approximation algorithm for \(k_i\)-partitioning, An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints, EPTAS for parallel identical machine scheduling with time restrictions, Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint, Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(k\)-partitioning problem
• Applying tabu search with influential diversification to multiprocessor scheduling
• List scheduling algorithms to minimize the makespan on identical parallel machines
• A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems
• Worst-case analysis of greedy algorithms for the subset-sum problem
• A linear time approximation algorithm for multiprocessor scheduling
• An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• An Application of Bin-Packing to Multiprocessor Scheduling
• Optimal Scheduling of Tasks on Identical Parallel Processors
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• Bounds for Certain Multiprocessing Anomalies
• Bounds for the cardinality constrained \(P \|C_{max}\) problem