Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time

DOI10.1142/S0217595918500483zbMath1407.90144OpenAlexW2899589000WikidataQ128968420 ScholiaQ128968420MaRDI QIDQ4561187

Wenhua Li, Xing Chai, Ling-Fa Lu, Li-Qi Zhang

Publication date: 10 December 2018

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0217595918500483

zbMATH Keywords

schedulingonline algorithmbest-possible competitive ratio

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Related Items (4)

Single machine scheduling with rejection to minimize the weighted makespan ⋮ Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines ⋮ Online NDP-constraint scheduling of jobs with delivery times or weights ⋮ Single-machine online scheduling of jobs with non-delayed processing constraint

Cites Work

• Unnamed Item
• Unnamed Item
• Two-agent scheduling to minimize the total cost
• Online over time scheduling on parallel-batch machines: a survey
• A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan
• Minimizing average completion time in the presence of release dates
• Restarts can help in the on-line minimization of the maximum delivery time on a single machine
• On-line algorithms for minimizing makespan on batch processing machines
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Minimizing the total completion time on-line on a single machine, using restarts

This page was built for publication: Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time