A cutting plane algorithm for the unrelated parallel machine scheduling problem

DOI10.1016/S0377-2217(01)00270-3zbMath1081.90558OpenAlexW2079477591MaRDI QIDQ1847208

Philippe Chrétienne, Ethel Mokotoff

Publication date: 17 November 2002

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(01)00270-3

zbMATH Keywords

Combinatorial optimizationSchedulingPolyhedral combinatorics

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)

Related Items (12)

A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers ⋮ On the \(m\)-clique free interval subgraphs polytope: polyhedral analysis and applications ⋮ A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem ⋮ Simplifying dispatching rules in genetic programming for dynamic job shop scheduling ⋮ Exact makespan minimization of unrelated parallel machines ⋮ Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems ⋮ An exact algorithm for the identical parallel machine scheduling problem. ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut ⋮ A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times ⋮ Unrelated parallel machine scheduling with multiple time windows: an application to Earth observation satellite scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• A state-of-the-art review of parallel-machine scheduling research
• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• Valid inequalities for mixed 0-1 programs
• Unrelated parallel machine scheduling using local search
• A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search
• Exact and approximation algorithms for makespan minimization on unrelated parallel machines
• Heuristics for scheduling unrelated parallel machines
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Bounds for Multifit Scheduling on Uniform Processors
• APPROXIMATE AND EXACT ALGORITHMS FOR SCHEDULING INDEPENDENT TASKS ON UNRELATED PROCESSORS
• Algorithms for Scheduling Tasks on Unrelated Processors
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• An Application of Bin-Packing to Multiprocessor Scheduling
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Duality-Based Algorithms for Scheduling Unrelated Parallel Machines

This page was built for publication: A cutting plane algorithm for the unrelated parallel machine scheduling problem