The Optimal Competitive Ratio Is 19/16 for Semi-Online Scheduling on Five Identical Machines with Nonincreasing Processing Times
Jobs arrive one at a time in nonincreasing order of processing time and must be assigned immediately to five identical machines. The input may stop after any job. We give a deterministic algorithm whose makespan on every prefix is at most 19/16 times its offline optimum. The algorithm tries placements using the sizes of the jobs already seen and always uses a least-loaded machine from job 13 onward. Before a first violation, every machine holds at most three jobs, so it suffices to examine the first sixteen jobs. Depending on whether an optimal packing requires a four-job bin, the available slots force particular machines to receive jobs 6 and 7 or force job 8 to fail its first trial. Comparing these necessary placements with the algorithm excludes the remaining stopping points. An input with three job sizes and its early stops give a matching lower bound.
Authors
- Chaojin Wu (ORCID: https://orcid.org/0009-0008-7322-9291)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24409951
- Primary Topic
- Optimization and Search Problems
- Type
- preprint