Experimental comparison of approximation algorithms for scheduling unrelated parallel machines

DOI10.1287/IJOC.14.2.175.119MaRDI QIDQ2884532zbMATH OpenOpenAlexFDO

Authors T. Vredeveld, Cor Hurkens

Publication date 30 May 2012

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/f3b76843ec1af5102f18b0436d3bad0d92d07194

zbMATH Keywords

linear programmingmultiple machinesproduction-scheduling

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• Approximation algorithms for scheduling unrelated parallel machines
• A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
• A unified approach to scheduling on unrelated parallel machines
• Approximability of average completion time scheduling on unrelated machines
• Improved approximation schemes for scheduling unrelated parallel machines

Cited in

(15)

• A new approximation algorithm for unrelated parallel machine scheduling with release dates
• An exact extended formulation for the unrelated parallel machine total weighted completion time problem
• Unrelated parallel machine scheduling with multiple time windows: an application to Earth observation satellite scheduling
• A branch-and-price algorithm for unrelated parallel machine scheduling with machine usage costs
• Energy-efficient scheduling in an identical parallel machine environment with peak power consumption and deadline constraints
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
• An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
• Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems
• A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity
• Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations
• Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms
• Processing time generation schemes for parallel machine scheduling problems with various correlation structures
• Generating Experimental Data for Computational Testing with Machine Scheduling Applications
• GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times

Describes a project that uses

Uses Software

• SeDuMi

This page was built for publication: Experimental comparison of approximation algorithms for scheduling unrelated parallel machines

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