A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems

DOI10.1023/B:JOCO.0000031420.05971.29zbMath1133.90337OpenAlexW2058193654WikidataQ118165503 ScholiaQ118165503MaRDI QIDQ1768611

Emiliano Necciari, Maria Grazia Scutellà, Antonio Frangioni

Publication date: 15 March 2005

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/b:joco.0000031420.05971.29

zbMATH Keywords

production/scheduling networks/graphs approximations/heuristic: multi-exchange neighborhood flow algorithms: disjoint cycle computation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (21)

Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem ⋮ Exponential size neighborhoods for makespan minimization scheduling ⋮ A characterization of optimal multiprocessor schedules and new dominance rules ⋮ Improved approaches to the exact solution of the machine covering problem ⋮ Exact makespan minimization of unrelated parallel machines ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ The longest processing time rule for identical parallel machines revisited ⋮ Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints ⋮ Matheuristics: survey and synthesis ⋮ Tight bounds for the identical parallel machine‐scheduling problem: Part II ⋮ Partial solutions and multifit algorithm for multiprocessor scheduling ⋮ A hypergraph multi-exchange heuristic for the single-source capacitated facility location problem ⋮ Minimizing the makespan in nonpreemptive parallel machine scheduling problem ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ Block rearranging elements within matrix columns to minimize the variability of the row sums ⋮ A survey of very large-scale neighborhood search techniques ⋮ A composite algorithm for multiprocessor scheduling ⋮ Optimal and heuristic solution methods for a multiprocessor machine scheduling problem ⋮ Exact and approximate algorithms for high-multiplicity parallel machine scheduling ⋮ Tight bounds for the identical parallel machine scheduling problem ⋮ Performance guarantees of local search for minsum scheduling problems

This page was built for publication: A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems