A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs

2021/04/13 by Cheriyan, Joseph, Ravi, R., Skutella, Martin · 1 citation
#68W40 #90B35 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Performance (cs.PF)

paper · doi:10.48550/arxiv.2104.06210

Abstract

The Moore-Hodgson Algorithm minimizes the number of late jobs on a single machine. That is, it finds an optimal schedule for the classical problem 1~| |~∑U_j. Several proofs of the correctness of this algorithm have been published. We present a new short proof.

Cited by

• Deadline-Aware Joint Task Scheduling and Offloading in Mobile Edge Computing Systems

Related

• Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
• The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
• Approximation Ratio of LD Algorithm for Multi-Processor Scheduling and the Coffman-Sethi Conjecture
• Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
• Greedy Minimization of the Number of Late Jobs: Deadline Trees, Optimal Prefixes and Tier Matroids