On-line scheduling on a single machine: Maximizing the number of early jobs

DOI10.1016/S0167-6377(00)00061-4zbMath0991.90071OpenAlexW1980008867WikidataQ127124827 ScholiaQ127124827MaRDI QIDQ5929136

Gerhard J. Woeginger, Hoogeveen, J. A., Chris N. Potts

Publication date: 3 September 2002

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(00)00061-4

zbMATH Keywords

single-machine schedulingcombinatorial problemscompetitive analysisonline algorithmsworst-case bounds

Mathematics Subject Classification ID

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

Related Items (25)

Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart ⋮ Online production planning to maximize the number of on-time orders ⋮ On-line production order scheduling with preemption penalties ⋮ Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting ⋮ ON ONLINE SCHEDULING JOBS WITH RESTART TO MAXIMIZE THE NUMBER OF JOBS COMPLETED TIME ON A SINGLE MACHINE ⋮ Online scheduling with delivery time on a bounded parallel batch machine with limited restart ⋮ A survey of single machine scheduling to minimize weighted number of tardy jobs ⋮ Temperature aware online algorithms for scheduling equal length jobs ⋮ Online scheduling with preemption or non-completion penalties ⋮ Online scheduling of jobs with kind release times and deadlines on a single machine ⋮ Online Single Machine Scheduling to Minimize the Maximum Starting Time ⋮ On maximizing the throughput of multiprocessor tasks. ⋮ Online NDP-constraint scheduling of jobs with delivery times or weights ⋮ Unnamed Item ⋮ Online parallel machine scheduling to maximize the number of early jobs ⋮ Workforce-constrained maintenance scheduling for military aircraft fleet: a case study ⋮ 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 ⋮ Temperature Aware Online Algorithms for Scheduling Equal Length Jobs ⋮ Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart ⋮ How much can lookahead help in online single machine scheduling ⋮ Lower bounds on online deadline scheduling with preemption penalties ⋮ LPT online strategy for parallel-machine scheduling with kind release times ⋮ Online scheduling in a parallel batch processing system to minimize makespan using restarts ⋮ Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead

Cites Work

• A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Online algorithms. The state of the art
• An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Scheduling Parallel Machines On-Line
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On-line scheduling on a single machine: Maximizing the number of early jobs