Approximation algorithm for minimizing total latency in machine scheduling with deliveries

DOI10.1016/J.DISOPT.2007.11.007MaRDI QIDQ924636zbMATH OpenOpenAlexFDO

Authors Asaf Levin, Michal Penn

Publication date 16 May 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2007.11.007

zbMATH Keywords

approximation algorithmminimum latencyscheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• An improved approximation algorithm for single machine scheduling with job delivery
• Parallel machine scheduling with job delivery coordination
• Single machine scheduling with job delivery to multiple customers
• Single machine scheduling with batch delivery to multiple customers in a star-shaped network
• Machine scheduling with deliveries to multiple customer locations

Cites work

• A Faster, Better Approximation Algorithm for the Minimum Latency Problem
• A General Approximation Technique for Constrained Forest Problems
• An improved approximation ratio for the minimum latency problem
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Combinatorial Optimization with Rational Objective Functions
• scientific article; zbMATH DE number 1445374 (Why is no real title available?)
• Machine scheduling with deliveries to multiple customer locations
• P-Complete Approximation Problems
• Saving an epsilon: a 2-approximation for the k-MST problem in graphs
• Strongly polynomial-time approximation for a class of bicriteria problems.

Cited in

(8)

• 2-approximation algorithm for minmax absolute maximum lateness scheduling-location problem
• Improved approximation algorithm for scheduling on a serial batch machine with split-allowed delivery
• Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains
• A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem
• Single machine scheduling with batch delivery to multiple customers in a star-shaped network
• Algorithms – ESA 2005
• Algorithms and Data Structures
• On the max coloring problem

This page was built for publication: Approximation algorithm for minimizing total latency in machine scheduling with deliveries

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