Restarts can help in the on-line minimization of the maximum delivery time on a single machine

DOI<333::AID-JOS53>3.0.CO;2-8 10.1002/1099-1425(200011/12)3:6<333::AID-JOS53>3.0.CO;2-8zbMath0966.90033MaRDI QIDQ1592755

Nodari Vakhania, Marjan van den Akker, Hoogeveen, J. A.

Publication date: 20 August 2001

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

zbMATH Keywords

single-machine schedulingon-line algorithmworst-case analysisrestart

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items (21)

Online integrated production-distribution scheduling problems without preemption ⋮ Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart ⋮ Online scheduling on a parallel batch machine with delivery times and limited restarts ⋮ Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time ⋮ Online scheduling with delivery time on a bounded parallel batch machine with limited restart ⋮ On-line supply chain scheduling problems with preemption ⋮ Improved approximation algorithm for scheduling on a serial batch machine with split-allowed delivery ⋮ An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown ⋮ Online Single Machine Scheduling to Minimize the Maximum Starting Time ⋮ Online NDP-constraint scheduling of jobs with delivery times or weights ⋮ Semi-online two-level supply chain scheduling problems ⋮ On-line integrated production and outbound distribution scheduling to minimize the maximum delivery completion time ⋮ Online scheduling on a single machine with grouped processing times ⋮ A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan ⋮ On-line scheduling on a batch machine to minimize makespan with limited restarts ⋮ Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart ⋮ Integrated production and delivery scheduling on a serial batch machine to minimize the makespan ⋮ Integrated scheduling of production and distribution with release dates and capacitated deliveries ⋮ Single-machine online scheduling of jobs with non-delayed processing constraint ⋮ Online scheduling in a parallel batch processing system to minimize makespan using restarts ⋮ On-line integrated production-distribution scheduling problems with capacitated deliveries

Cites Work

• Unnamed Item
• Nonclairvoyant scheduling
• New lower and upper bounds for on-line scheduling
• Algorithms for Scheduling Tasks on Unrelated Processors
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling Parallel Machines On-Line
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Restarts can help in the on-line minimization of the maximum delivery time on a single machine