Single machine scheduling with job delivery to multiple customers

DOI10.1007/s10951-017-0508-2zbMath1406.90039OpenAlexW2588577004MaRDI QIDQ1617286

Xueshi Wang, Jianming Dong, Guo-Hui Lin, Jueliang Hu

Publication date: 7 November 2018

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

Full work available at URL: https://doi.org/10.1007/s10951-017-0508-2

zbMATH Keywords

approximation algorithmsingle machine schedulingknapsackbin-packingjob delivery

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• Improved algorithms for two single machine scheduling problems
• On the machine scheduling problem with job delivery coordination
• Semi on-line algorithms for the partition problem
• Machine scheduling with job delivery coordination
• Optimal two- and three-stage production schedules with setup times included
• Analysis of a Compound Bin Packing Algorithm
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• SINGLE MACHINE SCHEDULING WITH JOB DELIVERY TO MINIMIZE MAKESPAN
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey