Back to Search
Start Over
A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs
- Publication Year :
- 2021
- Publisher :
- arXiv, 2021.
-
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~|\;|~\sum{U_j}$. Several proofs of the correctness of this algorithm have been published. We present a new short proof.<br />Comment: 3 pages
- Subjects :
- FOS: Computer and information sciences
Schedule
Correctness
Computer science
0211 other engineering and technologies
02 engineering and technology
Management Science and Operations Research
Mathematical proof
01 natural sciences
Industrial and Manufacturing Engineering
010104 statistics & probability
Simple (abstract algebra)
Computer Science - Data Structures and Algorithms
FOS: Mathematics
Mathematics - Combinatorics
Data Structures and Algorithms (cs.DS)
0101 mathematics
Computer Science::Operating Systems
021103 operations research
Computer Science - Performance
Applied Mathematics
90B35, 68W40
Performance (cs.PF)
Combinatorics (math.CO)
F.2.2
Algorithm
Software
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....1a6faa0d52d0db80af23652179d5f789
- Full Text :
- https://doi.org/10.48550/arxiv.2104.06210