A cutting plane algorithm for the unrelated parallel machine scheduling problem

DOI10.1016/S0377-2217(01)00270-3MaRDI QIDQ1847208zbMATH OpenOpenAlexFDO

Authors 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 optimizationPolyhedral combinatoricsScheduling

Mathematics Subject Classification ID

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

Recommendations

• Exact and approximation algorithms for makespan minimization on unrelated parallel machines
• Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem
• Solving a time-indexed formulation for an unrelated parallel machine scheduling problem by preprocessing and cutting planes
• Approximation algorithms for scheduling unrelated parallel machines
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search
• A state-of-the-art review of parallel-machine scheduling research
• Algorithms for Scheduling Tasks on Unrelated Processors
• An Application of Bin-Packing to Multiprocessor Scheduling
• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• APPROXIMATE AND EXACT ALGORITHMS FOR SCHEDULING INDEPENDENT TASKS ON UNRELATED PROCESSORS
• Approximation algorithms for scheduling unrelated parallel machines
• Bounds for Multifit Scheduling on Uniform Processors
• Duality-Based Algorithms for Scheduling Unrelated Parallel Machines
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Exact and approximation algorithms for makespan minimization on unrelated parallel machines
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• Heuristics for scheduling unrelated parallel machines
• scientific article; zbMATH DE number 1670878 (Why is no real title available?)
• scientific article; zbMATH DE number 3904331 (Why is no real title available?)
• scientific article; zbMATH DE number 4083375 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1783886 (Why is no real title available?)
• scientific article; zbMATH DE number 780782 (Why is no real title available?)
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Unrelated parallel machine scheduling using local search
• Valid inequalities for mixed 0-1 programs

Cited in

(17)

• A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times
• Exact and approximation algorithms for makespan minimization on unrelated parallel machines
• An exact algorithm for the identical parallel machine scheduling problem.
• A cutting plane algorithm for a single machine scheduling problem
• On the m-clique free interval subgraphs polytope: polyhedral analysis and applications
• A Lagrangean-based heuristic for multi-plant, multi-item, multi-period capacitated lot-sizing problems with inter-plant transfers
• Unrelated parallel machine scheduling with multiple time windows: an application to Earth observation satellite scheduling
• Simplifying dispatching rules in genetic programming for dynamic job shop scheduling
• Exact makespan minimization of unrelated parallel machines
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• Unrelated parallel machine scheduling problem with precedence constraints: polyhedral analysis and branch-and-cut
• scientific article; zbMATH DE number 432991 (Why is no real title available?)
• Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem
• Solving a time-indexed formulation for an unrelated parallel machine scheduling problem by preprocessing and cutting planes
• Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems
• Cutting-plane algorithms for preemptive uniprocessor scheduling problems
• Iterated greedy local search methods for unrelated parallel machine scheduling

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1847208)