Improved approaches to the exact solution of the machine covering problem

DOI10.1007/S10951-016-0477-XMaRDI QIDQ2398644zbMATH OpenOpenAlexFDO

Authors Rico Walter, Martin Wirth, Alexander Lawrinenko

Publication date 18 August 2017

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-016-0477-x

zbMATH Keywords

branch-and-bounddominance criteriaidentical parallel machinesmachine covering

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Maximizing the minimum completion time on parallel machines
• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
• Minimizing the makespan in nonpreemptive parallel machine scheduling problem
• Optimal Scheduling of Tasks on Identical Parallel Processors
• Heuristic and exact algorithms for the identical parallel machine scheduling problem

Cites work

• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
• A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• An exact algorithm for the dual bin packing problem
• Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
• Approximation and Online Algorithms
• Bounds on Multiprocessing Timing Anomalies
• Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem
• Comparing the minimum completion times of two longest-first scheduling-heuristics
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Inverse Optimization
• Inverse scheduling with maximum lateness objective
• Inverse scheduling: Two-machine flow-shop problem
• Max-min online allocations with a reordering buffer
• Maximizing the minimum completion time on parallel machines
• On-line machine covering
• Optimal Scheduling of Tasks on Identical Parallel Processors
• Optimal semi-online algorithms for machine covering
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• SEMI-ONLINE MACHINE COVERING
• The exact LPT-bound for maximizing the minimum completion time

Cited in

(4)

• Maximizing the minimum completion time on parallel machines
• Improved algorithms to minimize workload balancing criteria on identical parallel machines
• An exact algorithm for parallel machine scheduling with conflicts
• A characterization of optimal multiprocessor schedules and new dominance rules

This page was built for publication: Improved approaches to the exact solution of the machine covering problem

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