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

SchedulingCombinatorial optimizationPolyhedral combinatorics

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• APPROXIMATE AND EXACT ALGORITHMS FOR SCHEDULING INDEPENDENT TASKS ON UNRELATED PROCESSORS
• 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
• 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
• 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

(16)

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

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)